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

Przykład C++

Rozwinięcie dziesiętne ułamka Algorytm Program w C++ (lista jednokierunkowa) Program w C++ (wektor struktur) Program w C++ (wektor obiektów) Poprzedni przykład Następny przykład Program w Visual C# Kontakt

Rozwinięcie dziesiętne ułamka

Zadaniem programu jest wczytanie z klawia­tury dwóch liczb całko­witych określa­jących licznik i miano­wnik ułamka, znale­zienie ciągu cyfr jego rozwi­nięcia dziesię­tnego i wypisanie uzyska­nego wyniku na monitorze. Na przykład dla danych 23 i 4 prawi­dłowym wynikiem jest ciąg znaków 5.75 (rozwi­nięcie skończone), a dla 23 i 14 ciąg 1.6(428571) reprezen­tujący ułamek okresowy (rozwi­nięcie nieskoń­czone).

Algorytm

Bez szkody dla ogólności rozważań możemy założyć, że licznik x ułamka jest liczbą nieujemną, a mianownik y liczbą dodatnią. Ułamek można wtedy wyrazić za pomocą wzoru:

w którym c jest liczbą całkowitą, a d1,d2,... są współczyn­nikami od 0 do 9 stano­wiącymi numery­czny odpowie­dnik cyfr rozwi­nięcia dziesię­tnego ułamka właści­wego. Po wydzie­leniu części całko­witej c współczyn­niki te dają się wyznaczać kolejno poprzez mnożenie licznika ułamka przez 10 i dzielenie całkowite uzyska­nego iloczynu przez mianownik. Otrzymany iloraz stanowi wartość cyfrową kolejnego współczy­nnika dk, zaś reszta nowy licznik ułamka w następnym kroku. Jeżeli reszta jest równa zero, ułamek ma rozwi­nięcie skończone, natomiast gdy powtórzy się, ułamek jest okresowy. Działanie algorytmu ilustrują poniższe dwa przykłady:

Wyznaczanie kolejnego współczynnika można w języku C++ wyrazić następuj­ąco:

d[k] = (x *= 10) / y;   // Kolejny współczynnik
x %= y;                 // Kolejny licznik (reszta)

Jak widać, algorytm prowadzi do wyznaczania tablicy liczb całko­witych. Nie wiemy jednak, ile ma ona elementów, dlatego bardziej odpowie­dnią implemen­tacją ciągu obliczanych w programie współczyn­ników rozwi­nięcia dziesię­tnego ułamka jest lista jednokie­runkowa lub wektor.

Program w C++ (lista jednokierunkowa)

Elementy listy jednokierunkowej używanej w pro­gramie znajdo­wania rozwi­nięcia dziesię­tnego ułamka zawierają po trzy składniki: numery­czny odpowie­dnik kolejnej cyfry dziesię­tnej, licznik ułamka rozpatry­wanego przy wyznaczaniu tej wartości cyfrowej i wska­źnik na następny element listy:

struct Element
{
    char cyfra;         // Wartość cyfrowa (0 - 9)
    int licznik;        // Licznik ułamka (reszta)
    Element *nast;      // Następny element listy
} *poc = NULL, *okr;    // Początek listy i okresu

Zadeklarowana zmienna poc o wartości NULL określa początek wstępnie pustej listy, a okr element zawiera­jący pierwszą cyfrę okresu. Sprawdzenie, czy licznik x występuje w liście, czyli czy ułamek jest okresowy, można zaprogra­mować nastę­pująco:

bool ulamek_okresowy(int x)
{
    for (okr = poc; okr != NULL && okr->licznik != x; okr = okr->nast)
        ;
    return okr != NULL;
}

Wskaźnik okr przebiega wzdłuż listy aż do momentu, gdy uzyska wartość NULL lub wskaże na element, którego pole licznik jest równe liczni­kowi x ułamka określonemu w argu­mencie funkcji. Jej wartością zwrotną jest false, gdy licznik nie występuje w liście, a true, gdy ułamek jest okresowy. Efektem ubocznym działania funkcji jest nadanie wartości zmiennej nielo­kalnej okr. Takie rozwią­zanie ułatwia genero­wanie listy. Generalnie jednak efektów ubocznych należy unikać, ponieważ zaburzają strukturę programu, zmniej­szają czytelność i utru­dniają analizę jego kodu.

