kasjer

KASJER

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ę.

Opis słowny algorytmu wydawania reszty.

Dane: Kwota pieniędzy do wydania, nominały banknotów i bilonu uporządkowane malejąco

Wyniki: Ilość poszczególnych nominałów banknotów i bilonu

Krok 1: Ustalenie wartości początkowych

Krok 2: Sprawdzamy, ile razy najwyższy nominał mieści się w kwocie do wydania

Krok 3: Obliczamy resztę do wydania: poprzednia kwota - obliczona ilość * nominał

Krok 4: Przechodzimy do niższego nominału

Krok 5: Jeśli reszta do wydania = 0 [stop] w przeciwnym razie powtarzamy kroki 2 - 4

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