W Europie monety mają wartość 1, 2, 5, 10, 20, 50, 100 (w Polsce zwana złotówką), 200, 500 (nie wszędzie). W Stanach Zjednoczonych występują monety o nominałach 1, 5, 10, 25, 50, 100 centów, przy czym 100 centów składa się na jednego dolara. Systemy te są o tyle poręczne, że zawsze najkorzystniejszym sposobem wydawania reszty jest tzw. algorytm zachłanny. Polega on na tym, że wymaganą kwotę dobiera się wybierając zawsze maksymalny nominał, który możemy wziąć bez nadwyżki.
Przykładowo, aby wydać 86 groszy, należy - stosując ten algorytm - użyć monet 50, 20, 10, 5, 1 groszy, zaś w systemie amerykańskim 50, 25, 10, 1 centów, czyli o jedną monetę mniej. Czy to oznacza, że drugi system jest lepszy?
Z pewnością nie w każdym przypadku (np. nie dla 20) - wielu algorytmikom spędzało to sen z powiek. Kilkanaście lat temu w Waterloo przeprowadzono badania komputerowe, które miały na celu wyliczenie, który z systemów monetarnych jest lepszy i jakie monety należy wprowadzić (bądź wykluczyć) z obiegu, aby algorytm zachłanny wykorzystywał średnio jak najmniej monet. Przy nominałach 1, 5, 10, 25 średnia monet do wypłacenia kwoty od jednego do 99 centów wyniosła 4,7. Czy da się obniżyć tę średnią stosując inny zestaw czterech monet? Badania pokazały, że tak!
Takim optymalnym zestawem byłoby 1, 5, 18, 29 centów lub 1, 5, 18, 25 centów. Wtedy średnia monet wykorzystywanych do transakcji poniżej stu centów wyniosłaby 3,89. Ciekawym wydaje się drugi układ, gdyż wymagałby zmiany jedynie jednej z czterech istniejących monet. Podobne rozważania można snuć dla różnych systemów monetarnych na świecie.
Brak komentarzy:
Prześlij komentarz