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

Przykład C++

Krzywe Sierpińskiego Rekurencja w programowaniu Algorytm kreślenia krzywej Program w C++ Algorytm (wersja 2) Program w C++ (wersja 2) Poprzedni przykład Następny przykład Program w Visual C# Kontakt

Krzywe Sierpińskiego

Przykładami atrakcyjnie wyglądających układów grafi­cznych, które dają się łatwo wygene­rować za pomocą programu kompute­rowego, są krzywe Sierpiń­skiego. Przy ich rysowaniu nie korzysta się z równań matematy­cznych, których być może nikt jeszcze nie odkrył, lecz ze ściśle określo­nego schematu rekuren­cyjnego sterują­cego narzę­dziem kreślącym kompu­tera. Poniższy rysunek przedstawia krzywe Sierpiń­skiego rzędu 1 (z lewej) i 2 (z prawej). Już na pierwszy rzut oka widać, że krzywą rzędu 2 złożono z czterech krzywych rzędu 1 dwukrotnie zmniej­szonych, w których najpierw usunięto po jednym narożnym odcinku, a nastę­pnie wszystkie połą­czono czterema odcinkami na przemian poziomymi i pionowymi. Odkrycie schematu rekurencji stanowi klucz do napisania programu.

Rekurencja w programowaniu

Algorytm lub podprogram (funkcję w języku C lub C++) nazywamy rekuren­cyjnym, gdy odwołuje się do siebie (bezpośre­dnio lub pośre­dnio). Zazwyczaj algorytmy i podpro­gramy rekuren­cyjne są bardziej przej­rzyste i krótsze niż ich odpowie­dniki itera­cyjne, jednak realizo­wane na komputerze mają większą złożoność pamięciową i czasową.

Za każdym razem, gdy podprogram jest wywoły­wany, rezerwuje się dla niego w części pamięci zwanej stosem (ang. stack) obszar pamięci nazywany ramką stosu (ang. stack frame), w którym przecho­wuje się m.in. wartości argumentów, nowy zestaw zmiennych lokalnych i adres miejsca pamięci, do którego ma nastąpić powrót po wyko­naniu podprogramu. Gdy podprogram jest wywoły­wany, ramka stosu jest tworzona nieza­leżnie od tego, czy podobna ramka istnieje dla wcześniej­szego wywołania, czy nie, i jest zdejmowana ze stosu, gdy zakończy się wykonanie podprogramu dla tego wywołania i następuje powrót do miejsca wywołania. Tak więc w przypadku wywołań rekuren­cyjnych powstaje odrębna ramka stosu dla każdego wywołania, przez co wzrasta zajętość pamięci, a z uwagi na konie­czność zarządzania ramkami wzrasta także czas pracy procesora.

Nie oznacza to bynajmniej, że zawsze należy unikać rekurencji. Za użyciem rekurencji przemawia czytelność i prostota algorytmu oraz rekuren­cyjne zdefinio­wanie rozwiązy­wanego problemu, kiedy to wybór rekuren­cyjnej wersji algorytmu wydaje się szczególnie naturalny i uzasa­dniony. Rekurencji należy unikać przede wszystkim wtedy, gdy istnieje oczywiste rozwią­zanie itera­cyjne, a także, gdy prowadzi ona do zbyt długiego ciągu wywołań rekuren­cyjnych, ponieważ grozi niebezpie­czeństwem przepeł­nienia stosu lub znacznym spowolnie­niem wykony­wania programu.

Przykładem rozwiązania iteracyj­nego i rekuren­cyjnego jest obliczanie współczyn­ników Newtona. Nawet w przypadku tak prostych dwóch funkcji wersja rekuren­cyjna jest czytel­niejsza. Jednak wraz ze wzrostem wartości argumentów liczba uakty­wnień rekuren­cyjnych rośnie wykła­dniczo, wiodąc do wielokro­tnego obliczania tych samych wartości, przez co funkcja ta staje się niepra­ktyczna. Innym przykładem zastoso­wania rekurencji, tym razem uzasa­dnionej, jest wypisy­wanie słowne cyfr dziesiętnych liczby całkowitej n≥0. Problem można sprowadzić do wypisania cyfr wartości n/10, czyli wszystkich cyfr n prócz ostatniej, a następnie do dopisania ostatniej cyfry liczby n. Prowadzi to do programu, w którym występuje funkcja rekuren­cyjna:

