Implementacja algorytmu wydawania reszty w języku Python

Nominal 50 wydano 1 razy
Nominal 20 wydano 1 razy
Nominal 10 wydano 0 razy
Nominal 5 wydano 1 razy
Nominal 2 wydano 1 razy
Nominal 1 wydano 0 razy
Liczba nominalow uzytych do wydania reszty 77: 4

Poniżej przedstawiono przykładową implementację algorytmu zachłannegoalgorytm zachłannyalgorytmu zachłannego,  który może zostać wykorzystany do rozwiązania problemu. Funkcja zachlanne_wydawanie_reszty() przyjmuje dwa parametry:

• reszta_do_wydania – wartość reszty do wydania,

• nominaly – tablica dostępnych nominałów posortowana malejąco,

Zmienna k wewnątrz pętli for przechowuje maksymalną liczbę powtórzeń danego nominału, przy pozostałej kwocie do wydania reszta_do_wydania. Wartość reszta_do_wydania jest zmniejszana o maksymalną wartość, którą można wydać danym nominałem. Algorytm zwraca liczbę monet lub banknotów użytych do wydania reszty o początkowej wartości reszta_do_wydania.

def zachlanne_wydawanie_reszty(reszta_do_wydania, nominaly):
    wynik = 0

    for nominal in nominaly:
        k = reszta_do_wydania // nominal
        wynik += k
        reszta_do_wydania -= k * nominal

        print("Nominao " + str(nominal) + " wydano " + str(k) + " razy")

    return wynik

nominaly = [50, 20, 10, 5, 2, 1]
reszta_do_wydania = 77
k = zachlanne_wydawanie_reszty(reszta_do_wydania, nominaly)

print("Liczba nominałów użytych do wydania reszty " + str(reszta_do_wydania) + ": " + str(k))

Przyjrzyjmy się innej implementacji funkcji zachlanne_wydawanie_reszty(), która w celu określenia liczby nominałów potrzebnej do wydania reszty reszta_do_wydania używa operacji dzielenia modulo. Możemy podzielić całkowicie resztę reszta_do_wydania przez dany nominał. Dzięki temu dowiemy się, ile sztuk danego nominału algorytm użyje do wydania reszty. Operacja modulo reszta_do_wydania %= nominal zwróci informację o tym, jaka kwota pozostała do wydania.

def zachlanne_wydawanie_reszty(reszta_do_wydania, nominaly):
    wynik = 0

    for nominal in nominaly:
        k = reszta_do_wydania // nominal
        wynik += k
        reszta_do_wydania %= nominal

        print("Nominal", nominal, "wydano", k, "razy")

    return wynik

nominaly = [50, 20, 10, 5, 2, 1]
reszta_do_wydania = 77
k = zachlanne_wydawanie_reszty(reszta_do_wydania, nominaly)

print("Liczba nominałów użytych do wydania reszty", reszta_do_wydania, ":", k)

Nie możemy zapomnieć o przypadku, w którym reszta będzie liczbą zmiennoprzecinkową. W Polsce do wydawania reszty po przecinku używamy nominałów 50 gr, 20 gr, 10 gr, 5 gr, 2 gr, 1 gr. W przypadku języka Python, podczas wydawania reszty, należy pamiętać o niedokładnościach w reprezentacji liczb zmiennoprzecinkowych. Operacje na takich liczbach powodują pewne niedokładności. Dlatego, aby nasze obliczenia były precyzyjne, najłatwiej jest zamienić wszystkie nominały na grosze. W takiej sytuacji resztę 19,99 zł zamienimy na 1999 gr, co pozwoli na łatwe i dokładne określenie minimalnej liczby monet lub banknotów potrzebnych do wydania reszty.

Słownik