Przejdźmy do operacji generowania listy reprezen­tującej rozwi­nięcie dziesiętne ułamka. Nowe elementy powinny być dołączane do niej nie na początku, jak np. w programie implemen­tującym sito Eratostenesa, lecz na końcu. Oczywiście koniec listy można znajdować za każdym razem, przeglądając ją sekwen­cyjnie, lepiej jednak użyć odrębnego wskaźnika wskazu­jącego zawsze na ostatni element. W poniższej funkcji zadekla­rowano dwa wskaźniki o nazwach pkon. Pierwszy wskazuje na nowy, wstawiany do listy element, a drugi właśnie na jej koniec.

void rozwin_ulamek(int x, int y)
{
    Element *p, *kon = NULL;
    for ( ; x != 0 && !ulamek_okresowy(x); x %= y)
    {
        (p = new Element)->licznik = x;
        p->cyfra = (x *= 10) / y;
        if (kon != NULL)
            kon->nast = p;
        else
            poc = p;
        (kon = p)->nast = NULL;
    }
}

Na początku, gdy lista jest pusta, wartością zmiennej kon jest NULL. W pętli for niemającej wyra­żenia inicju­jącego i wykony­wanej, gdy licznik ułamka jest różny od zera i nie występuje w liście, tworzony jest nowy element, w którym zapamię­tany zostaje licznik ułamka i wartość kolejnej cyfry dziesię­tnej. Gdy lista nie jest pusta, element ten zostaje dołączony na jej końcu (rys. poniżej u góry), a gdy jest pusta, staje się jej jedynym elementem. Ostatnie przypi­sanie ustala, że wstawiony do listy element jest jej nowym elementem końcowym, który nie ma nastę­pnika (rys. poniżej u dołu). Nowy licznik ułamka potrzebny w nastę­pnym kroku pętli jest obliczany w jej wyrażeniu modyfi­kującym.

Pełny program w języku C++ znajdujący rozwinięcie dziesiętne ułamka jest przedsta­wiony na poniższym listingu. Oprócz funkcji głównej i dwóch powyższych funkcji w programie występują trzy inne funkcje: czytania danych z prostą kontrolą ich poprawności, drukowania uzyskanego rozwi­nięcia ułamka i usuwania wygenero­wanej listy.

#include <iostream>
#include <cmath>

using namespace std;

struct Element
{
    char cyfra;
    int licznik;
    Element *nast;
} *poc = NULL, *okr;

bool ulamek_okresowy(int x)
{
    for (okr = poc; okr != NULL && okr->licznik != x; okr = okr->nast)
        ;
    return okr != NULL;
}

void rozwin_ulamek(int x, int y)
{
    Element *p, *kon = NULL;
    for ( ; x != 0 && !ulamek_okresowy(x); x %= y)
    {
        (p = new Element)->licznik = x;
        p->cyfra = (x *= 10) / y;
        if (kon != NULL)
            kon->nast = p;
        else
            poc = p;
        (kon = p)->nast = NULL;
    }
}

void drukuj_ulamek(int x, int y)
{
    cout << "Rozwinięcie: ";
    if (x * y < 0) cout << "-";
    cout << abs(x / y);
    if (poc == NULL) return;
    cout << ".";
    for (Element *p = poc; p != NULL; p = p->nast)
    {
        if (p == okr) cout << "(";
        cout << int(p->cyfra);
    }
    if (okr != NULL) cout << ")";
}

void usun_liste()
{
    Element *p;
    while (poc != NULL)
    {
        poc = (p = poc)->nast;
        delete p;
    }
}

bool czytaj_dane(int &p, int &q)
{
    cout << "Licznik: ";
    if (!(cin >> p)) return false;
    cin.ignore(1000, '\n');
    cout << "Mianownik: ";
    return ((cin >> q) && q != 0);
}

int main()
{
    int x, y;
    cout << "Rozwinięcie dziesiętne ułamka\n"
            "-----------------------------\n";
    if (!czytaj_dane(x, y))
    {
        cout << "Problem z danymi.\n";
        return 1;
    }
    rozwin_ulamek(abs(x % y), abs(y));
    drukuj_ulamek(x, y);
    cout << endl;
    usun_liste();
    return 0;
}

