Problem wydawania reszty - problem polegający na
wybraniu z danego zbioru monet o określonych nominałach takiej konfiguracji, by
wydać żądaną kwotę przy użyciu minimalnej liczby monet. Jego rozwiązania są
wykorzystywane w automatach z napojami, bankomatach itd.
Algorytm
to skończony, uporządkowany zbiór jasno zdefiniowanych czynności, koniecznych
do wykonania pewnego zadania, w ograniczonej liczbie kroków.
Opis słowny algorytmu wydawania reszty.
Dane: Kwota pieniędzy do wydania, nominały banknotów i
bilonu uporządkowane malejąco
Wyniki: Ilość poszczególnych nominałów banknotów i
bilonu
Krok 1: Ustalenie wartości początkowych
Krok 2: Sprawdzamy, ile razy najwyższy nominał mieści
się w kwocie do wydania
Krok 3: Obliczamy resztę do wydania: poprzednia kwota
- obliczona ilość * nominał
Krok 4: Przechodzimy do niższego nominału
Krok 5: Jeśli reszta do wydania =0 [stop] w przeciwnym
razie powtarzamy kroki 2-4
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:
Za pomocą programu Excel można stworzyć kalkulator, który automatycznie
liczy jaką resztę kasjer ma wydać.
Za pomocą języków programowania można rozwiązać problem wydawania reszty.
Pascal
Pascal to język programowania wysokiego poziomu. Za jego pomocą można napisać proste
lub złożone programy trybu tekstowego. Język Pascal został opracowany w 1971 roku przez Niklaus-a Wirth - szwajcarskiego informatyka.
Kod Pascala jest bardzo przejrzysty i czytelny. Intuicyjne nazwy poleceń sprawiają, że jego nauka jest dosyć prosta.
Obecnie czysty Pascal nie jest używany do zastosowań profesjonalnych. Został on wyparty przez nowsze języki programowania,
które okazują się bardziej funkcjonalne.
program Reszta;
{$APPTYPE CONSOLE}
uses
SysUtils;
var
//tablica dostepnych nominalow
N: Array [1..8] of integer = (200, 100, 50, 20, 10, 5, 2, 1);
i,P,R: integer;
begin
Write('Podaj reszte do wyplacenia: ');
ReadLn(R);
i:=1;
while (R>0) do //dopoki nie wydano calej reszty
begin
if R>= N[i] then //sprawdz czy mozna wydac danym nominalem
begin
P:= R div N[i]; //ile razy wydac dany nominal
R:= R - (P*N[i]); //zmniejsz reszte o wydany nominal
WriteLn(N[i], ' x ', P); //wypisz wynik
end;
inc(i); //rozpatrz kolejny nominal
end;
ReadLn;
end.
Język C++ został stworzony w 1979r. przez Bjarne Stroustrupa.
#include <iostream>
#include <stdlib.h>
using namespace std;
int main(int argc, char *argv[])
{
//tablica dostepnych nominalow
int N[8]={200, 100, 50, 20, 10, 5, 2, 1};
int R,P, i;
cout << "Podaj reszte do wyplacenia: ";
cin >> R;
i=0;
while (R>0) //dopoki nie wydano calej reszty
{
if (R >= N[i]) //sprawdz czy mozna wydac danym nominalem
{
P=R / N[i]; //ile razy wydac dany nominal
R=R-(N[i]*P); //zmniejsz reszte o wydany nominal
cout << N[i] << " x " << P << endl; //wypisz wynik
}
i++; //rozpatrz kolejny nominal
}
system("PAUSE");
return 0;
}
