Problem wydawania reszty

Problem wydawania reszty to znane zagadnienie algorytmiczne. Polega ono na znalezieniu takiej konfiguracji monet, aby reszta, którą musimy wydać, była wydana jak najmniejszą ilością monet. Jest to zagadnienie obowiązujące na maturze z informatyki.

Problem wydawania reszty

Problem wydawania reszty jest problemem optymalizacyjnym. Oznacza to, że z grupy wielu dostępnych rozwiązań należy znaleźć takie, które będzie najbardziej optymalne. Co będziemy optymalizować? Oczywiście ilość monet, za pomocą których wydamy resztę.

Przykład

Chcemy wydać resztę wynoszącą 6zł za pomocą dostępnych monet: 1zł, 2zł oraz 5zł. Możliwe rozwiązania to np.:

Oczywiście rozwiązaniem najbardziej optymalnym jest 5zł + 1zł, ponieważ użyjemy tylko dwóch monet, a właśnie ich ilość chcemy optymalizować.

Istnieje wiele sposobów na rozwiązanie tego zagadnienia. Na maturze z informatyki musisz umieć rozwiązać problem wydawania reszty metodą zachłanną.

Algorytmy zachłanne

Algorytmy zachłanne polegają na tym, że wybierają takie rozwiązanie, które jest w danej chwili wykonania najbardziej optymalne. Wyobraźmy sobie, że napisaliśmy grę, a bohater musi umieć wybrać jedno z możliwych rozwiązań, takie aby najbardziej się wzbogacić.

W algorytmie zachłannym bohater wybierze kwotę 100zł, ponieważ jest większa niż 50zł. Algorytm nie zwraca uwagi na to, że ostatecznie kwota jaką wybierze zachłannie w danej chwili czasu będzie ostatecznie gorsza od rozwiązania optymalnego.

Algorytm wydawania reszty

W algorytmie zachłannym wydawania reszty tworzymy pętle, która będzie wykonywać się dopóki kwota do wydania jest większa od zera. Przy każdym obiegu pętli odejmujemy od kwoty do wydania największy możliwy nominał, którym dysponujemy, i który jednocześnie nie spowoduje, że wydamy zbyt dużą resztą.

Spójrzmy na przykład z poprzedniego akapitu: Mamy do wydania 6zł posiadając monety 1zł, 2zł i 5zł:

Jak widać na obrazku, w prosty sposób wyznaczyliśmy dwie monety, którymi najszybciej można wydać kwotę 6zł.

Istnieją pewne przypadki, kiedy algorytm zachłanny nie wyda reszty w prawidłowy sposób, jednak stałoby się tak w przypadku użycia niestandardowych nominałów monet (np. wprowadzanie money 7zł). Obecnie wszystkie systemy monetarne są tworzone tak, że algorytm zachłanny zadziała.

Kod programu w C++

Kod programu C++ zwracający ilość monet do wydania określonej reszty wygląda następująco:

#include <iostream>

using namespace std;

int main()
{
    int iloscMonet = 3;
    int monety[iloscMonet] = { 1, 2, 5};
    int reszta = 0;

    cout << "Jaka reszte chcesz wydac?" << endl;
    cin >> reszta;

    int licznik = 0;

    while (reszta > 0)
    {
        int nominal = 0;
        for (int i = 0; i < iloscMonet; ++i)
        {
            if ((monety[i] <= reszta) && (monety[i] > nominal))
            {
                nominal = monety[i];
            }
        }
        reszta = reszta - nominal;
        licznik++;
    }

    cout << "Reszte mozna wydac " << licznik << " monetami " << endl;

    system("PAUSE >nul");
    return 0;
}

Gdybyś chciał zapisać także historię monet, które wypłacamy, można dodać pomocniczą tablicę i je tam zapisywać:

#include <iostream>

using namespace std;

int main()
{
    int iloscMonet = 3;
    int monety[iloscMonet] = { 1, 2, 5};
    int reszta = 0;

    int historia[9999];

    cout << "Jaka reszte chcesz wydac?" << endl;
    cin >> reszta;

    int licznik = 0;

    while (reszta > 0)
    {
        int nominal = 0;
        for (int i = 0; i < iloscMonet; ++i)
        {
            if ((monety[i] <= reszta) && (monety[i] > nominal))
            {
                nominal = monety[i];
            }
        }
        reszta = reszta - nominal;
        historia[licznik] = nominal;
        licznik++;
    }

    cout << "Reszte mozna wydac " << licznik << " monetami " << endl;
    cout << "Uzyte monety: ";

    for (int i = 0; i < licznik; ++i)
    {
        cout << historia[i] << "zl, ";
    }

    system("PAUSE >nul");
    return 0;
}

Rozkład liczby na czynniki pierwsze

Znajdowanie najmniejszego i największego elementu

Sprawdzanie wielkości litery