Uwaga. Dyrektywa #include włączająca biblio­tekę matema­tyczną jest wymagana jedynie w przypadku prepro­cesora MinGW C++. Ten mały problem z przeno­śnością programu wynika z niejedna­kowej struktury bibliote­cznych plików nagłów­kowych w różnych środowi­skach programi­stycznych C++.

Poniższy rysunek przedstawia wynik wykonania powyższego programu uruchamianego dwukrotnie z wiersza poleceń dla przykła­dowych danych reprezentu­jących ułamki o rozwinięciu skończonym i okresowym.

Program w C++ (wektor struktur)

W drugiej wersji programu wyznaczania rozwinięcia dziesię­tnego ułamka decydujemy się na skorzy­stanie z konte­nera klasy vector ze standar­dowej biblio­teki szablonów STL, ponieważ przecho­wuje dowolną liczbę elementów oraz pozwala na wygodne ich dokładanie i usuwanie. Elementami wektora będą struktury złożone z dwóch składników: numery­czny odpowie­dnik kolejnej cyfry dziesię­tnej i licznik ułamka rozpatry­wanego przy jej obli­czaniu. Definicja struktury oraz dekla­racje zmiennych reprezen­tujących wektor struktur i indeks identyfi­kujący pierwszą cyfrę okresu lub wskazujący na jego brak mogą wyglądać następu­jąco:

struct Element
{
    char cyfra;         // Wartość cyfrowa (0 - 9)
    int licznik;        // Licznik ułamka (reszta)
};

vector<Element> d;      // Wektor struktur Element
unsigned int okr;       // Indeks początku okresu

Opierając się na poprzedniej wersji programu bazującego na liście jednokie­runkowej, z łatwością tworzymy jego drugą wersję używającą wektora o elemen­tach typu Element. Zaczynamy od sprecy­zowania funkcji ulamek_­okresowy, która przegląda kolejne elementy wektora d i sprawdza, czy aktualny licznik x ułamka pojawił się przy ich wyzna­czaniu:

bool ulamek_okresowy(int x)
{
    for (okr = 0; okr < d.size() && d[okr].licznik != x; okr++)
        ;
    return okr < d.size();
}

Zakończenie przeglądania może nastąpić z dwóch powodów: osiągnięto koniec wektora lub natknięto się na element, którego pole licznik ma wartość równą x. Funkcja zwraca wartość false, gdy licznik x pojawił się po raz pierwszy w obli­czeniach, albo true, gdy pojawił się już wcześniej, co oznacza, że ułamek jest okresowy. Efektem ubocznym działania tej funkcji jest przypisanie zmiennej nielo­kalnej okr indeksu przekracza­jącego zakres indeksów wektora lub identyfi­kującego element z pierwszą cyfrą okresu.

Odwołując się do funkcji rozwin_ulamek znajdu­jącej rozwi­nięcie dziesiętne ułamka w postaci listy jednokie­runkowej, z łatwością otrzy­mujemy jej odpowie­dnik dla wektora:

void rozwin_ulamek(int x, int y)
{
    Element str;
    for ( ; x != 0 && !ulamek_okresowy(x); x %= y)
    {
        str.licznik = x;
        str.cyfra = (x *= 10) / y;
        d.push_back(str);
    }
}

Zmienna lokalna str jest strukturą używaną w każdym kroku pętli do przygoto­wania elementu złożonego z kolejnego licznika ułamka i cyfry rozwi­nięcia dziesię­tnego. Metoda push_back dopisuje przekazaną jej przez wartość strukturę str, czyli jej kopię, na końcu wektora d.

Niestety, ta propozycja zawiera błąd ujawniający się, gdy ułamek nie jest okresowy. Pętla for zostanie wówczas zakoń­czona z powodu zerowej wartości licznika x, dla której funkcja ulamek_­okresowy nie zostanie wywołana. Skutkiem tego od ostatniego jej wywołania indeks okr pozostanie niezmie­niony, a ponieważ od tego momentu do wektora dodano jeszcze jeden element, indeks ten będzie miał wartość d.size()-1 identyfi­kującą ostatni element wektora. Oznacza to, że ostatnia cyfra rozwi­nięcia dziesię­tnego ułamka nieokre­sowego zostanie potrakto­wana jako pierwsza i ostatnia cyfra okresu. Błąd ten da się naprawić poprzez przypisanie zmiennej okr aktualnej liczby elementów wektora po zakoń­czeniu pętli, gdy wartością x jest zero:

