Problem kasjera - wydawanie reszty

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;
}