PROGRAMOWANIE – PRZYKŁADY
IDE C++ WinBGI C# Wpadki

Przykład C++

Wydawanie reszty Tablice jednowymiarowe Algorytm Program w Borland C++ Program w MinGW C++ Program w Visual C++ Poprzedni przykład Następny przykład Program w Visual C# Kontakt

Wydawanie reszty

Jednym z zagadnień algorytmiki jest problem wydawania reszty w sklepie lub wypła­cania kwoty w banku. Zazwyczaj klienci nie lubią otrzymywać zbyt wielu banknotów i monet, dlatego kasjer powinien złożyć żądaną kwotę przy użyciu jak najmniej­szej liczby nominałów. Zadaniem programu w języku C++ jest wczytanie nieujemnej liczby rzeczy­wistej wyraża­jącej kwotę i wyprowadzenie liczby banknotów i monet, z których ta kwota jest złożona. Na przykład dla liczby 145.74 prawi­dłowym wynikiem jest:

    100 zł: 1
     20 zł: 2
      5 zł: 1
     50 gr: 1
     20 gr: 1
      2 gr: 2

Tablice jednowymiarowe

Tablica jednowymiarowa jest w językach C i C++ ciągiem elementów tego samego typu o wspólnej nazwie. Elementy tablicy są ponume­rowane kolejnymi liczbami całkowitymi od zera wzwyż, zwanymi indeksami. W pamięci komputera elementy tablicy są ułożone jeden obok drugiego w kolejności wzrasta­jących indeksów, a dostęp do nich w programie odbywa się poprzez nazwę tablicy i podany w nawiasach kwadra­towych [] indeks. Na przykład instrukcja

double x[10];

definiuje tablicę o nazwie x, która ma 10 elementów x[0], x[1], ..., x[9]. Każdy z nich może przyj­mować wartość rzeczy­wistą typu double.

Zdarza się, że w programie potrzebna jest tablica o zadanych z góry warto­ściach elementów. Należy wówczas, bez precy­zowania rozmiaru tablicy, podać w nawiasach klamrowych {} tzw. listę inicjali­zacyjną określającą wartości wszystkich jej elementów. Na przykład instrukcja