if (x == 0) okr = d.size();

Druga wersja programu wyznaczania rozwi­nięcia dziesię­tnego ułamka korzysta­jąca z kontenera klasy vector, którego elementami są struktury, jest przedsta­wiona na poniższym listingu. W porównaniu z pierwszą wersją bazującą na liście jednokie­runkowej oprócz omówionych powyżej dwóch funkcji dodatkowe niewielkie zmiany występują jedynie w funkcji drukowania rozwi­nięcia ułamka, a zamiast funkcji sekwen­cyjnego usuwania elementów listy użyta jest metoda clear usuwania wszystkich elementów wektora.

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

struct Element
{
    char cyfra;
    int licznik;
};

vector<Element> d;
unsigned int okr;

bool ulamek_okresowy(int x)
{
    for (okr = 0; okr < d.size() && d[okr].licznik != x; okr++)
        ;
    return okr < d.size();
}

void rozwin_ulamek(int x, int y)
{
    Element str;
    for ( ; x != 0 && !ulamek_okresowy(x); x %= y)
    {
        str.licznik = x;
        str.cyfra = (x *= 10) / y;
        d.push_back(str);
    }
    if (x == 0) okr = d.size();
}

void drukuj_ulamek(int x, int y)
{
    cout << "Rozwinięcie: ";
    if (x * y < 0) cout << "-";
    cout << abs(x / y);
    if (d.empty()) return;
    cout << ".";
    for (unsigned int k = 0; k < d.size(); k++)
    {
        if (k == okr) cout << "(";
        cout << int(d[k].cyfra);
    }
    if (okr < d.size()) cout << ")";
}

bool czytaj_dane(int &p, int &q)
{
    cout >> "Licznik: ";
    if (!(cin >> p)) return false;
    cin.ignore(1000, '\n');
    cout << "Mianownik: ";
    return ((cin >> q) && q != 0);
}

int main()
{
    int x, y;
    cout << "Rozwinięcie dziesiętne ułamka\n"
            "-----------------------------\n";
    if (!czytaj_dane(x, y))
    {
        cout << "Problem z danymi.\n";
        return 1;
    }
    rozwin_ulamek(abs(x % y), abs(y));
    drukuj_ulamek(x, y);
    cout << endl;
    d.clear();
    return 0;
}

Uwaga. Zamiast struktur elementami wektora mogą być wskaźniki na struktury, a ponadto zamiast indeksów iteratory. Oczywiście rozwią­zania te wymagają modyfi­kacji kodu źródło­wego programu.

Program w C++ (wektor obiektów)

W trzeciej wersji programu wyznaczania rozwinięcia dziesię­tnego ułamka skorzy­stamy z konte­nera klasy vector, którego elementami będą wskaźniki na obiekty klasy Element złożonej z dwóch pól reprezen­tujących cyfrę dziesiętną i licznik ułamka rozpatry­wanego przy jej obli­czaniu oraz konstru­ktora inicjali­zującego te pola. Taki wektor wskaźników zilustro­wano na poniższym rysunku.

Dla ułatwienia dostępu do pól klasy Element przyjmiemy, że są one publiczne. Definicja klasy oraz dekla­racje wektora wskaźników na obiekty i indeksu identyfi­kującego pierwszą cyfrę okresu lub wskazu­jącego na jego brak mogą mieć postać następu­jącą:

class Element
{
public:
    char cyfra;           // Wartość cyfrowa (0 - 9)
    int licznik;          // Licznik ułamka (reszta)
    Element(int x, int y) // Konstruktor klasy Element
    {
        licznik = x;
        cyfra = (10 * x) / y;
    }
};

vector<Element*> d;       // Wektor wskaźników Element*
unsigned int okr;         // Indeks początku okresu

Konstruktor klasy inicjalizuje obydwa pola tworzonego obiektu, mianowicie zgodnie z omówionym powyżej algorytmem w polu licznik zapamię­tuje licznik przeka­zanego mu w argu­mentach ułamka, a polu cyfra przypisuje wynik mnożenia tego licznika przez 10 i dzielenia całko­witego uzyskanego iloczynu przez mianownik ułamka.

