algorytm.org

Problem wydawania reszty

Pomoc
Potrzebujesz algorytmu/kodu źródłowego, którego nie znalazłeś(aś) w serwisie?
Zamów algorytm!
Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Problem wydawania reszty
Ocena użytkowników:***** / 118
SłabyŚwietny 
Wpisany przez Michał Witaszek, 17 czerwca 2011 13:24

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

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


Przykład:

Przyjmijmy dostępne nominały (200, 100, 50, 20, 10, 5, 2, 1) PLN.
Załóżmy że chcemy wypłacić kwotę 148 PLN.

Największym nominałem nie większym niż 148 jest 100.
148 div 100 = 1 Wypłacamy jeden banknot 100 PLN.
148 – (100*1) = 48, zostało nam jeszcze do wydania 48 PLN.

Kolejną wartością nie większą niż aktualna reszta jest 20.
48 div 20 = 2 Wypłacamy dwa banknoty 20 PLN.
48 – (20*2) = 8, zostało nam jeszcze do wydania 8 PLN.

Największy nominał nie większy niż 8 to 5 PLN
8 div 5 =1 Wypłacamy monetę 5 PLN
8 – 5 = 3, zostało nam jeszcze do wydania 3 PLN.

Wartość nie większa niż 3 to 2
3 div 2 = 1 Jedna moneta 2 PLN
3 – 2 = 1

Do wydania pozostaje już tylko złotówka
1 – 1 = 0

Reszta została wydana za pomocą nominałów:
100*1 + 20*2 + 5*1 + 2*1 + 1*1 = 148

Przyjmijmy teraz, że mamy również do dyspozycji grosze. Zatem tablica naszych nominałów wyglądać będzie teraz następująco: (200, 100, 50, 20, 10, 5, 2, 1, 0.50, 0.20, 0.10, 0.05, 0.02, 0.01) PLN.
Załóżmy że chcemy wypłacić kwotę 12.45 PLN.

Największym nominałem nie większym niż 12.45 jest 10.
12.45 / 10 = 1.245, bez reszty to 1, a więc Wypłacamy jeden banknot 10 PLN.
12.45 – (10*1) = 2.45.

Teraz największym nominałem nie większym niż 2.45 jest 2.
2.45 / 2 = 1.225, bez reszty to 1, a więc Wypłacamy jedną monetę 2 PLN.
2.45 – (2*1) = 0.45

Zostało nam więc do wypłacenia jeszcze 45 groszy, największy możliwy nominał to 0.20 czyli 20 groszy.
0.45 / 0.20 = 2.25, bez reszty to 2, zatem wypłacamy 2 monety 20 groszowe.
0.45 - (0.20*.) = 0.05

Do wydania pozostaje już tylko 5 groszy
0.05 – 0.05 = 0

Reszta została wydana za pomocą nominałów:
10*1 + 2*1 + 0.20*2 + 0.05*1 = 12.45

Przykład w JavaScript:

Podaj kwote:

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Jacek GzelC#
.cs
.cs
***** / 4
Michał WitaszekC/C++
.cpp
.cpp
***** / 14
Michał WitaszekDelphi/Pascal
.pas
.pas
***** / 1
Dominik GoździukJava
.java
.java
***** / 0
Tomasz LubińskiJavaScript
.js
.js
***** / 3
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 15 sierpnia 2012 09:49
Komentarze
photo
-4 # Zajączkowski 2011-09-13 05:34
Jeżeli dana jest tablica nominałów A={a1, a2, a3, ..., an}, posortowana tak, że ai jest mniejsze od a(i+1) to algorytm zachłanny będzie działał poprawnie, jeżeli spełniony zostanie warunek ai mniejsze lub równe a(i+1) / 2. Przykład niepoprawnego wydawania reszty dla nominałów A={1, 2, 5, 6}, reszta do wydania to 10, algorytm zachłanny najpierw weźmie nominał o największej wartości, czyli w tym przypadku 6, po czym wybierze dwa nominały 2, 2. Algorytm zachłanny w tym przypadku nie zadziałał poprawnie, ponieważ można było wydać dwa nominały po 5 a nie trzy 6, 2, 2.
Oczywiście system monetarny jest tak dobrany, by spełniał warunek ai mniejsze bądź równe a(i+1)/2
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+2 # PawełT 2012-02-21 17:59
nominały: 1, 200, 483.. kwota: 600.. nadal poprawne?
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-9 # Witamaster 2012-02-22 20:21
Przy pomocy nominałów 483, 200, 1 algorytm zachłanny wyda kwotę 600 w następujący sposób:
1 x 483,
117 x 1.

Algorytm zachłanny działa tu prawidłowo gdy nominały posortowane malejąco spełniają warunek: ai mniejsze bądź równe a(i+1)/2.
Podane nomonaly spełniają ten warunek.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-4 # Andrzejlika 2015-10-27 09:36
Dobra robota
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz