Skonstruuj algorytm zachłanny w postaci specyfikacji, listy kroków i schematu blokowego realizujący wydawanie reszty klientowi w taki sposób, aby otrzymał jak najmniejszą liczbę monet i banknotów.
w pythonie
w pythonie
Odpowiedź:
Poniżej przedstawiam kod w Pythonie:
def wydaj_reszte(reszta, nominaly):
nominaly.sort(reverse=True)
wydane_nominaly = []
for nominal in nominaly:
while reszta >= nominal:
wydane_nominaly.append(nominal)
reszta -= nominal
return wydane_nominaly
Poniżej znajduje się schemat blokowy przedstawiający ten algorytm zachłanny:
START
Posortuj nominali malejąco
Zdefiniuj wydane_nominaly jako pustą listę
Dla każdego nominału w liście nominali:
Jeśli reszta >= nominal:
Dodaj nominal do wydane_nominaly
Odejmij nominal od reszta
Zwróć wydane_nominaly jako wynik
STOP
Wyjaśnienie: