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

Przykład C++

Sito Eratostenesa Algorytm Lista jednokierunkowa w C++ Program w C++ Biblioteka STL w C++ i klasa "vector" Program w C++ (wersja 2) Poprzedni przykład Następny przykład Program w Visual C# Kontakt

Sito Eratostenesa

Liczbę naturalną (całkowitą nieujemną) nazy­wamy pierwszą, gdy ma tylko dwa podziel­niki: 1 i samą siebie. Najmniejszą liczbą pierwszą jest 2. Naszym zadaniem jest zbudo­wanie programu wyzna­czania wszystkich liczb pierw­szych nie większych od danej liczby całko­witej n. Zastosujemy algorytm, który podał grecki matematyk Eratostenes, ur. ok. 275 p.n.e. w Cyrenie (Libia), zm. ok. 194 p.n.e. w Aleksandrii (Egipt). Algorytm nosi nazwę sito Eratostenesa.

Algorytm

W algorytmie Eratostenesa zaczynamy od utwo­rzenia listy wszystkich liczb całko­witych od 2 do n. Listę rozpo­czyna liczba pierwsza 2. Pozosta­wiamy ją, a wszystkie dalsze liczby, które są podzielne przez 2, usuwamy z listy. Następnie przecho­dzimy do liczby znajdu­jącej się bezpo­średnio za liczbą 2. Jest nią liczba 3. Pozosta­wiamy ją, a wszystkie dalsze liczby, które są podzielne przez 3, usuwamy. Bezpo­średnio za liczbą 3 znajduje się teraz liczba 5. Dalej więc usuwamy z listy wszystkie liczby występu­jące po liczbie 5, które są podzielne przez 5. Z pozo­stałymi liczbami postę­pujemy podobnie, aż dojdziemy do końca listy. W rezultacie pozostaną na niej tylko liczby pierwsze z określo­nego na początku zakresu. Opisana metoda nazywana jest sitem, gdyż efekt usuwania liczb podziel­nych przez wybraną liczbę pierwszą kojarzy się z nasta­wieniem oczek sita na przeni­kanie liczb złożonych i zatrzy­mywanie liczb pierwszych.

Stosowanie tablicy liczb naturalnych jest wygodne w realizacji sita Eratostenesa na papierze. W oblicze­niach kompute­rowych dopisanie nowego elementu do listy wymaga rezer­wacji rozmiaru tablicy na wyrost, a gdy nie ma w niej miejsca na nowy element, przepi­sania wartości ze starej tablicy do nowej o większym rozmiarze. Ponadto gdy element nie jest dopisy­wany na końcu tablicy, należy przesunąć wartości części lub wszystkich jej elementów w kierunku końca, by zrobić miejsce na nowy element. Co prawda w rozpatry­wanym przypadku problemy te nie wystąpią, gdyż z góry znany jest maksy­malny rozmiar tablicy, lecz przy usuwaniu elementów, których wartości nie są liczbami pierwszymi, potrzebne jest przesu­wanie wartości jej części elementów w kierunku początku. Oczywiście można tych przesunięć uniknąć, np. zastę­pując usuwane elementy zerami symbolizu­jącymi ich nieobe­cność, nie mniej jednak elasty­czność tablic jest niska.

Lista jednokierunkowa w C++

W programie realizującym sito Eratostenesa zamiast tablicy użyjemy listy jednokie­runkowej – dynami­cznej struktury danych, której elementy nie muszą zajmować ciągłego obszaru pamięci. Dodawanie i usuwanie elementów listy jest bardzo szybkie, gdyż nie wymaga przesu­wania jej pozosta­łych elementów. Przypo­mnijmy, że lista jednokie­runkowa była używana w prezen­towanym na niniejszej witrynie programie imitu­jącym fontannę.

Lista jednokierunkowa składa się z elementów (struktur w C/C++) zawiera­jących pewne dane i wskaźnik na następny element (rys.). W ostatnim elemencie jest nim wskaźnik pusty NULL, który oznacza, że element ten nie ma nastę­pnika. Dodatkowy wskaźnik (poc na rys.) udostę­pnia pierwszy element listy. Pomiędzy elemen­tami listy jednokie­runkowej można przecho­dzić tylko w jednym kierunku – od początku do końca; przecho­dzenie w dwóch kierunkach umożliwia lista dwukie­runkowa, której elementy zawierają dwa wskaźniki – na poprzedni i następny element. Rozmiar listy może się zmieniać, elementy mogą być tworzone i wsta­wiane do listy, mogą też być z niej usuwane.

Użycie listy jednokierunkowej reprezen­tującej ciąg liczb przetwa­rzany przez sito Eratostenesa wymaga zdefinio­wania struktury złożonej z dwóch pól, których wartościami są: liczba całkowita (poten­cjalna liczba pierwsza) i wskaźnik na następny element. Jeśli strukturę elementów listy nazwiemy Element, a jej skła­dniki x (liczba) i nast (wskaźnik), to strukturę tę definiujemy w C++ następu­jąco:

struct Element
{
    int x;             // Liczba
    Element *nast;     // Następny element
} *poc = NULL;         // Początek listy

Zadeklarowana dodatkowo zmienna poc o wartości NULL oznacza, że wstępnie lista jest pusta. Jak wiadomo, dostęp do składników struktury wskazy­wanej przez wskaźnik umożliwia operator ->. Jeśli np. p jest wskaźni­kiem na strukturę typu Element (element listy), to p->nast jest polem tej struktury (wskaźni­kiem na następny element listy). Przypo­mnijmy, że zapis ten jest równo­ważny mniej czytel­nemu zapisowi (*p).nast, w którym *p oznacza strukturę wskazy­waną przez wskaźnik p (nawiasy są niezbędne, gdyż operator kropki ma wyższy priorytet niż operator gwiazdki).

Operacje wstawiania elementów do listy i usuwania ich są bardzo proste, gdy dotyczą początku listy. Wstawienie nowego elementu na początek listy sprowadza się do uaktualnień dwóch wskaźników. Jeśli wartością zmiennej p jest wskaźnik na wsta­wiany element, to operację tę można sformu­łować następu­jąco:

p->nast = poc;
poc = p;

Kolejność tych dwóch przypisań jest bardzo istotna. Pierwsze sprawia, że nastę­pnikiem elementu wskazy­wanego przez wskaźnik p jest dotych­czasowy pierwszy element listy (rys. poniżej z lewej), a drugie, że nowym pierwszym elementem listy jest element wskazy­wany przez wskaźnik p (rys. poniżej z prawej). Kod ten jest poprawny również w przypadku, gdy lista jest pusta.

Operacja wielokrotnego wstawiania nowego elementu na początek wstępnie pustej listy jest prostym sposobem genero­wania takiej listy. Wynikowy porządek elementów listy jest odwrotny do kolejności ich wstawiania. Nietrudno zatem sprecy­zować funkcję genero­wania listy wszystkich liczb od 2 wzwyż przesie­wanych przez sito Eratostenesa:

void generuj_liste()   // Wersja uproszczona
{
    cout << "n = ";
    int n;
    cin >> n;
    Element *p;
    while (n > 1)
    {
        (p = new Element)->x = n--;
        p->nast = poc;
        poc = p;
    }
}

(w funkcji pominięto kontrolę poprawności wczyty­wanej z klawia­tury wartości n). W każdym kroku pętli while tworzony jest w pamięci nowy element (struktura typu Element). Po przypi­saniu polu x wartości n element ten jest wstawiany na początek listy. Z uwagi na odwrotny porządek wynikowy elementów listy do porządku ich genero­wania i wsta­wiania elementy te są obsługi­wane w kolejności maleją­cych wartości pola x (dekremen­tacja n).