#include <iostream>
#include <string>

using namespace std;

string c[] = {"zero", "jeden", "dwa", "trzy", "cztery", "pięć",
              "sześć", "siedem", "osiem", "dziewięć"};

void wypisz(int n)
{
    if (n > 9)
        wypisz(n / 10);
    cout << c[n % 10] << " ";
}

int main()
{
    int n;
    cout << "Liczba całkowita nieujemna: ";
    cin >> n;
    wypisz(n);
    cout << endl;
    return 0;
}

Liczba wywołań rekurencyjnych jest w funkcji wypisz mała, a zamiana jej na postać iteracyjną wymaga wyzna­czenia tablicy lub łańcucha cyfr występu­jących w zapisie dziesię­tnym liczby albo konkate­nacji (dodawania) łańcuchów. Funkcja nie byłby jednak tak zręczna i czytelna. Nieporówny­walnie trudniej­szym byłoby przekształ­cenie na postać itera­cyjną sformuło­wanych poniżej programów kreślenia krzywych Sierpińskiego.

Algorytm kreślenia krzywej

W celu znalezienia schematu rekurencji krzywej Sierpiń­skiego oznaczmy przez n jej rząd, a przez h przesu­nięcie jednostkowe pisaka. Jak widać na poniższym rysunku, krzywa składa się z ukośnych odcinków wiodących wzdłuż przeką­tnych kwadratów o boku h oraz poziomych i piono­wych odcinków o długości 2h. Rysunek sugeruje również, że w krzywej rzędu n można wyróżnić cztery identy­czne segmenty Sn (kolor czarny) obrócone względem siebie o kąt prosty i powią­zane czterema narożnymi odcinkami (kolor czerwony). Jeśli przyjąć, że zegment S0 jest krzywą pustą, to wówczas cała krzywa redukuje się do kwadratu złożonego tylko z naroż­nych odcinków. Traktujemy ją jako krzywą Sierpiń­skiego rzędu 0.

Pisak jest oczywiście narzędziem wyimagi­nowanym. Przyjmijmy, że podobnie jak żółw w języku Logo może on poruszać się naprzód wzdłuż odcinka prostej i zmieniać kierunek ruchu. Jeżeli po naryso­waniu segmentu pisak będzie ustawiony w takim samym kierunku, w jakim był ustawiony tuż przed rozpoczę­ciem ryso­wania go (strzałki), to schemat kreślenia krzywej Sierpiń­skiego rzędu n sprowadzi się do wstępnego usta­wienia pisaka pod kątem –45o względem osi x (zgodnie z ruchem wskazówek zegara) i czterokro­tnego wykonania ciągu trzech operacji:

Rekurencyjność rozwiązania występuje w proce­durze kreślenia segmentu Sn i przejawia się w zastą­pieniu go czterema segmentami Sn–1 odpowie­dnio obróco­nymi i połą­czonymi trzema odcinkami:

Nietrudno zauważyć, że krzywa rzędu 0 zawiera się w kwadracie o boku 2h, krzywa rzędu 1 w kwadracie o boku 6h, a krzywa rzędu 2 w kwadracie o boku 14h. Z konstru­kcji krzywej Sierpiń­skiego rzędu n>0 wynika, że mieści się ona w kwadracie o boku an równym sumie długości dwóch boków an–1 i odcinka 2h. Łatwo stąd wyprowa­dzić ogólny wzór na rozmiar takiego kwadratu zależny tylko od przesu­nięcia jednostko­wego h:

Program w C++

Formułowanie programu rysującego krzywe Sierpiń­skiego rozpoczy­namy od zadekla­rowania trzech zmiennych global­nych określających rząd krzywej, przesu­nięcie jedno­stkowe pisaka i kierunek jego ruchu oraz sprecyzo­wania funkcji kreślenia odcinka. Jeżeli osiem możliwych kierunków ustawienia pisaka ponume­rujemy kolej­nymi liczbami całko­witymi od 0 do 7 (0 – północ, 1 – półno­cny zachód, 2 – zachód, ..., 7 – północny wschód), to stosowny fragment kodu źródło­wego możemy zapisać w następu­jącej postaci:

