Jakas reklama 

 

 Ten artykuł wymaga dopracowania zgodnie z zaleceniami edycyjnymi.
Należy w nim poprawić: Usunięcie pierwszej osoby liczby mnogiej..
Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się na stronie dyskusji tego artykułu w sekcji Dopracować
Po wyeliminowaniu wskazanych powyżej niedoskonałości prosimy usunąć szablon {{Dopracować}} z kodu tego artykułu.

Problem wydawania reszty – zagadnienie z dziedziny algorytmiki, 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.

Przykładowe zadanie: dane są trzy nominały – 1 zł, 2 zł i 5 zł. Ile minimalnie monet potrzeba, by wydać 13 zł?

Poniżej pokazujemy dwa popularne rozwiązania tego problemu dla wariantu problemu, w którym zakłada się dostępność dowolnej ilości monet każdego nominału: jedno przy pomocy algorytmu zachłannego, drugie z wykorzystaniem programowania dynamicznego.

edytuj Algorytm zachłanny

Algorytm zachłanny jest poprawny dla tego problemu przy założeniu, że każda kwota, jaką trzeba wydać, oraz wszystkie dostępne nominały dzielą się bez reszty przez najmniejszy z dostępnych nominałów. Systemy monetarne w większości krajów (w tym w Polsce) są dostosowane tak, by ten warunek był zawsze spełniony, o ile są do dyspozycji wszystkie nominały będące w obrocie. Najmniejszym nominałem jest jeden grosz, a kwoty podaje się z dokładnością właśnie do jednego grosza. Jeśli w konkretnym zastosowaniu wszystkie kwoty wyrażają się w pełnych złotych albo z ułamkiem w dziesiątkach groszy, to odpowiednio najmniejszym niezbędnym nominałem będzie ich największy wspólny dzielnik – nominał 1 zł albo 10 gr.

Również podany powyżej przykład spełnia to założenie, bo zarówno wymagana kwota (13) i wszystkie dostępne nominały (1, 2, 5) są podzielne bez reszty przez najmniejszy z nominałów (1).

Algorytm odejmuje od zadanej kwoty największy spośród nominałów mniejszych i równych kwocie. Następnie, o ile kwota jest większa od zera, powtarza czynność. Liczba powtórzeń jest liczbą potrzebnych monet.

Dla powyższego przykładu algorytm zadziała następująco:

k – żądana kwota; wg przykładu 13; w każdym kroku pomniejszana o n
n – największy element zbioru nominałów mniejszy lub równy k
x – liczba potrzebnych monet; początkowo 0, w każdym kroku o 1 większa
k 13 8 3 1 0
n 5 5 2 1 -
x 1 2 3 4 -

Zaletą powyższego algorytmu jest szybkość i prostota implementacji. Algorytm zachłanny zapisany w C++ to zaledwie klika linijek:

    // k – zadana kwota, x=0 – wynik
    // N – zbior (tablica o długości l) nominalow
    while (k>0)                              // dopoki kwota wieksza od zera
    {
      int n=0;                                 // n – maksymalny nominal mniejszy lub rowny kwocie
      for (int i=0;i<l;++i)                    // wsrod wszystkich nominalow...
         if((Ni<=k)&&(Ni>n)) n=Ni;         // ...znajdz n
      k -= n;                                  // pomniejsz kwote o n
      ++x;                                     // zwieksz wynik o 1
    }

Analogiczny algorytm w Pascalu (funkcja mogłaby zajmować mniej linijek, ale jest rozpisana z myślą o przejrzystości):

type
Tnominaly: array 1..n of Integer;
 
{funkcja ilosc_monet zwraca najmniejszą liczbę monet potrzebnych, aby wydać zmienną
kwota typu Integer (uproszczenie dla skrócenia algorytmu) za pomocą nominałów 
których wartości są zawarte w tablicy nominaly typu Tnominaly (typ zadeklarowany powyżej).
n jest stałą oznaczającą długość tablicy.}
 
function ilosc_monet(kwota: Integer; nominaly: Tnominaly )
var
i, x: integer;       {deklaracja zmiennych - i  to iterator, a x - odpowiednik n z}
                     {powyższego przykładu}
