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

Przykład C++

Zapis liczby w notacji rzymskiej Łańcuchy C i C++ 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

Zapis liczby w notacji rzymskiej

Zadaniem programu konsolowego w języku C++ jest wczytanie z klawiatury dodatniej liczby całko­witej i wygenerowanie jej notacji rzymskiej. Jak powsze­chnie wiadomo, w systemie rzymskim do zapisu liczb używa się siedmiu symboli lite­rowych, którym przypisane są wybrane liczby całkowite, które nazwiemy wagami:

    I     1
    V     5
    X     10
    L     50
    C     100
    D     500
    M     1000

Ciąg takich symboli reprezentuje liczbę równą sumie odpowia­dających im wag, np. MMXVIII oznacza liczbę 2018 (1000 + 1000 + 10 + 5 + 1 + 1 + 1). Ogólna reguła zapisu liczb w notacji rzymskiej orzeka, że symbol o wadze niższej nie może wystąpić przed symbolem o wadze wyższej. Wyjątkiem są jednak symbole I, X i C, które mogą wystę­pować przed niektó­rymi symbolami o wyższych wagach, a wtedy ich wagi są odejmo­wane. Dokładniej, poprawne są następu­jące symbole dwuliterowe i ich wagi:

    IV     4
    IX     9
    XL     40
    XC     90
    CD     400
    CM     900

Na przykład MCDXLIV oznacza liczbę 1444 (1000 + 400 + 40 + 4). Obowią­zuje również reguła, że zapis powinien zawierać jak najmniejszą liczbę znaków, np. liczba 9 powinna być zapisana jako IX, nie zaś jako VIIII lub VIV.

Łańcuchy C i C++

Do przechowywania łańcucha w stylu języka C służy tablica znaków, której kolejne elementy zawie­rają wartości typu char, czyli 1-bajtowe liczby całkowite repre­zentujące 8-bitowe znaki. Symbolem końca łańcucha jest znak specja­lny '\0' o kodzie 0. Na przy­kład w wyniku wyko­nania kodu

#include <string.h>
...
char s[10];
strcpy(s, "Ala i As");

zostanie utworzona 10-znakowa tablica, do której zostanie skopio­wanych 8 znaków Ala i As i znak końcowy '\0' (rys.). Funkcja strcpy, kopiu­jąca łańcuch znaków okre­ślony w drugim argu­mencie do tablicy doce­lowej podanej w pierwszym argu­mencie, jest jedną z wielu funkcji biblio­teki standar­dowej string operu­jących na tablicach łańcu­chowych.

Stała łańcuchowa jest w językach C i C++ traktowana jako wskaźnik (adres pamięci) na pierwszy znak ciągu znaków reprezen­towany przez tę stałą. Na przy­kład instrukcja

char *p = "Ala i As";

powoduje, że gdzieś w pamięci przydzielonej programowi zostaje umieszczony ciąg znaków Ala i As zakoń­czony znakiem '\0', a zmiennej p przypi­sany zostaje wska­źnik na pierwszy znak tego ciągu (litera A). Cieka­wostką może wydawać się, że nazwa tablicy jest trakto­wana jako wskaźnik na jej począ­tkowy element. Skutkiem tego powyższa instru­kcja jest równo­ważna instrukcji

char p[] = "Ala i As";

W języku C++ można również do przechowywania ciągu znaków i manipulowania nimi korzystać z klasy string. Nazwa klasy wystę­puje wtedy w roli nazwy typu, do znaków można odwo­ływać się jak do elementów tablicy, można używać trady­cyjnych opera­torów do porówny­wania łańcuchów, ich doda­wania (łączenia) i przypi­sywania. Dostępnych jest też wiele użyte­cznych metod opero­wania na ciągach znaków, m.in.

empty Zwraca true, gdy łańcuch jest pusty, false w przeciwnym razie
size, length Długość (liczba znaków) łańcucha
at Znak o określonym indeksie (jak [])
clear Usuwa wszystkie znaki łańcucha
erase Usuwa wybrane znaki łańcucha
find Znajduje określony ciąg znaków w łańcuchu
swap Zamienia miejscami dwa łańcuchy
substr Zwraca podłańcuch na podstawie indeksu początkowego i długości podłańcucha
c_str Zwraca łańcuch w stylu języka C (wskaźnik typu const char*)

Na przykład w wyniku wykonania instrukcji

#include <string>
using namespace std;
...
string s = "Ala i As";
string t = s.substr(0,4) + "ma kota";

wartością zmiennej t jest łańcuch Ala ma kota.

Algorytm

Wszystkie symbole rzymskie i ich wagi mogą być reprezento­wane przez dwie 13-elementowe tablice jednowy­miarowe uporządkowane w kolejności od najwię­kszej do najmniej­szej wagi:

char *Symbol[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

int Waga[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};

Elementami tablicy Symbol są stałe łańcu­chowe w stylu języka C, czyli ciągi znaków zakoń­czone znakiem o kodzie zero. Na przykład warto­ścią elementu Symbol[5] jest "XC".

Korzystając z uporządkowania obu tablic, można łatwo wygene­rować zapis rzymski wczytanej z klawiatury dodatniej liczby całkowitej n. Algorytm polega na przebie­ganiu w pętli for kolejnych symboli, poczy­nając od M, i sprawdzaniu, czy rozpatry­wany symbol ma być uwzglę­dniony w zapisie n:

for (int r = 0; n > 0; )
    if (n >= Waga[r])   // Symbol uwzględniany w zapisie n
    {
        ...             // Wypisz Symbol[r]
        n -= Waga[r];
    }
    else                // Przejście do następnego symbolu
        r++;

Jeżeli waga symbolu nie przekracza wartości n, należy go wysłać na wyjście i zmniejszyć wartość n o tę wagę, w przeciwnym razie należy przejść do nastę­pnego symbolu. Zerowa wartość n oznacza, że genero­wanie notacji rzym­skiej liczby zostało zakończone.

Zauważmy, że składnia instrukcji for pozwoliła na wyrażenia modyfiku­jącego, które – gdy istnieje – jest obli­czane po każdym kroku pętli. Właściwie to zostało ono przenie­sione do części else instru­kcji warun­kowej if opisu­jącej krok pętli, bowiem r++ powo­duje przejście do nastę­pnego symbolu, gdy rozpatry­wany symbol nie może być uwzglę­dniony. Podobnie jak w przypadku wyda­wania reszty, algorytm należy do grupy algo­rytmów zachłan­nych, które w każdym kroku dokonują wyboru rokują­cego najle­psze rozwiązanie.

Program w Borland C++

Kod źródłowy programu konsolowego generowania notacji rzymskiej liczby całko­witej używają­cego bibliotek standar­dowych stdioconio, w którym zasto­sowano omówiony wyżej algorytm zachłanny, może wyglądać następująco:

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

char *Symbol[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

int Waga[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};

int main()
{
    int n;
    printf("Liczba calkowita dodatnia: ");
    scanf("%d", &n);
    printf("Postac rzymska liczby %d: ", n);
    for (int r = 0; n > 0; )
        if (n >= Waga[r])
        {
            printf("%s", Symbol[r]);
            n -= Waga[r];
        }
        else
            r++;
    printf("\n");
    _getch();
    return 0;
}

W drugiej wersji programu zamiast standardowej biblio­teki stdio języka C użyjemy standar­dowej biblio­teki iostream języka C++. Ponadto zamiast trady­cyjnych w C stałych łańcu­chowych w postaci ciągów znaków zakoń­czonych znakiem o kodzie zero skorzy­stamy z łańcuchów C++ klasy string, a dokładniej, z tablicy elemen­tów tej klasy. Oto komple­tny kod źródłowy tego programu:

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

using namespace std;

string Symbol[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

int Waga[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};

int main()
{
    int n;
    cout << "Liczba calkowita dodatnia: "
    cin >> n;
    cout << "Postac rzymska liczby " << n << ": ";
    for (int r = 0; n > 0; )
        if (n >= Waga[r])
        {
            cout << Symbol[r];
            n -= Waga[r];
        }
        else
            r++;
    cout << endl;
    _getch();
    return 0;
}

W kodzie programu nie ma dyrektywy #include włączającej plik nagłówkowy biblio­teki string niezbę­dnej przy obsłudze łańcu­chów w stylu języka C++, ponieważ włącza go plik nagłówkowy biblio­teki iostream.

Program w MinGW C++

Kod źródłowy pierwszej wersji programu konsolowego generującego zapis rzymski liczby i używającego biblio­teki standar­dowej stdio jest niemal taki sam jak kod jego odpowie­dnika opraco­wanego dla kompi­latora Borland C++. Nie ma jedynie potrzeby bloko­wania zamknięcia okna konsoli na końcu wykonania programu, możemy więc zrezy­gnować z biblioteki conio i funkcji _getch. Kompi­lator ma jednak zastrze­żenia, traktując konwersje stałych łańcu­chowych typu string na char* jako przesta­rzałe (rys.). Chociaż program wynikowy działa poprawnie, warto pokusić się, by nie stawiać kompi­latora przed dyle­matem wyboru rozwią­zania, gdyż mogłoby ono okazać się niesatysfa­kcjonujące. Progra­mista zawsze powinien zwracać uwagę na ostrze­żenia kompi­latora i starać się je wyeliminować.

Komunikaty kompilatora MinGW C++ mogą wydawać się enigmatyczne. Na szczęście z pomocą przychodzi kompi­lator Visual C++, pomimo że jest bardziej rygory­styczny i interpretuje usterkę jako błąd (rys.). Jego komuni­katy informują, że nie można konwer­tować łańcu­chów typu const char[] na char* (wiersz 6).

Przyczyną niepowodzenia jest niezgo­dność typu elementów tablicy Symbol z typem elementów jej listy inicjali­zacyjnej:

Błąd jest łatwy do usunięcia, gdy zauważymy, że typy char*char[] są równo­ważne. Wystarczy zatem w defi­nicji tablicy Symbol dodać słowo kluczowe const, które oznacza, że nie można w trakcie działa­nia programu zmieniać wartości jej elemen­tów, czyli że są one stałe. Oto osta­teczna wersja tego programu:

#include <stdio.h>

const char *Symbol[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

int Waga[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};

int main()
{
    int n;
    printf("Liczba calkowita dodatnia: ");
    scanf("%d", &n);
    printf("Postac rzymska liczby %d: ", n);
    for (int r = 0; n > 0; )
        if (n >= Waga[r])
        {
            printf("%s", Symbol[r]);
            n -= Waga[r];
        }
        else
            r++;
    printf("\n");
    return 0;
}

A oto druga wersja programu dla kompilatora MinGW C++ generu­jąca notację rzymską wczyty­wanej z klawiatury dodatniej liczby całko­witej używa­jąca biblio­teki iostream zamiast stdio i łańcuchów w stylu języka C++ zamiast tablic znaków języka C:

#include <iostream>

using namespace std;

string Symbol[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

int Waga[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};

int main()
{
    int n;
    cout << "Liczba calkowita dodatnia: "
    cin >> n;
    cout << "Postac rzymska liczby " << n << ": ";
    for (int r = 0; n > 0; )
        if (n >= Waga[r])
        {
            cout << Symbol[r];
            n -= Waga[r];
        }
        else
            r++;
    cout << endl;
    return 0;
}

Program w Visual C++

Pierwsza wersja programu generowania notacji rzymskiej liczby całko­witej dla Visual C++, używa­jąca biblio­teki stdio i łańcuchów w stylu języka C, jest iden­tyczna jak dla kompi­latora MinGW C++, oczywiście gdy w jej projekcie zrezy­gnujemy z prekompilo­wanego nagłówka i plików stdafx.h, stdafx.cpptargetver.h (lub pch.hpch.cpp). Jedyną modyfi­kacją jest zastą­pienie przesta­rzałej funkcji scanf funkcją scanf_s. Warto przy okazji zadbać, by komunikacja z użytkownikiem odbywała się w języku polskim, co w przypadku strony kodowej CP852 okna konso­lowego wymaga użycia znaku '\x88' dla litery ł'\x86' dla ć. Rozwa­żania te prowadzą do następu­jącego kodu źródłowego:

#include <stdio.h>

const char *Symbol[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

int Waga[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};

int main()
{
    int n;
    printf("Liczba ca\x88kowita dodatnia: ");
    scanf_s("%d", &n);
    printf("Posta\x86 rzymska liczby %d: ", n);
    for (int r = 0; n > 0; )
        if (n >= Waga[r])
        {
            printf("%s", Symbol[r]);
            n -= Waga[r];
        }
        else
            r++;
    printf("\n");
}

A oto przykładowy wynik obliczeń tego programu:

Druga wersja programu konwersji liczby całkowitej z notacji dziesiętnej na rzymską, przenie­siona z kompilatora MinGW C++ do Visual C++ i używająca biblio­teki iostream zamiast stdio i łańcuchów w stylu języka C++, nie daje się skompi­lować (rys.). Przyczyną niepowo­dzenia są trudności z wyprowa­dzaniem elementów tablicy Symbol do stru­mienia cout (w przypadku kompila­torów Borland C++ i MinGW C++ problem nie istniał).

Błąd eliminujemy, włączając do kodu źródłowego programu plik nagłów­kowy biblio­teki string. Ostate­czna wersja programu po uwzglę­dnieniu polskich znaków wygląda następująco:

#include <iostream>
#include <string>

using namespace std;

string Symbol[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

int Waga[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};

int main()
{
    int n;
    cout << "Liczba ca\x88kowita dodatnia: "
    cin >> n;
    cout << "Posta\x86 rzymska liczby " << n << ": ";
    for (int r = 0; n > 0; )
        if (n >= Waga[r])
        {
            cout << Symbol[r];
            n -= Waga[r];
        }
        else
            r++;
    cout << endl;
    return 0;
}

Wypada na koniec zwrócić uwagę, że program nie generuje notacji rzymskiej liczb mniej­szych lub rówych zero. Taka konwersja nie miałaby sensu, ponieważ Rzymianie nie znali liczb ujemnych ani zera. Nie mniej jednak program mógłby poinfor­mować o zaistniałej sytuacji wyją­tkowej zamiast ją zignorować.


Opracowanie przykładu: lipiec 2018