int n;              // Rząd krzywej Sierpińskiego
int h;              // Przesunięcie jednostkowe pisaka
int kierunek = 5;   // Kierunek ruchu pisaka (południowy wschód)

void odcinek()
{
    switch (kierunek)
    {
        case 0: linerel(0, -2 * h); break;  // Północ
        case 1: linerel(-h, -h);    break;  // Północny zachód
        case 2: linerel(-2 * h, 0); break;  // Zachód
        case 3: linerel(-h, h);     break;  // Południowy zachód
        case 4: linerel(0, 2 * h);  break;  // Południe
        case 5: linerel(h, h);      break;  // Południowy wschód
        case 6: linerel(2 * h, 0);  break;  // Wschód
        case 7: linerel(h, -h);     break;  // Północny wschód
    }
}

Inicjalizacja zmiennej kierunek wartością 5 odpo­wiada wstępnemu ustawieniu pisaka pod kątem –45o względem osi x. Zwiększenie wartości tej zmiennej o 1 oznacza obrót pisaka o 45o, zwiększenie o 3 obrót o 3x45o=135o, zaś zwiększenie o 6 obrót o 6x45o=270o, czyli o –90o. Jeżeli po tej modyfi­kacji nowa wartość zmiennej przekroczy zakres od 0 do 7, zostaje skorygo­wana za pomocą działania modulo 8 (% 8). Przedsta­wiony powyżej rekuren­cyjny schemat kreślenia segmentu Sn może więc wyglądać następująco:

void segment(int n)
{
    if (n > 0)
    {
        segment(n - 1);
        odcinek();
        kierunek = (kierunek + 6) % 8;  // Obrót o -90 stopni
        segment(n - 1);
        kierunek = (kierunek + 3) % 8;  // Obrót o +135 stopni
        odcinek();
        kierunek = (kierunek + 1) % 8;  // Obrót o +45 stopni
        segment(n - 1);
        odcinek();
        kierunek = (kierunek + 6) % 8;  // Obrót o -90 stopni
        segment(n - 1);
    }
}

Pełny program w C++ rysujący krzywą Sierpiń­skiego rzędu n dla pobiera­nych z klawia­tury parametrów n i h jest zaprezen­towany na poniższym listingu. Ograni­czenia rzędu n do zakresu od 0 do 8 i przesu­nięcia h do zakresu od 1 do 28–n pikseli wynikają z rozmiaru krzywej i rozdziel­czości ekranu. Przy obliczaniu górnej granicy h (zmienna hMax w funkcji dane) i boku kwadratu mieszczącego krzywą (zmienna a w funkcji main) użyto przesu­nięcia bitowego w lewo (operator <<), które w odnie­sieniu do liczby 1 odpowiada podnie­sieniu podstawy 2 do potęgi równej liczbie przesu­nięć. Rekuren­cyjna funkcja kreślenia segmentu jest w stosunku do pierwo­wzoru nieco usprawniona poprzez użycie operatora dekremen­tacji (--) bezpośre­dnio w porówna­niu n z zerem (zmniej­szenie wartości n po jej wykorzy­staniu). Rysowanie krzywej rozpoczyna się od wierz­chołka (h,0) przesunię­tego w kierunku środka obszaru robo­czego okna grafi­cznego, by zajmowała jego centralne miejsce, gdy się w nim mieści, bądź o cztery piksele od jego górnego ew. lewego brzegu, gdy przekracza jego rozmiar (funkcja moveto).

#include <iostream>
#include <graphics.h>

using namespace std;

int n;              // Rząd krzywej Sierpińskiego
int h;              // Przesunięcie jednostkowe pisaka
int kierunek = 5;   // Kierunek ruchu pisaka (południowy wschód)

