Wyszukiwanie binarne
Jest to algorytm działający na zasadzie metody dziel i zwyciężaj. Metoda ta polega na podziale naszego problemu na mniejsze problemy, które zazwyczaj są tym samym problemem, ale przez to że ma on teraz mniejszy rozmiar, łatwiej jest go pokonać. Dalej rozwiązane problemy scala się, aby uzyskać w ten sposób rozwiązanie całego zadania.
Zasada działania algorytmu wyszukiwania binarnego polega na podzieleniu listy z danymi na połowę i sprawdzaniu czy element szukany znajduje się w miejscu podziału, jeżeli tam się nie znajduje to sprawdzamy czy jest większy lub mniejszy. W taki oto sposób wydajnie zawężamy zakres naszych poszukiwań w liście z danymi, aż w pewnym momencie natrafimy na element który jest przez nas poszukiwany lub po prostu go nie znajdujemy. W najgorszym przypadku nasz program będzie miał złożoność czasową log2n gdzie n to długość przeszukiwanej tablicy.
W podstawowej wersji algorytm ten działa w następujący sposób:
- lista z danymi jest posortowana (np. lista liczb)
- algorytm dzieli ją na dwie równe części (listy)
- następnie sprawdza czy znalazł szukaną liczbę.
- Jeżeli nie, to sprawdza która część zawiera zakres liczb poszukiwanych (gdy widzi, że w zbiorze po lewej stronie są liczby mniejsze, to nie zajmuje się szukaniem w tym zbiorze, tylko sprawdza zbiór po stronie prawej)
- ponownie, dzieli go na 2 równe części (listy)
- następnie sprawdza czy znalazł szukaną liczbę, dzieli zbiór itd.
Oto przykład działania takiego algorytmu, gdzie poszukujemy liczby 14 :
Do ustalenia miejsca gdzie znajduje się środek naszej listy używamy wzoru:
gdzie:
s – środek listy (miejsce podziału na dwie kolejne)
p – początek listy
k – koniec listy
Algorytm wydawania reszty
Algorytm wydawania reszty polega na tym że dzielimy wartość (resztę do wydania) na jak najmniejszą ilość elementów. Ma to na celu wydanie reszty przy użyciu najmniejszej możliwej ilości banknotów/bilonów. Algorytm ten często też jest nazywany problemem wydawania reszty.
Działanie tego algorytmu polega na podzieleniu wartości (reszty do wydania) na jak najmniejszą liczbę elementów. Oznacza to wydanie reszty przy pomocy możliwie jak najmniejszej liczby banknotów/bilonów. Aby móc wydać resztę musimy w pierwszej kolejności ustalić listę dostępnych nominałów. Może to być tablica o wartościach [500, 200, 100, 50, 20, 10, 5, 2, 1, 0,50, 0,20, 0,10, 0,05, 0,02, 0,01]
Do rozwiązania tego problemu użyjemy metody zachłannej, oznacza to że do wypłacania reszty będziemy musieli używać największych dostępnych nam nominałów. Ważne jest to że nominał musi być mniejszy lub równy wydawanej wartości.
Najprościej znaleźć rozwiązanie, gdy listę dostępnych dla nas nominałów uporządkujemy malejąco. W pierwszej kolejności będziemy szukać wartości mniejszej lub równej wypłacanej kwocie. Gdy znajdziemy ją, używamy największej możliwej ilości znalezionego nominału (będzie to wynik dzielenia bez reszty wypłacanej kwoty przez wartość wskazanego przez nas nominału). Kolejnym krokiem będzie zmniejszenie reszty o wartość kwoty wypłaconej za pomocą bieżącego nominału. W późniejszym kroku powtarzamy szukanie. Czynność tą powtarzamy tak długo aż wypłacimy całą sumę.