Operację generowania wektora wskaźników formułujemy podobnie jak wektora struktur w poprzednim programie. Najpierw definiujemy pomocniczą funkcję ulamek_okresowy, której zadaniem jest przeglą­danie elementów wektora celem rozstrzy­gnięcia, czy ułamek jest okresowy:

bool ulamek_okresowy(int x)
{
    for (okr = 0; okr < d.size() && d[okr]->licznik != x; okr++)
        ;
    return okr < d.size();
}

Następnie formułujemy funkcję rozwin_ulamek, która wykonuje zasadniczą pracę polegającą na zbudowaniu ciągu obiektów klasy Element reprezen­tującego rozwi­nięcie dziesiętne ułamka i zapisaniu w elementach wektora wskaźników udostępnia­jących te obiekty:

void rozwin_ulamek(int x, int y)
{
    for ( ; x != 0 && !ulamek_okresowy(x); x = (10 * x) % y)
        d.push_back(new Element(x, y));
    if (x == 0) okr = d.size();
}

Zauważmy, że funkcja ta różni się bardziej od swojego pierwo­wzoru dla struktur niż funkcja pomocnicza. Po pierwsze, obliczenia wartości pól obiektu są w niej pominięte, ponieważ zostały przejęte przez konstru­ktor klasy. Po drugie, nie ma w niej dodatkowej zmiennej lokalnej, gdyż wygene­rowany przez operator new wskaźnik na utworzony przez konstru­ktor obiekt jest argu­mentem metody push_back, która dodaje go na końcu wektora d. Po trzecie wreszcie, wyrażenie modyfi­kujące w pętli for jest nieco rozbu­dowane, bowiem operacja mnożenia licznika x przez 10 reali­zowana wewnątrz konstru­ktora nie zmienia jego wartości wewnątrz funkcji rozwin_­ulamek.

W zaprezentowanej poniżej trzeciej wersji programu wyznaczania rozwi­nięcia dziesię­tnego ułamka wykorzy­stano kontener klasy vector, którego elementami są wskaźniki na obiekty klasy Element. W porównaniu z drugą wersją w programie występuje dodatkowa metoda usun_­wektor, która za pomocą operatora delete zwalnia pamięć przydzie­loną wszystkim obiektom wskazy­wanym przez elementy wektora.

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

class Element
{
public:
    char cyfra;
    int licznik;
    Element(int x, int y)
    {
        licznik = x;
        cyfra = (10 * x) / y;
    }
};

vector<Element*> d;
unsigned int okr;

bool ulamek_okresowy(int x)
{
    for (okr = 0; okr < d.size() && d[okr]->licznik != x; okr++)
        ;
    return okr < d.size();
}

void rozwin_ulamek(int x, int y)
{
    for ( ; x != 0 && !ulamek_okresowy(x); x = (10 * x) % y)
        d.push_back(new Element(x, y));
    if (x == 0) okr = d.size();
}

void drukuj_ulamek(int x, int y)
{
    cout << "Rozwinięcie: ";
    if (x * y < 0) cout << "-";
    cout << abs(x / y);
    if (d.empty()) return;
    cout << ".";
    for (unsigned int k = 0; k < d.size(); k++)
    {
        if (k == okr) cout << "(";
        cout << int(d[k]->cyfra);
    }
    if (okr < d.size()) cout << ")";
}

void usun_wektor()
{
    for (unsigned int k = 0; k < d.size(); k++)
        delete d[k];
    d.clear();
}

bool czytaj_dane(int &p, int &q)
{
    cout << "Licznik: ";
    if (!(cin >> p)) return false;
    cin.ignore(1000, '\n');
    cout << "Mianownik: ";
    return ((cin >> q) && q != 0);
}

int main()
{
    int x, y;
    cout << "Rozwinięcie dziesiętne ułamka\n"
            "-----------------------------\n";
    if (!czytaj_dane(x, y))
    {
        cout << "Problem z danymi.\n";
        return 1;
    }
    rozwin_ulamek(abs(x % y), abs(y));
    drukuj_ulamek(x, y);
    cout << endl;
    usun_wektor();
    return 0;
}

Opracowanie przykładu: grudzień 2019