Usunięcie pierwszego elementu listy jednokie­runkowej sprowadza się jedynie do uaktual­nienia wskaźnika poc (rys.). Należy jednak zachować wskaźnik na usuwany element, by go nie zgubić:

p = poc;               // Usuwany element
poc = p->nast;         // Nowy początek listy

Kod ten można wyrazić w prostszej postaci:

poc = (p = poc)->nast;

Usunięty element listy może być nadal używany w programie, a jeśli nie, należy zwolnić przydzie­loną mu pamięć (oddać zajmowaną przez niego pamięć do dyspo­zycji systemu operacyj­nego), by uniknąć wycieku pamięci. Zwolnienie pamięci wszystkich elementów listy jest prostą operacją sekwen­cyjną. Mianowicie dopóki lista nie jest pusta, należy usuwać jej pierwszy element i zwalniać zajmowany przez niego obszar pamięci:

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

W niektórych zastosowaniach operacje dołączania elementów do listy i usuwania ich nie dotyczą początku listy, lecz innych jej miejsc. W przy­padku implemen­tacji listowej sita Eratostenesa trzeba usuwać zbędne elementy występu­jące po innych elemen­tach listy. Rozważmy zadanie usunięcia z listy nastę­pnika elementu *p. Innymi słowy, chcemy usunąć element znajdu­jący się bezpo­średnio za elementem wskazy­wanym przez wskaźnik p. Rozwią­zanie sprowadza się do wyko­nania dwóch przypisań:

q = p->nast;           // Usuwany element
p->nast = q->nast;     // Usunięcie elementu z listy

Pierwsze przypisanie zapamiętuje w zmiennej pomocni­czej q wskaźnik na usuwany element (rys. poniżej u góry), drugie ustala, że następni­kiem elementu *p jest następnik elementu *q (rys. poniżej u dołu).

Program w C++

Najwyższy czas zająć się operacją przesiewania reali­zowaną przez algorytm Eratostenesa. Przyjmijmy, że wskaźnik w wskazuje na element listy zawiera­jący liczbę pierwszą. Na początku jest to pierwszy element listy z liczbą 2. Za każdym razem po usunięciu wszystkich elementów znajdu­jących się za elementem *w, które zawierają liczbę podzielną przez liczbę pierwszą w->x, wskaźnik w jest przesu­wany na następny element, który, jak wiadomo, zawiera kolejną liczbę pierwszą. Przesie­wanie zakończy się, gdy wskaźnik w osiągnie wartość NULL:

for (Element *w = poc; w != NULL; w = w->nast)
{
    ...   // Usuwanie zbędnych elementów występujących po *w
}

Aby usunąć wszystkie zbędne elementy listy występu­jące po elemencie *w, wystarczy przeglądać listę, manipu­lując dwoma wskaźni­kami p i q wskazu­jącymi na dwa sąsiednie jej elementy (q=p->nast), poczynając od wskaźnika w. Jeśli okaże się, że wartość q->x jest podzielna przez w->x, należy usunąć element *q i zwolnić jego pamięć. W przeci­wnym razie należy przesunąć wskaźnik p w miejsce q, pozosta­wiając na razie element *q w liście, gdyż może on zawierać liczbę pierwszą. Całą operację przesie­wania elementów listy można sformu­łować następu­jąco:

void przesiewaj_liste()
{
    Element *p, *q, *w;
    for (w = poc; w != NULL; w = w->nast)
        for (p = w; (q = p->nast) != NULL; )
            if (q->x % w->x == 0)
            {
                p->nast = q->nast;
                delete q;
            }
            else
                p = q;
}

Pełny program w C++, który dla podanej z klawiatury liczby naturalnej znajduje wszystkie liczby pierwsze nie większe od niej, używając sita Eratostenesa implemento­wanego za pomocą listy jednokie­runkowej, jest przedsta­wiony na poniższym listingu. Funkcja generuj­_liste jest w nim w porównaniu z pierwo­wzorem rozbu­dowana o kontrolę poprawności wczyty­wanej liczby z uwzglę­dnieniem zakresu określo­nego przez stałą N.