bool dane()
{
    cout << "Krzywa Sierpińskiego\n--------------------\n";
    cout << "n (od 0 do 8): ";
    if (!(cin >> n) || n < 0 || n > 8)
        return false;
    int hMax = 1 << (8 - n);
    cout << "h (od 1 do " << hMax << "): ";
    return (cin >> h) && h > 0 && h <= hMax;
}

void odcinek()
{
    switch (kierunek)
    {
        case 0: linerel(0, -2 * h); break;  // Północ
        case 1: linerel(-h, -h);    break;  // Północny zachód
        case 2: linerel(-2 * h, 0); break;  // Zachód
        case 3: linerel(-h, h);     break;  // Południowy zachód
        case 4: linerel(0, 2 * h);  break;  // Południe
        case 5: linerel(h, h);      break;  // Południowy wschód
        case 6: linerel(2 * h, 0);  break;  // Wschód
        case 7: linerel(h, -h);     break;  // Północny wschód
    }
}

void segment(int n)
{
    if (n-- > 0)
    {
        segment(n);
        odcinek();
        kierunek = (kierunek + 6) % 8;  // Obrót o -90 stopni
        segment(n);
        kierunek = (kierunek + 3) % 8;  // Obrót o +135 stopni
        odcinek();
        kierunek = (kierunek + 1) % 8;  // Obrót o +45 stopni
        segment(n);
        odcinek();
        kierunek = (kierunek + 6) % 8;  // Obrót o -90 stopni
        segment(n);
    }
}

int main()
{
    if (dane())
    {
        initwindow(800, 600, "Krzywa Sierpińskiego");
        int a = ((1 << (n + 2)) - 2) * h;
        int dx = (getmaxx() - a) / 2;
        int dy = (getmaxy() - a) / 2;
        moveto(((dx < 0) ? 4 : dx) + h, (dy < 0) ? 4 : dy);
        for (int k = 0; k < 4; k++)
        {
            segment(n);
            odcinek();
            kierunek = (kierunek + 6) % 8;  // Obrót o -90 stopni
        }
        getch();
        closegraph();
        return 0;
    }
    else
    {
        cout << "Problem z danymi" << endl;
        return 1;
    }
}

Przykładowy wynik wykonania programu dla n=5 i h=6 przedstawia poniższy rysunek. Szybkość rysowania krzywej nieco rozczaro­wuje przy wyższych wartościach parametru n.

Algorytm (wersja 2)

Inny algorytm kreślenia krzywej Sierpiń­skiego podał Niklaus Wirth w książce Algorithms + Data Structures = Programs (1976, język Pascal) wydawanej również w Polsce (Algorytmy + struktury danych = programy, 1980–2004). Implemen­tację tego algorytmu w Delphi 7 można znaleźć na niniej­szej witrynie. Schemat rekuren­cyjny polega na złożeniu krzywej z czterech krzywych otwartych i łączących je odcinków. Na poniż­szym rysunku przedsta­wiającym krzywe Sierpiń­skiego rzędu 1 i 2 krzywe składowe są naryso­wane kolorem czarnym i oznaczone literami A, B, C i D z inde­ksami określa­jącymi rząd, a łączące je odcinki kolorem czerwonym. Rzecz jasna krzywe składowe rzędu 0 są puste, a krzywa Sierpiń­skiego rzędu 0 jest kwadratem złożonym z narożnych odcinków.

Schemat rekurencyjny kreślenia krzywych składowych A, B, C i D rzędu n można łatwo zdefi­niować za pomocą wywołań rekuren­cyjnych takich krzywych rzędu n–1:

Strzałki wskazują kierunek ruchu pisaka podczas kreślenia odcinków łączących. Linie pojedyncze oznaczają przesu­nięcie pisaka wzdłuż przekątnej kwadratu o boku h, a linie podwójne przesu­nięcie o długości 2h wzdłuż osi xy. Całą krzywą Sierpiń­skiego rzędu n można narysować za jednym pociągnię­ciem pisaka według schematu:

Program w C++ (wersja 2)

W programie rysującym krzywe Sierpiń­skiego według algorytmu Wirtha potrzebne są tylko dwie zmienne globalne n i h reprezen­tujące rząd krzywej i przesu­nięcie jedno­stkowe pisaka. Do wczytania ich wartości z klawia­tury można użyć tej samej funkcji dane, co w poprze­dnim programie. Przedstawiony powyżej schemat rekuren­cyjny kreślenia czterech krzywych składo­wych daje się łatwo przekształcić na język C++, np. jego pierwszy wiersz można zapisać w postaci:

