Strona główna » Algorytmy » Artykuły » Wydawanie reszty

Wydawanie reszty

Opis działania

Nasz algorytm przyjmie liczbę, która będzie oznaczała resztę, którą mamy wydać klientowi. Przy pomocy algorytmu wyznaczymy ile jakich nominałów użyć, aby wydać jak najmniej banknotów i monet. W celu ułatwienia sobie zadania przyjmujemy, że kwota do wydania jest podana w groszach. Dzięki temu będziemy mogli użyć do obliczeń funkcji modulo. Listą wartości odpowiednich nominałów będziemy przechowywać na liście uporządkowanej malejąco tzn. wartości będą maleć.

Przechodzą do algorytmu to po kolei dla każdej wartości na liście wartości nominałów będziemy sprawdzać ile razy mieści się w reszcie. Kwotę, którą już wydamy będziemy odejmować od kwoty do wydania - inaczej byśmy wydali klientowi zdecydowanie za dużo. Na koniec wypiszemy ile jakich dokładnie banknotów użyliśmy.

Implementacja

Przed rozpoczęciem pisania funkcji zadeklarujemy zmienną N, która będzie listą, która będzie zawierała wartości banknotów i monet. Wszystkie wartości będą podane w groszach, dlatego pierwszym element to 20000, bo 20000gr = 200zł:

  1.   int N []= {20000, 10000, 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5, 2, 1};

Nasza funkcja będzie przyjmować trzy argumenty: r - kwotę jaką należy wydać w groszach, listę N, która będzie zawierała wartości nominałów oraz argument dl, który będzie oznaczał ile elementów mamy na liście N. Na koniec zwrócimy listę, która będzie miała tyle samo elementów co N i na i-tym miejscu mamy ile i-tych banknotów / monet potrzebujemy.

  1. int* reszta (int r, int* N, int dl) {
  2.   int* wynik = new int[dl];
  3.   for(int i = 0; i < dl; i++){
  4.     wynik[i] = (int)(r / N[i]);
  5.     r -= wynik[i] * N[i];
  6.   }
  7.   return wynik;
  8. }

(2.) Deklarujemy listę wynikową, która będzie zawierać ile i jakich monet potrzebujemy. (3.) Dla każdej zarejestrowanej wartości nominały: (4.) wyliczamy ile takich banknotów / monet możemy wydać i wyciągamy część całkowitą, którą przypisujemy jako i-ty element do listy wynikowej. (5.) Zmniejszamy resztę o wydaną już kwotę. (7.) Zwracamy listę wynikową.

Kwota nie w groszach

Możemy przeciążyć funkcję reszta(), aby działała również dla wartości rzeczywistych tj. kiedy będziemy chcieli podać wartość w złotych zamiast groszach:

  1. int* reszta (double r, int* N, int dl) {
  2.   return reszta((int)(r * 100), N, dl);
  3. }

Od tej pory program sam prawidłowo skonwertuje podaną wartość do groszy. Zakładamy, że wartość całkowita to zawsze wartość w groszach.

Testowanie funkcji

Przykładowo funkcję możemy wykorzystać tak:

  1. int main () {
  2.   const int dl = 14;
  3.   int N []= {20000, 10000, 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5, 2, 1};
  4.   int* wynik = reszta(2016, &(N[0]), dl);
  5.   for(int i = 0; i < dl; i++)
  6.     if(wynik[i] != 0)
  7.       cout << wynik[i] << " x " << (double)(N[i]) / 100 << " PLN" << endl;
  8.   system("pause");
  9.   return 0;
  10. }

Inne systemy

Chcąc zmienić jakie mamy dostępne wartości nominałów wystarczy zmodyfikować linijki (2. - 3.) funkcji main(). Należy pamiętać, że aplikacja nie sprawdza na koniec czy faktycznie resztę można wydać - w każdym systemie pieniężnym można wydać "co do grosza". Jeśli jednak chcemy, aby sprawdzić czy resztę można wydać wystarczy sprawdzić czy na koniec wykonywania funkcji reszta() r == 0.

Zadania

Zadanie 1

Zmień fragment wypisujący jakie banknoty i monety powinny zostać wydane, aby wartości monet groszowych nie były wyświetlane jako ułamek dziesiętny. Podczas wypisywania zadbaj, aby wyświetlić kolejne wartości pod sobą w "kolumnach".

Przykładowo dla wprowadzonej przez użytkownika wartości 40020.99 program wypisze:

  1. 200 x 200 zl
  2. 1   x 20 zl
  3. 1   x 50 gr
  4. 2   x 20 gr
  5. 1   x 5 gr
  6. 2   x 2 gr