#include <iostream>
#include <iomanip>

using namespace std;

struct Element
{
    int x;
    Element *nast;
} *poc = NULL;

const int N = 25000;    // Maksymalny zakres

bool generuj_liste()
{
    cout << "n = ";
    int n;
    if (!(cin >> n) || n < 2 || n > N)
        return false;
    Element *p;
    while (n > 1)
    {
        (p = new Element)->x = n--;
        p->nast = poc;
        poc = p;
    }
    return true;
}

void przesiewaj_liste()
{
    Element *p, *q, *w;
    for (w = poc; w != NULL; w = w->nast)
        for (p = w; (q = p->nast) != NULL; )
            if (q->x % w->x == 0)
            {
                p->nast = q->nast;
                delete q;
            }
            else
                p = q;
}

void drukuj_liste()
{
    for (Element *p = poc; p != NULL; p = p->nast)
        cout << setw(7) << p->x << " ";
    cout << endl;
}

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

int main()
{
    cout << "Sito Eratostenesa\nLiczby pierwsze od 2 do n (max. " << N << ")\n";
    if (generuj_liste())
    {
        przesiewaj_liste();
        drukuj_liste();
        zwolnij_liste();
        return 0;
    }
    else
    {
        cout << "Problem z n.\n";
        return 1;
    }
}

Poniższy rysunek przedstawia ciąg wszystkich liczb pierwszych nie większych od 1000 wygenero­wany przez program SitoEra w wersji dla kompi­latora MinGW.

Biblioteka STL w C++ i klasa "vector"

W języku C++ dostępna jest standardowa biblioteka szablonów (ang. Standard Template Library, STL) zawiera­jąca wiele gotowych do użycia klas umożliwia­jących wygodne korzystanie z kontenerów oraz operu­jących na nich algo­rytmów. Kontenery (pojemniki, zasobniki) są obiektami, które służą do przecho­wywania elementów tego samego typu, przy czym może to być typ standar­dowy, wbudowany w bibliotekę STL lub zdefinio­wany przez użytko­wnika. Kontenery zarządzają potrzebną pamięcią i udostę­pniają elementy za pomocą indeksów lub tzw. iteratorów (obiektów podobnych w działaniu do wskaźników), umożli­wiając łatwą implemen­tację podsta­wowych struktur danych, takich jak wektory (tablice), listy, stosy, kolejki. Należy pamiętać, że zawartość biblio­teki STL znajduje się w przestrzeni nazw std.

Jednym z najprostszych i najczęściej używanych konte­nerów jest wektor – obiekt klasy vector stano­wiący ulepszoną wersję tablicy dynami­cznej. Elementy wektora są podobnie jak elementy tablicy przecho­wywane w pamięci jeden obok drugiego w spójnym bloku, ale w trakcie działania programu można zmieniać ich liczbę. Elementy można dodawać i usuwać w dowolnym miejscu wektora, choć najefekty­wniej jest robić to na końcu, gdyż nie jest wtedy wymagane przesu­wanie innych elementów. Oczywiście gdy przydzie­lony wektorowi obszar pamięci jest za mały, by pomieścić dodawany element, rezerwo­wany jest większy obszar pamięci dla nowej tablicy elementów, do której kopiowana jest zawartość dotychcza­sowej tablicy, po czym obszar pamięci starej tablicy jest oddawany do dyspozycji systemu operacyj­nego. Odbywa się to automa­tycznie, progra­mista jest zwolniony od zarządza pamięcią wektora. Aby uzyskać dostęp do klasy vector, należy włączyć plik nagłów­kowy vector.