void A(int n)
{
    if (n > 0)
    {
        A(n - 1);  linerel(h, h);
        B(n - 1);  linerel(2 * h, 0);
        D(n - 1);  linerel(h, -h);
        A(n - 1);
    }
}

W podobny sposób można zdefiniować funkcje rekuren­cyjne odpowia­dające pozostałym wierszom schematu. Problem stanowi jednak rekurencja pośrednia, np. w funkcji A oprócz dwóch wywołań bezpośre­dnich jej samej występują wywołania dwóch niezadekla­rowanych wcześniej funkcji BD, które w dalszej kolej­ności wywołują wszystkie cztery funkcje z pomniej­szonym o 1 argu­mentem. Wyjściem z tej patowej, wydawałoby się, sytuacji jest poprze­dzenie tych czterech definicji funkcji ich prototypami:

void A(int);
void B(int);
void C(int);
void D(int);

(pierwszy można pominąć, gdyż określa go definicja funkcji A). Teraz już można sformu­łować fragment kodu źródłowego odpowia­dającego podanemu wyżej wzorcowi kreślenia całej krzywej Sierpiń­skiego rzędu n:

A(n);  linerel(h, h);
B(n);  linerel(-h, h);
C(n);  linerel(-h, -h);
D(n);  linerel(h, -h);

Pełny program rysujący krzywą Sierpiń­skiego rzędu n dla wczytanych z klawiatury parametrów n i h jest przedsta­wiony na poniższym listingu. Cztery rekuren­cyjne funkcje kreślenia krzywych składowych zostały nieco ulepszone poprzez użycie operatora dekremen­tacji (--) bezpośre­dnio w porówna­niach ich rzędu z zerem.

#include <iostream>
#include <graphics.h>

using namespace std;

int n;              // Rząd krzywej Sierpińskiego
int h;              // Przesunięcie jednostkowe pisaka

bool dane()
{
    cout << "Krzywa Sierpińskiego\n--------------------\n";
    cout << "n (od 0 do 8): ";
    if (!(cin >> n) || n < 0 || n > 8)
        return false;
    int hMax = 1 << (8 - n);
    cout << "h (od 1 do " << hMax << "): ";
    return (cin >> h) && h > 0 && h <= hMax;
}

void A(int);
void B(int);
void C(int);
void D(int);

void A(int n)
{
    if (n-- > 0)
    {
        A(n);  linerel(h, h);
        B(n);  linerel(2 * h, 0);
        D(n);  linerel(h, -h);
        A(n);
    }
}

void B(int n)
{
    if (n-- > 0)
    {
        B(n);  linerel(-h, h);
        C(n);  linerel(0, 2 * h);
        A(n);  linerel(h, h);
        B(n);
    }
}

void C(int n)
{
    if (n-- > 0)
    {
        C(n);  linerel(-h, -h);
        D(n);  linerel(-2 * h, 0);
        B(n);  linerel(-h, h);
        C(n);
    }
}

void D(int n)
{
    if (n-- > 0)
    {
        D(n);  linerel(h, -h);
        A(n);  linerel(0, -2 * h);
        C(n);  linerel(-h, -h);
        D(n);
    }
}

int main()
{
    if (dane())
    {
        initwindow(800, 600, "Krzywa Sierpińskiego");
        int a = ((1 << (n + 2)) - 2) * h;
        int dx = (getmaxx() - a) / 2;
        int dy = (getmaxy() - a) / 2;
        moveto(((dx < 0) ? 4 : dx) + h, (dy < 0) ? 4 : dy);
        A(n);  linerel(h, h);
        B(n);  linerel(-h, h);
        C(n);  linerel(-h, -h);
        D(n);  linerel(h, -h);
        getch();
        closegraph();
        return 0;
    }
    else
    {
        cout << "Problem z danymi" << endl;
        return 1;
    }
}

Opracowanie przykładu: kwiecień 2019