Algorytm poszukiwanie przez połowienie

Specyfikacja:

Dane: Zbiór elementów w postaci ciągu n uporządkowanych liczb x1<= x2<= …<=xn. Wyróżniony element y. Wynik: Jeśli y należy do tego zbioru, podaj miejsce (index) w ciągu, w przeciwnym razie sygnalizuj brak takiego elementu w zbiorze.

Algorytm:

Powtarzaj kroki 1-3, dopóki nie natrafisz na poszukiwany element.

Krok 1: Sprawdź element środkowy ciągu (gdy ciąg ma nieparzystą liczbę elementów) lub jeden z dwóch elementów środkowych (gdy ciąg ma parzystą liczbę elementów).

Krok 2: Jeśli jest on elementem poszukiwanym y, to zakończ algorytm.

Krok 3: Jeśli środkowy element jest większy od y, to pozostaw podciąg na lewo od elementu środkowego, a w przeciwnym wypadku (gdy element środkowy jest mniejszy od y), pozostaw podciąg na prawo od elementu środkowego.

Zadanie: Zapisz program „Zgadnij jaka to liczba?” odpowiadający na podane pytanie.
Wybierz partnera z grupy. Następnie partner wymyśli dowolną liczbę n z przedziały [1, 50], a Ty masz ją znaleźć, zadając mu pytania typu: „Czy to jest liczba …?” Na co Twój partner może jedynie odpowiedzieć : „Tak”- gdy trafiłeś, lub „Za mała”, „Za duża”- w zależności od położenia wybranej przez Ciebie liczby względem ukrytej liczby.

Wytłumaczenie do tego algorytmu z forum elektroda:
Jak się szuka? Mamy przykładowo 32 liczby, od zera do 31
1.
zakresDolny = 0
zakresGorny = 31

2.
pozycja = w połowie = (zakresDolny+zakresGorny)/2

3.
Jeżeli tablica[pozycja] == szukana to znaleziono, exit.

Jeżeli liczba w tablicy na pozycji `pozycja` jest mniejsza od szukanej, to przesuwamy dolny zakres nad aktualną pozycję, bo szukanej liczby na pewno nie będzie niżej (zakresDolny=pozycja+1).

Jeżeli liczba w tablicy na pozycji `pozycja` jest większa od szukanej, to znaczy że jesteśmy za wysoko, więc górna granica spada poniżej aktualnej pozycji: zakresGorny=pozycja-1.

Jeżeli górny zakres nie jest większy od dolnego, powtórz od kroku 2.


Jeżeli nie znaleziono liczby, to automatycznie mamy pozycję na którą można wstawić nową liczbę (przesuwając wszystkie elementy po `prawej` w `prawo` o jedną pozycję). Jest nią pozycja+x, gdzie x jest jedynką tylko wtedy, gdy ostatnie porównanie podniosło dolną granicę.

Kod:
On: Pomyślałem sobie liczbą od zera do 31, zgadnij jaką? (pomyślał sobie 9)
Ja: (liczę...)
zakresDolny = 0
zakresGorny = 31
połowa = (zakresDolny+zakresGorny)/2 = 15

Ja: pytam czy to 15
On: mniej

Ja: (liczę... zostały liczby 0-14)
zakresDolny = 0
zakresGorny = 15-1 = 14
połowa = (0+14)/2 = 7

Ja: pytam czy to 7
On: więcej

Ja: (liczę... zostały liczby 8-14)
zakresDolny = 7+1 = 8
zakresGorny = 14
połowa = (8+14)/2 = 11

Ja: pytam czy to 11
On: mniej

Ja: (liczę... zostały liczby 8,9,10)
zakresDolny = 8
zakresGorny = 11-1 = 10
połowa = (8+10)/2 = 9

Ja: pytam czy to 9
On: Tak

Implementacja w C++

#include <iostream>

using namespace std;

const int n = 50;
const int y = 10;

int wyszukaj (int p, int k, int tab[])
{
int l_zbioru = k - p;
int polowa_liczb = l_zbioru/2;
int srodek_zbioru = p + polowa_liczb;



    if ( y == tab[srodek_zbioru]) return tab[y];
    if (l_zbioru < 0) return 0;

    if ( y < tab[srodek_zbioru]  )
        {
           return wyszukaj(p,srodek_zbioru-1,tab);

        }

    if ( y > tab[srodek_zbioru] )  return  wyszukaj (srodek_zbioru+1,k,tab);



}
int main()
{
    int tab[n];
    for (int i = 1; i<=n; i++)
    {
        tab[i] = i;

    }

    cout << wyszukaj(1,n,tab);
    return 0;
}

Naprawa przedniego pokrętła w aparacie Canon Powershot G11

Aparat ten ma jedną wadę, po około roku, przednie kółko (pokrętło) zaczyna działać dziwnie, gdy kręcimy nim w górę zamiast standardowo zwiększać parametry zmniejsza je o parę i zwiększa o trochę więcej. Trudno to wytłumaczyć ;p