Klasa vector należy do tzw. typów (klas) genery­cznych charaktery­zujących się tym, że ich kod jest uogólniony – pisany jako szablon (ang. template) bez znajo­mości typu danych, na których działają. W dekla­racji obiektu klasy genery­cznej należy typ takich danych określić w nawiasach <> po nazwie klasy. Zatem wektor o nazwie x reprezen­tujący ciąg liczb całko­witych przetwa­rzany przez sito Eratostenesa możemy zdefi­niować następu­jąco:

vector<int> x;

Utworzony w ten sposób wektor nie ma żadnego elementu, o czym można się przekonać, wywołując metodę size, która zwraca liczbę aktualnie przechowy­wanych w wektorze elementów. Można również sprawdzić, czy wektor jest pusty, korzystając z metody empty zwraca­jącej wartość logiczną (true – pusty, false – nie).

Metoda push_back dodaje nowy element na końcu wektora. Wywołując ją wielokro­tnie dla wartości całko­witych od 2 wzwyż, uzyskamy wektor reprezen­tujący początkowy ciąg liczb przesie­wanych przez sito Eratostenesa. Jego rozmiar możemy ustalić za pomocą metody reserve przed dodawaniem elementów, gdy tylko wczytane zostanie z klawia­tury górne ograni­czenie ciągu. Funkcję genero­wania wektora możemy więc sprecy­zować następu­jąco:

void generuj_wektor()   // Wersja uproszczona
{
    cout << "n = ";
    int n;
    x.reserve(n - 1);
    for (int k = 2; k <= n; k++)
        x.push_back(k);
}

Gdy nie zarezerwujemy maksymalnej pojemności wektora, funkcja genero­wania go będzie poprawna, ale jej złożoność czasowa może być wyższa, ponieważ przy dodawaniu nowego elementu wektor ten może być powiększany więcej niż jeden raz. Pojemność zarezerwo­wanego wektora udostę­pnia metoda capacity. Ostatni element wektora zwraca metoda back, a usuwa metoda pop_back. Wszystkie elementy wektora można usunąć sekwen­cyjnie:

while (!x.empty())
    x.pop_back();

ale o wiele prościej tego dokonać, wywołując metodę clear.

Dostęp do poszczególnych elementów wektora można uzyskać, korzystając z opera­tora [] i indeksu, czyli dokładnie tak samo jak do elementów tablicy. Skutkiem tego funkcja wypisania całego ciągu może mieć postać:

void drukuj_wektor()
{
    for (unsigned int k = 0; k < x.size(); k++)
        cout << setw(7) << x[k] << " ";
    cout << endl;
}

(modyfikator unsigned został użyty dla zape­wnienia zgodności z typem metody size). Ten sposób dostępu nie jest jednak możliwy we wszystkich opera­cjach na wektorach, np. nie można skorzystać z indeksu przy wsta­wianiu i usu­waniu elementu, gdy operacje te nie dotyczą końca wektora (metody inserterase). Podsta­wowym narzę­dziem poruszania się po elementach wektora są iteratory – obiekty klasy ściśle związanej z klasą wektora przypomi­nające wskaźniki. Przykła­dowo definicja

vector<int>::iterator it;

określa zmienną it typu iterator dla wektora typu vector<int>. Jeśli it wskazuje na pewien element wektora x, to *it jest tym elementem, a it++ wskazuje na następny element tego wektora. Klasa vector udostępnia również bezargu­mentowe metody zwraca­jące itera­tory:

Istnieją również iteratory klasy reverse_iterator działające w odwro­tnej kolejności z metodami rbegin (iterator wskazu­jący na ostatni element wektora) i rend (iterator odwołu­jący się do nieistnie­jącego elementu przed pierwszym elementem wektora). Przedstawioną powyżej funkcję wypisywania ciągu liczbowego można sformu­łować przy użyciu iteratora przebiega­jącego wszystkie elementy wektora x od pierwszego do ostatniego:

void drukuj_wektor()
{
    for (vector<int>::iterator it = x.begin(); it != x.end(); it++)
        cout << setw(7) << *it << " ";
    cout << endl;
}

