|
W artykule tym zajmiemy się problemem wydawania reszty.Omówimy algorytm wydawania reszty, a także przedstawimy jego implementację w C++.Zaczynamy! Na co dzień spotykamy się z urządzeniami mającymi zaimplementowany algorytm do wydawania reszty.Są to automaty z napojami czy bankomaty.Na pozór te urządzenia są bardziej skomplikowane, niż może się wydawać.Problem wydawania reszty to zagadnienie z dziedziny algorytmiki.Problem zajmuje się kwestią wydania reszty należności ze zbioru dostępnych nominałów, przy czym ilość wydawanych monet/banknotów powinna być minimalna.Problem ten rozwiązuje się dwoma algorytmami: algorytmem zachłannym i za pomocą programowania dynamicznego.My zajmiemy się tym pierwszym.Algorytm zachłanny jest ograniczony jedną własnością: przy rozwiązywaniu problemu wydawania reszty zakładamy, że mamy nieograniczoną ilość monet i banknotów o różnych nominałach.
Na potrzeby programu wprowadzimy sobie kilka zmiennych i oznaczeń. k - zmienna typu int, mówiąca o reszcie do wydania
x - liczba monet/banknotów, które otrzyma klient
int N[8] = {200,100,50,20,10,5,2,1}; //tablica nominałów posortowana rosnąco
int X[8] = {0,0,0,0,0,0,0,0};// każdy indeks tablicy to informacja, ile klient dostanie banknotów 1 zł, 2 zł, 5 zł itd. Jak działa algorytm zachłanny rozwiązujący problem wydawania reszty Na początku wprowadzamy lub wyliczamy kwotę potrzebną do wydania klientowi.Jest to nasza zmienna k.Dalej, algorytm wyszukuje największy nominał n ze zbioru nominałów ale taki, aby nie przekraczał on pozostałej kwoty do wydania.Mając taki nominał, od pozostałej kwoty do wydania k odejmujemy ten właśnie największy nominał n.Program pracuje w pętli, a więc za każdym razem jak zostanie znaleziony największy nominał do wydania, zwiększa się licznik x niosący ze sobą informację o liczbie monet/banknotów wydanych klientowi.Algorytm powinien więc znajdować minimum funkcji wydawania liczby monet/banknotów.Jako, że nasz program nie tylko podaje ile monet/banknotów dostanie z powrotem klient, ale także rozbija tę ilość na poszczególne nominały, wprowadziłem zmienną tablicową X przechowującą liczbą poszczególnych nominałów wydanych klientowi.W zmiennej tablicowej N natomiast wpisane są wszystkie dostępne nominały.Dla ułatwienia, algorytm nie uwzględnia monet mniejszych od 1 zł, a podawana kwota musi być liczbą całkowitą (int). Tworzymy program do wydawania reszty Na formę kładziemy 1 pole Edit służące do wprowadzania kwoty do wydania.Także 1 przycisk, do niego podpięta będzie akcja obliczania reszty.Dodatkowo w programie testowym wykorzystałem 9 kontrolek Label oraz 9 kontrolek StaticText.Zdefiniujmy dwie zmienne globalne: int N[8] = {200,100,50,20,10,5,2,1}; //tablica nominalow posortowana rosnaco
int X[8] = {0,0,0,0,0,0,0,0};//tablica liczby nominalow każdego rodzaju wydanych w kolejnosci wg NAlgorytm programu jest następujący: int k = Edit1->Text.ToIntDef(0);//do wydania przy kasie
int x = 0; //liczba monet do wydania
while(k>0)
{
int n = 0;//maksymalny nominal mniejszy lub rowny kwocie pozostalej do zaplaty
int ile_nominalow = ARRAYSIZE(N);//ilosc elementow tablicy N
int kolejny=-1;//bo indeksy tablicy zaczynaja sie od 0
for(int i=0;i<ile_nominalow;++i) //znajdowanie najwiekszego nominalu do wydania
{//i oznacza indeks nominalu
if( (N[i]<=k)&&(N[i]>n) )
{
n=N[i];
kolejny=i;
}
}
k-=n;
++x;
X[kolejny]+=1;
}
Label1->Caption = x; //liczba monet/banknotow do wydania
Label2->Caption = X[0];
Label3->Caption = X[1];
Label4->Caption = X[2];
Label5->Caption = X[3];
Label6->Caption = X[4];
Label7->Caption = X[5];
Label8->Caption = X[6];
Label9->Caption = X[7];
Zrzut ekranu prezentowanego programu można zobaczyć tu, a pobrać program można tu.Zapraszam do komentowania artykułu.
|