begin
 
ilosc_monet:=0;
repeat
 
  i:=n;
 
  repeat
    x:=nominalyi;
    if x>kwota then           {znajdowanie x}
      i:=i-1;
  until kwota>=x;
 
  ilosc_monet:=ilosc_monet+1;
  kwota:=kwota-x;
 
until kwota=0;
 
end;

Wadą rozwiązania zachłannego jest brak możliwości wykorzystania w przypadku, gdy nominały mogą być tak dobrane, że nie zawsze znajdzie się nominał, przez który kwota dzieli się bez reszty. Przykładem jest sytuacja z życia codziennego: nominały w bankomatach to zwykle 20, 50, 100 i 200 zł. Algorytm zachłanny zastosowany przy takich nominałach dla kwoty 60 zł nie zadziałałby – w pierwszym kroku pomniejszyłby kwotę o 50 zł, pozostawiając 10 zł; tak mała kwota nie może być wydana przy użyciu w/w nominałów.

W bankomatach stosowany jest więc algorytm z wykorzystaniem programowania dynamicznego.

edytuj Algorytm z wykorzystaniem programowania dynamicznego

Dzięki wykorzystaniu programowania dynamicznego jest możliwe znalezienie bezbłędnego rozwiązania dla tego problemu przy dowolnym zbiorze nominałów i dowolnej kwocie. Algorytm polega na przetwarzaniu kolejnych nominałów i obliczeniu minimalnej liczby potrzebnych monet dla wydania kwot od 0 do k. Przy analizie kolejnego nominału wykorzystywane są informacje pozyskane w czasie wcześniejszych analiz. Jeśli nie będzie możliwe wydanie kwoty przy użyciu dostępnych nominałów, zostanie zwrócony wynik "nieskończoność".

Przebieg algorytmu:

Dla podanego na początku artykułu przykładu zadziała następująco:

n T
0 1 2 3 4 5 6 7 8 9 10 11 12 13
- 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
1 0 1 2 3 4 5 6 7 8 9 10 11 12 13
2 0 1 1 2 2 3 3 4 4 5 5 6 6 7
5 0 1 1 2 2 1 2 2 3 3 2 3 3 4

Przy odwrotnej kolejności wczytywania nominałów wyniki będą następujące:

n T
0 1 2 3 4 5 6 7 8 9 10 11 12 13
- 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
5 0 ∞ ∞ ∞ ∞ 1 ∞ ∞ ∞ ∞ 2 ∞ ∞ ∞
2 0 ∞ 1 ∞ 2 1 3 2 4 3 2 4 3 5
1 0 1 1 2 2 1 2 2 3 3 2 3 3 4

Taki algorytm jest bardziej uniwersalny, ale nieco trudniejszy w implementacji. Zapisany w C++, wygląda tak:

#define INFINITY 2147483647 // nieskończoność definiujemy umownie jako górny kres typu integer
   /* 
     ...
   */
   // a – liczba nominałów, k – żądana kwota
   int Tk+1;                  // utwórz tablicę T o zakresie od 0 do k
   T0 = 0;                    // dla kwoty 0 potrzebujesz 0 monet
   int i;
   for (i=1;i<=k;++i)           // dla każdej kwoty od 1 do k 
     Ti=INFINITY;             // potrzebujesz nieskończoność monet
   for (i=1;i<=a;++i)           // dla każdego nominału wykonuj:
   {
     int n;                     // n – aktualnie analizowany nominał
     cin >> n;                  // wczytaj nominał
     for (int j=0;j<=k-n;++j)   // dla j=0 do k-n wykonuj: 
       if (Tj < INFINITY)     // jeżeli T[j] już ma przypisaną wartość i jeżeli
         if (Tj+1 < Tj+n)   // dodanie monety zmniejszy liczbę monet dla kwoty j+n,
           Tj+n = Tj+1;     // to zapisz nową liczbę monet dla zwiększonej kwoty.
   }
TENERYFA szkoły policealne Katalog stron apteka internetowa Catering Warszawa