Jak widać, przebieganie elementów wektora za pomocą iteratora kończy się, gdy osiągnął on wartość zwracaną przez metodę end wskazu­jącą na element nieistnie­jący. Podobień­stwo itera­torów do trady­cyjnych wskaźników przejawia się również w wyraże­niach takich, jak:

Można nawet za pomocą operatora -> dostać się do składowych elementów wektora, gdy są nimi struktury lub obiekty. Jeśli np. elementami wektora byłyby struktury zawiera­jące dane osobowe z polem pesel, to wyrażenie it->pesel określa­łoby numer PESEL osoby, której dane znajdują się w elemencie wskazy­wanym przez iterator it.

Przejdźmy wreszcie do sformułowania funkcji przesie­wania wektora x przy zastoso­waniu sita Eratostenesa. Opierając się na omówionej wyżej funkcji przesie­wania listy, defi­niujemy w nowej funkcji trzy iteratory p, q i w spełniające podobną rolę jak wskaźniki w funkcji przesiewa­jącej listę. Iterator w ma wskazywać na element wektora będący liczbą pierwszą. Na początku jest nim pierwszy element równy 2, a każdo­razowo po usunięciu wszystkich następnych elementów, które są podzielne przez *w, iterator w jest przesuwany o jedno miejsce, czyli na następny element będący liczbą pierwszą. Usuwanie elementów podziel­nych przez *w i przesu­wanie iteratora w jest kontynuo­wane dopóty, dopóki nie osiągnie wartości wskazu­jącej poza ostatni element wektora.

Usuwanie elementów wektora podzielnych przez element wskazy­wany przez iterator w będzie realizo­wane przy użyciu pary iteratorów p i q wskazu­jących na dwa sąsiednie elementy (q=p+1). Iteratory te są przesuwane w kierunku końca wektora, począwszy od iteratora w wskazu­jącego na liczbę pierwszą. Jeśli element *q jest podzielny przez element *w, jest usuwany za pomocą metody erase, w przeci­wnym razie iterator p jest przesuwany w miejsce q. Całą operację przesie­wania elementów wektora można sformu­łować następu­jąco:

void przesiewaj_wektor()
{
    vector<int>::iterator p, q, w;
    for (w = x.begin(); w != x.end(); w++)
        for (p = w; (q = p + 1) != x.end(); )
            if (*q % *w == 0)
                x.erase(q);
            else
                p = q;
}

Program w C++ (wersja 2)

Druga wersja programu w C++, która dla podanej z klawiatury liczby naturalnej znajduje wszystkie liczby pierwsze nie większe od niej, używając sita Eratostenesa implemento­wanego za pomocą obiektu klasy vector, jest przedsta­wiona na poniższym listingu.

#include <iostream>
#include <iomanip>
#include <vector>

using namespace std;

const int N = 25000;    // Maksymalny zakres

vector<int> x;

bool generuj_wektor()
{
    cout << "n = ";
    int n;
    if (!(cin >> n) || n < 2 || n > N)
        return false;
    x.reserve(n - 1);
    for (int k = 2; k <= n; k++)
        x.push_back(k);
    return true;
}

void przesiewaj_wektor()
{
    vector<int>::iterator p, q, w;
    for (w = x.begin(); w != x.end(); w++)
        for (p = w; (q = p + 1) != x.end(); )
            if (*q % *w == 0)
                x.erase(q);
            else
                p = q;
}

void drukuj_wektor()
{
    for (vector<int>::iterator k = x.begin(); k != x.end(); k++)
        cout << setw(7) << *k << " ";
    cout << endl;
}

int main()
{
    cout << "Sito Eratostenesa\nLiczby pierwsze od 2 do n (max. " << N << ")\n";
    if (generuj_wektor())
    {
        przesiewaj_wektor();
        drukuj_wektor();
        x.clear();
        return 0;
    }
    else
    {
        cout << "Problem z n.\n";
        return 1;
    }
}

Opracowanie przykładu: grudzień 2019