Fotomontaż-obraz uzyskany poprzez zmontowanie
kilku fotografii, ich wycinków lub innych
elementów graficznych
![]() |
| SCHEMAT BLOKOWY
ALGORYTM ZACHŁANNY-Algorytm zachłanny jest poprawny dla tego problemu w większości stosowanych obecnie systemów monetarnych, jednak nie działa np. dla systemu (1, 4, 5) (kontrprzykładem jest kwota 8).
W tym przypadku, algorytm będzie wartość:
Algorytm odejmuje od zadanej kwoty największy spośród nominałów mniejszych i równych kwocie. Następnie, o ile kwota jest większa od zera, powtarza czynność. Liczba powtórzeń jest liczbą potrzebnych monet.
Wadą rozwiązania zachłannego jest brak możliwości wykorzystania w przypadku, gdy nominały mogą być tak dobrane, że nie zawsze znajdzie się nominał, przez który kwota dzieli się bez reszty. Przykładem jest sytuacja z życia codziennego: nominały w bankomatach to zwykle 20, 50, 100 i 200 zł. Algorytm zachłanny zastosowany przy takich nominałach dla kwoty 60 zł nie zadziałałby – w pierwszym kroku pomniejszyłby kwotę o 50 zł, pozostawiając 10 zł; tak mała kwota nie może być wydana przy użyciu w/w nominałów.
W bankomatach stosowany jest więc algorytm z wykorzystaniem programowania dynamicznego.
Algorytm zachłanny zapisany w C++:// k – zadana kwota, x=0 – wynik // N – zbiór nominałów (tablica o długości l) while (k > 0) // dopóki kwota większa od zera { int n = 0; // n – maksymalny nominał mniejszy lub równy kwocie for (int i = 0; i < l; ++i) // wśród wszystkich nominałów... { if ((N[i] <= k) && (N[i] > n)) // ...znajdź n n = N[i]; } k -= n; // pomniejsz kwotę o n ++x; // zwiększ wynik o 1 } |