Spotkanie 3 

Algorytm zachłanny (ang. greedy algorithm) – algorytm, który w celu wyznaczenia rozwiązania w każdym kroku dokonuje zachłannego, tj. najlepiej rokującego w danym momencie wyboru rozwiązania częściowego.


Problem wydawania reszty.

Problem wydawania reszty polega na podzieleniu wartości (reszty do wydania) na jak najmniejszą liczbę elementów. Czyli na wydaniu reszty przy pomocy najmniejszej możliwej liczby banknotów/bilonów. By wydać resztę musimy najpierw ustalić listę dostępnych nominałów. Niech będzie to tablica N o wartościach {200, 100, 50, 20, 10, 5, 2, 1}
Problem ten daje się rozwiązać przy pomocy metody zachłannej, czyli do wypłacania reszty będziemy zawsze używać największych dostępnych nominałów. Oczywiście użyty nominał musi być mniejszy lub równy wydawanej wartości.
Najłatwiej znaleźć rozwiązanie, gdy tablicę dostępnych nominałów posortujemy malejąco. A więc, najpierw szukamy wartości mniejszej lub równej wypłacanej kwocie. Po znalezieniu jej używamy największej możliwej ilości znalezionego nominału. Tą liczbą jest wynik dzielenia bez reszty wypłacanej kwoty przez wartość odnalezionego nominału. 

Resztę do wydania należy zmniejszyć o kwotę wypłaconą za pomocą bieżącego nominału. I powtórzyć szukanie. Czynność tą powtarzamy tak długo aż wypłacimy całą sumę.

Jedną z metod rozwiązania owego problemu, jest blok schematowy.

Schemat postępowania można przedstawić za pomocą następującego schematu blokowego:

Inne sposoby rozwiązania problemu :

1)  LISTA KROKÓW - Jest to szczegółowo wytłumaczona, krok po kroku, instrukcja osiągnięcia celu przy użyciu tylko słów, symboli matematycznych bądź logicznych. Jest ona również najszybszym sposobem przedstawienia algorytmu, jednak nie jest ona aż tak przejrzysta jak schemat blokowy.

2) ROZWIĄZANIE W EXEL'U

3) SCHEMATY BLOKOWE ( jak przykład pozyżej)

4) VBA (listing) -  język programowania oparty na Visual Basicu (VB) zaimplementowany w aplikacjach pakietu Microsoft Office oraz kilku innych.

5) TURBO PASCAL  - jedna z popularniejszych implementacji kompilatorówjęzyka Pascal, zintegrowane środowisko programistyczne

6) C++ – język programowania ogólnego przeznaczenia.