Naprawa to 3 minuty roboty, wystarczy nam jakikolwiek spray do czyszczenia styków, psikamy nim na kółko kręcimy parę razy i zostawiamy do wyschnięcia (oczywiście aparat wcześniej wyłączamy, i wyjmujemy baterię).


Jeśli to nam nie pomogło zostaje nam trik polegający na przytrzymywaniu klawisza programowalnego ( s ) i klikaniu przycisków prawo(flash) lewo(makro) w celu zmiany parametrów, zmienianych standardowo za pomocą kółka.

Metoda pucharowa - algorytm turniejowy

Zadanie z publikacji Macieja M. Sysło, "Wyszukiwanie i porządkowanie informacji":
Zapisz w postaci listy kroków algorytm służący do znajdowania największej liczby w ciągu „metodą pucharową”; dany ciąg może mieć dowolną długość, nie koniecznie będąca potęgą liczby 2. Przyjmij, że na początku ciąg liczb jest dany w tablicy i postaraj się, by w trakcie algorytmu pozostałe z ciągu liczby także były pamiętane w tej samej tablicy. Zaimplementuj opisany algorytm w wybranym języku programowania.

Czyli piszemy program na znalezienie osoby która wygra turniej.
Dla ułatwienia dodałem dużo cout-ów służących jedynie analizie działanie programu.

Implementacja w C++ metody pucharowej:

#include <iostream>

using namespace std;

int main()
{
    srand(time(NULL));
    int n;
    cin >> n;
    int tab[n];

    for ( int i = 0 ; i < n ; i++)
    {
        tab[i] = rand()%100+1;
        cout << tab[i]<< "  ";
    }

    int p = n;  // dodatkowa zmienna p
    int j = 0;
do{
    for (int i = 0; i < n; i += 2)
    {
        if (i+1 < p ){

        cout << endl<< "walczy:" << tab[i] << " z : " << tab[i +1] ;
        //wygranych ustawiamy na poczatku tabeli w miejsca poprzednich przegranych
        if(tab[i] > tab[i+1] ) swap(tab[i/2], tab[i]);
            else swap(tab[i/2], tab[i+1]);
        cout << " wygral: " << tab[i/2];
        j++; // zwiekszamy licznik meczy
        }
        else swap(tab[i], tab[i/2]) ; // w przypadku nieparzystej liczby zawodnikow, ostatniego zawodnika umieszczamy na miejscu ostatniego przegranego
    }

   cout <<endl<<"Tabela po "<< j << " meczach: " << endl;
   for ( int i = 0 ; i < p ; i++)
   {
       cout << tab[i]<< "  ";
    }

    n = n/2;

}while (j != p-1);  // ilosc meczy ktore musza byc rozegrane to n-1

cout << endl << "Ostateczny wyglad tabeli: " <<endl;

for ( int i = 0 ; i < p ; i++)
{
    cout << tab[i]<< "  ";
}

cout << endl<< "Zwyciezca turnieju: " << tab[0];
    return 0;
}

Algorytm Selection Sort – porządkowanie przez wybór

Algorytm Selection Sort – porządkowanie przez wybór

Specyfikacja:
Dane: Liczba naturalna n i ciąg n liczb x1, x2, …, xn
Wynik: Uporządkowane dane ciągu liczb od najmniejszej do największej, czyli ciąg wynikowy spełnia nierówność x1<= x2<= …<= xn (Uwaga! Elementy ciągu danego i wynikowego oznaczamy tak samo, gdyż porządkowanie odbywa się in situ, czyli „w miejscu”. ) Algorytm:
Krok 1: Dla i=1, 2, 3,…, n-1 wykonaj kroki 2 i 3, a następnie zakończ algorytm.
Krok 2: Znajdź k takie, xk jest najmniejszym elementem w ciągu xi,…, xn.
Krok 3: Zamień miejscami elementy xi oraz xk.


Zadanie: Zrealizuj powyższy problem dla wybranego n. Elementy losuj z zakresu
od -50 do 50.


Realizacja w C++ (kompilator Code::Blocks)

#include <iostream>

using namespace std;

int n;

int min_i(int tab[], int od)
{
    int min_in = 0;
    int min = 1000;

    for (int i = od; i<n; i++)
    {
        if (tab[i]<min)
        {
            min_in = i;
            min = tab[i];
        }

    }
    return min_in;
}


int main()
{
    srand(time(NULL));
    cout << "Podaj ilosc liczb do posortowania:";
    cin >>n;
    int tab[n];

    for (int i = 0 ; i < n ; i ++ )
    {
        tab[i] = rand()%101 -50 ;  // losujemy 101 liczb (od -50 do 50)
         cout.width(2);
        cout << i <<": " <<tab[i]<<endl;
    }



    cout <<endl <<"Po sortowaniu:" << endl;

    int k;
    for (int i = 0; i< n-1 ; i++ )
    {

        k = min_i(tab, i);
        swap(tab[i],tab[k]);
    }


    for (int i = 0 ; i < n ; i++ )
    {
        cout.width(2);
        cout << i <<": " <<tab[i]<<endl;
    }

    return 0;
}