int mc[] = {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

definiuje 12-elementową tablicę określającą, ile dni mają poszcze­gólne miesiące roku przestępnego: d[0] – styczeń ma 31 dni, d[1] – luty ma 29 dni, ..., d[11] – grudzień ma 31 dni (przyjęta w C i C++ numeracja elementów tablicy od 0 wzwyż narzuca nieco niefortunne numero­wanie miesięcy od 0 do 11).

Algorytm

Nominały wszytkich obecnie używanych banknotów i monet możemy zapamiętać w 15-elementowej tablicy liczb całko­witych wyraża­jących ich wartości w przeliczeniu na grosze:

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

Element Nom[0] tej tablicy oznacza banknot 500 zł, Nom[1] banknot 200 zł, ..., Nom[8] monetę 1 zł, Nom[9] monetę 50 gr, ..., Nom[14] monetę 1 gr. Algorytm, jaki się narzuca, polega na przeglą­daniu nominałów w kolejności od najwię­kszego do najmniej­szego i obli­czeniu dla każdego z nich, ile razy mieści się on w kwocie wyrażonej w groszach, wypi­saniu tego nomi­nału i wyli­czonej liczby jego wystą­pień na wyjściu oraz pomniej­szeniu tej kwoty o wartość wyli­czonej liczby nominałów:

n = Kwota / Nom[k];     // Liczba nominałów Nom[k]
...                     // Wypisz wartości Nom[k] i n
Kwota %= Nom[k];        // Kwota = Kwota - n * Nom[k];

(operator % określa operację modulo wyzna­czania reszty z dzielenia dwóch liczb całko­witych). Na początku wartością zmiennej Kwota jest przekształ­cona na liczbę groszy wczytana wartość rzeczy­wista zmiennej Reszta wyraża­jąca złotowo-groszową resztę do wydania (część całko­wita – złote, część ułamkowa – grosze). Powyższe instru­kcje należy wyko­nywać itera­cyjnie dla kolejnych indeksów k od zera wzwyż dopóty, dopóki pozo­stała jeszcze jakaś kwota do wydania:

Kwota = 100 * Reszta;        // Kwota do wypłacenia
for (k = 0; Kwota > 0; k++)
{
    n = Kwota / Nom[k];      // Liczba nominałów Nom[k]
    if (n > 0)
    {
        ...                  // Wypisz nominał Nom[k]
        ...                  // Wypisz n
        Kwota %= Nom[k];     // Kwota pozostała
    }
}

Zerowa wartość n oznacza, że nominał o wartości Nom[k] nie jest uwzglę­dniany w wypłacanej reszcie, dlatego jest pomijany na wyjściu.

Algorytm należy do grupy tzw. algorytmów zachłannych, które w każdym kroku dokonują wyboru roku­jącego w danym momencie najlepsze rozwią­zanie. Zachłanność algorytmu przejawia się w wyborze kolejnego najwyż­szego nieuwzglę­dnionego nominału. Optymal­ność rozwią­zania końcowego gwarantuje przyjęty system wartości nominałów. Gdyby jednak uwzględnić hipote­tyczną monetę o wartości 12 groszy, algorytm nie zawsze dawałby rozwią­zanie optymalne. Na przykład kwotę 15 groszy wyraziłby za pomocą trzech monet (12 gr + 2 gr + 1 gr), podczas gdy właściwe rozwią­zanie zawiera­łoby dwie monety (10 gr + 5 gr).

Program w Borland C++

Omówiony algorytm zachłanny wydawania reszty wykorzy­stamy teraz w programie konso­lowym używa­jącym bibliotek standar­dowych stdioconio. Definicję tablicy Nom umieścimy pomiędzy dyrekty­wani #include i nagłówkiem funkcji main. Będzie to wtedy tzw. zmienna globalna, która w przeciwieństwie do zmiennych lokalnych będzie dostępna od punktu jej definicji do końca programu, a nie tylko wewnątrz funkcji od punktu defi­nicji do końca bloku, w którym zosta­łaby zdefinio­wana. Blokiem lub instrukcją złożoną jest lista instrukcji ujęta w nawiasy {}.

Rozbudowę kodu źródłowego funkcji main rozpoczy­namy od umieszczenia definicji zmiennej Reszta typu doubleKwota typu int oraz operacji wczytania wartości pierwszej z tych zmiennych z klawiatury. Konwersja wczytanej liczby rzeczy­wistej określa­jącej kwotę w złotych (część całkowita) i groszach (część ułamkowa) na liczbę całko­witą wyrażającą równo­ważną kwotę w groszach:

Kwota = 100 * Reszta;

może prowadzić do błędnego wyniku. Dzieje się tak dlatego, że każdy, nawet bardzo mały przedział liczb rzeczy­wistych zawiera tych liczb nieskoń­czenie wiele, toteż większość z nich może zostać zapi­sana w pamięci kompu­tera tylko w sposób przybli­żony. Skutkiem wykony­wania działań arytmety­cznych na wartościach przybli­żonych, a przy większej liczbie cyfr znaczących nawet na dokładnych, są otrzymane wyniki obliczeń, które przybli­żają jedynie, z pewnym błędem, wyniki prawdziwe. I tak np. wynikiem powyższej konwersji kwoty 0.09 zł jest w przypadku rozpatry­wanego kompila­tora nieocze­kiwanie wartość 8 gr (więcej przykładów na stronie Wpadki). Liczba 0.09 jest bowiem w pamięci komputera repre­zentowana przez wartość zmiennopo­zycyjną z pewnym niedo­miarem, która po pomno­żeniu przez 100 daje wynik nieco mniejszy od 9.0, a po obcięciu części ułamkowej (niejawna konwersja wartości typu double na int) wynik 8. Problem można łatwo rozwiązać, zwiększając wartość przed obcięciem części ułamkowej:

Kwota = 100 * Reszta + 0.5;

Przejdźmy jeszcze do sprecyzowania formatu wyniku obliczeń. Z algorytmu wynika, że na wyjściu zostanie wypisana lista nominałów wraz z liczbami ich wystą­pień. Warto zadbać o to, by infor­macja o nominale miała postać ogólnie przyjętą, określa­jącą jego wysokość i specyfikację, czy jest to nominał złotowy, czy groszowy:

if (Nom[k] >= 100)
    ...         // Wypisz Nom[k]/100 zł
else
    ...         // Wypisz Nom[k] gr

Ostatecznie otrzymujemy następujący kod źródłowy programu:

#include <stdio.h>
#include <conio.h>

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

int main()
{
    double Reszta;
    printf("Reszta do wydania: ");
    scanf("%lf", &Reszta);
    printf("----------------------------\n");
    int Kwota = 100 * Reszta + 0.5;
    for (int k = 0; Kwota > 0; k++)
    {
        int n = Kwota / Nom[k];
        if (n > 0)
        {
            if (Nom[k] >= 100)
                printf("%3d zl: ", Nom[k] / 100);
            else
                printf("%3d gr: ", Nom[k]);
            printf("%d\n", n);
            Kwota %= Nom[k];
        }
    }
    printf("----------------------------\n");
    _getch();
    return 0;
}

Być może wyjaśnienia wymagają definicje zmiennych lokalnych Kwota, kn, a właściwie ich lokali­zacja w kodzie programu. W języku C zmienne lokalne można definiować tylko na początku bloku, natomiast w C++ w dowolnym jego miejscu, a nawet w nagłówku pętli for. W rozpatrywanym przypadku zmienna Kwota definio­wana jest po wczytaniu danej, dzięki temu wraz z przydziałem pamięci można jej przypisać stosowną wartość. Jej zasięg (dostęp do niej) rozciąga się od punktu defi­nicji do końca funkcji main. Z kolei zmienna k jest definio­wana w nagłówku pętli for, przy czym od razu przypisana jej zostaje wartość zero. Zasięgiem tej zmiennej jest nagłówek pętli for i wnętrze objętego nią bloku. Zmienna n zdefinio­wana jest na początku tego bloku, więc jest dostępna w całym jego wnętrzu.

W drugiej wersji programu zamiast standardowej biblio­teki stdio języka C użyjemy standar­dowej biblio­teki iostream języka C++. Aby program zadziałał identy­cznie jak w wersji pierwszej, należy określić, że wysokość nominału ma na wyjściu zajmować pole o szerokości trzech znaków. W tym celu posłużymy się manipu­latorem setw, który ustawia szero­kość pola dla następnej w kolejności wyprowa­dzanej wartości. Manipu­lator ten, jak większość manipu­latorów, jest zdefi­niowany w bibliotece iomanip. Oto kompletny kod źródłowy programu korzysta­jącego ze strumie­niowego wejścia-wyjścia C++:

#include <iostream>
#include <iomanip>
#include <conio.h>

using namespace std;

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

int main()
{
    double Reszta;
    cout << "Reszta do wydania: ";
    cin >> Reszta;
    cout << "----------------------------\n";
    int Kwota = 100 * Reszta + 0.5;
    for (int k = 0; Kwota > 0; k++)
    {
        int n = Kwota / Nom[k];
        if (n > 0)
        {
            if (Nom[k] >= 100)
                cout << setw(3) << Nom[k] / 100 << " zl: ";
            else
                cout << setw(3) << Nom[k] << " gr: ";
            cout << n << endl;
            Kwota %= Nom[k];
        }
    }
    cout << "----------------------------\n";
    _getch();
    return 0;
}

Program w MinGW C++

W przypadku kompilatora MinGW C++ konwersja wczytywanej z klawiatury wartości typu double określa­jącej kwotę złotowo-groszową na wartość typu int reprezen­tującej tę samą kwotę w groszach wymaga, tak jak poprzednio, szczególnej uwagi. W programie można jedynie zrezy­gnować z funkcji _getch i biblioteki conio, ponieważ środo­wisko Code::Block nie zamyka okna konsoli po zakończeniu jego wyko­nania. Pierwsza wersja rozpatry­wanego programu, używająca biblio­teki stdio, może więc mieć następu­jącą postać:

#include <stdio.h>

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

int main()
{
    double Reszta;
    printf("Reszta do wydania: ");
    scanf("%lf", &Reszta);
    printf("----------------------------\n");
    int Kwota = 100 * Reszta + 0.5;
    for (int k = 0; Kwota > 0; k++)
    {
        int n = Kwota / Nom[k];
        if (n > 0)
        {
            if (Nom[k] >= 100)
                printf("%3d zl: ", Nom[k] / 100);
            else
                printf("%3d gr: ", Nom[k]);
            printf("%d\n", n);
            Kwota %= Nom[k];
        }
    }
    printf("----------------------------\n");
    return 0;
}

A oto druga wersja programu dla kompilatora MinGW C++ rozwią­zująca problem wyda­wania reszty w sklepie lub wypła­cania kwoty w banku używa­jąca biblio­teki iostream zamiast stdio:

#include <iostream>
#include <iomanip>

using namespace std;

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

int main()
{
    double Reszta;
    cout << "Reszta do wydania: ";
    cin >> Reszta;
    cout << "----------------------------\n";
    int Kwota = 100 * Reszta + 0.5;
    for (int k = 0; Kwota > 0; k++)
    {
        int n = Kwota / Nom[k];
        if (n > 0)
        {
            if (Nom[k] >= 100)
                cout << setw(3) << Nom[k] / 100 << " zl: ";
            else
                cout << setw(3) << Nom[k] << " gr: ";
            cout << n << endl;
            Kwota %= Nom[k];
        }
    }
    cout << "----------------------------\n";
    return 0;
}

Program w Visual C++

Środowisko Visual Studio C++ uruchamia program wynikowy we własnej konsoli i zatrzymuje ją po jego wykonaniu, ocze­kując na naci­śnięcie dowolnego klawisza. Dlatego rozsądne wydaje się skopio­wanie kodu źródło­wego programu z edytora środowiska kompi­latora MinGW C++. Oczywiście w ustawie­niach właści­wości nowego projektu rezy­gnujemy z prekompi­lowanego nagłówka i usuwamy pliki stdafx.h, stdafx.cpptargetver.h (lub pch.hpch.cpp). Rezy­gnujemy również z korekty konwerto­wanej wartości rzeczy­wistej określa­jącej kwotę złotowo-groszową na wartość całkowitą wyrażają tę samą kwotę w groszach, która w przypadku tego kompi­latora wydaje się zbyteczna. Próba kompilacji uzyskanej w ten sposób pierwszej wersji programu wyda­wania reszty używa­jącego standar­dowej w C biblio­teki wejścia-wyjścia kończy się jednak niepowo­dzeniem (rys.).

Kompilator Visual C++ traktuje funkcję scanf jako potencjalnie niebezpie­czną i przeciwstawia się jej użyciu (błąd C4996, wiersz 12), propo­nując skorzy­stanie z jej nowszego odpowie­dnika scanf_s lub wyłą­czenie zabezpieczeń przed używaniem przesta­rzałych funkcji lub zmiennych. Ostrzega również przed niejawną konwersją wartości typu double na int (ostrze­żenie C4244, wiersz 14), która może prowadzić do utraty danych. Błąd elimi­nujemy, zastę­pując funkcję scanf funkcją scanf_s, natomiast ostrze­żenie możemy zigno­rować, gdyż utrata dokła­dności polega w tym przypadku na obcięciu części ułam­kowej, co jest akurat operacją pożądaną.

W gruncie rzeczy ignorowanie ostrzeżeń nie należy do dobrych zwyczajów programo­wania, gdyż może prowadzić do uśpienia czujności i w dalszej kolej­ności do niepopra­wnego działania programu. Używając jawnej konwersji, unikniemy ostrze­żenia. Mamy do wyboru dowolną z dwu notacji:

tradycyjna (int)x rzutowanie w stylu języka C
funkcyjna int(x) konwersja w stylu języka C++

Wydaje się, że notacja funkcyjna jest lepsza, aczkolwiek w języku C# pozosta­wiono tylko trady­cyjną. Pierwsza wersja programu wydawania reszty, używa­jąca tej notacji i biblio­teki stdio, może wyglą­dać następująco:

#include <stdio.h>

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

int main()
{
    double Reszta;
    printf("Reszta do wydania: ");
    scanf_s("%lf", &Reszta);
    printf("----------------------------\n");
    int Kwota = int(100 * Reszta);
    for (int k = 0; Kwota > 0; k++)
    {
        int n = Kwota / Nom[k];
        if (n > 0)
        {
            if (Nom[k] >= 100)
                printf("%3d zl: ", Nom[k] / 100);
            else
                printf("%3d gr: ", Nom[k]);
            printf("%d\n", n);
            Kwota %= Nom[k];
        }
    }
    printf("----------------------------\n");
    return 0;
}

W oknie konsoli stosowana jest strona kodowa CP852, na której polska litera ł ma kod dziesiętny 136 zapisy­wany w systemie szesna­stkowym jako 0x88. W językach C i C++ można ją zapisać w postaci znaku '\x88', a symbol polskiej waluty w postaci łańcucha "z\x88". Zatem druga wersja programu dla kompi­latora Visual C++ rozwią­zująca problem wyda­wania reszty w sklepie lub wypła­cania kwoty w banku używa­jąca biblio­teki iostream zamiast stdio może wyglądać następująco:

#include <iostream>
#include <iomanip>

using namespace std;

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

int main()
{
    double Reszta;
    cout << "Reszta do wydania: ";
    cin >> Reszta;
    cout << "----------------------------\n";
    int Kwota = int(100 * Reszta);
    for (int k = 0; Kwota > 0; k++)
    {
        int n = Kwota / Nom[k];
        if (n > 0)
        {
            if (Nom[k] >= 100)
                cout << setw(3) << Nom[k] / 100 << " z\x88: ";
            else
                cout << setw(3) << Nom[k] << " gr: ";
            cout << n << endl;
            Kwota %= Nom[k];
        }
    }
    cout << "----------------------------\n";
    return 0;
}

A oto przykładowe wyniki obliczeń programu:

Opracowanie przykładu: lipiec 2018