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

Przykład C++

Gra w chaos Liczby losowe Program w C++ Przekazywanie parametrów przez wartość i referencję Algorytm IFS Program w C++ (wersja 2) Poprzedni przykład Następny przykład Program w Visual C# Kontakt

Gra w chaos

Niekiedy bardzo proste algorytmy prowadzą do zaskaku­jących wyników. Jednym z nich jest opisany poniżej algorytm generowania obrazu nazywany grą w chaos. Rysunek utworzony na ekranie monitora zaskakuje szczególnie, ponieważ całe postępo­wanie jest oparte na losowości, czyli niemożności przewi­dywania, chaosie.

Algorytm gry w chaos jest rzeczywiście bardzo prosty. Na początku wybie­ramy na ekranie trzy punkty P0, P1P2 tak, by stanowiły wierz­chołki trójkąta równobo­cznego, oraz dowolny punkt Q0 (rys.). Jest to tzw. punkt wiodący. Następnie losujemy jeden z wierz­chołków trójkąta i w środku odcinka łączą­cego ten wierz­chołek z punktem Q0 zazna­czamy nowy punkt wiodący Q1. Ponownie losujemy wierz­chołek trójkąta i w środku odcinka o końcach w wylo­sowanym wierz­chołku i punkcie Q1 zazna­czamy kolejny punkt wiodący Q2. Losowanie wierz­chołka i zazna­czanie nastę­pnego punktu wiodącego dokładnie w połowie odcinka łączącego wyloso­wany wierz­chołek z poprze­dnim punktem wiodącym powtarzamy wiele razy. Na rysunku pokazano pięć począ­tkowych kroków, w których kolejnymi wyloso­wanymi wierz­chołkami były P1, P2, P1, P2, P0.

Jaki będzie rezultat wielokrotnego wyznaczania nastę­pnego punktu wiodącego i ryso­wania go na ekranie? Wydaje się oczywiste, że jeżeli punkt wiodący Q0 został wybrany na zewnątrz trójkąta P0P1P2, to i tak po niewiel­kiej liczbie kroków któryś z kolejnych punktów wiodących dostanie się do wnętrza trójkąta i każdy następny tam pozo­stanie. Można więc przypuszczać, że po dużej liczbie kroków itera­cyjnych punkty wiodące zapełnią cały trójkąt.

Liczby losowe

Symulacja zdarzeń losowych na komputerze wymaga odpowie­dniej funkcji generu­jącej liczby losowe. Należy jednak sobie uświadomić, że generator taki działa według ściśle określo­nego algorytmu, a dostar­czone przez niego liczby jedynie sprawiają wrażenie losowości. Bardziej stosowne jest więc nazywanie ich liczbami pseudo­losowymi. W językach C i C++ liczby pseudo­losowe można generować za pomocą bezargu­mentowej funkcji rand (plik nagłówkowy stdlib.h lub cstdlib). Funkcja zwraca liczbę całko­witą z przedziału od 0 do RAND_MAX (co najmniej 32767), którą zazwyczaj trzeba przekształcić do żądanego zakresu. Na przykład instrukcja

int k = rand() % 49 + 1;

przypisuje zmiennej k pseudolosową liczbę całko­witą ze zbioru {1,2,...,49}, zaś instrukcja

double x = double(rand()) / RAND_MAX;

przypisuje zmiennej x pseudolosową liczbę rzeczywistą z prze­działu [0,1]. Iteracyjne użycie funkcji rand daje ciąg liczb o rozkła­dzie jedno­stajnym. Należy pamiętać, że przed wykorzy­staniem genera­tora trzeba go zaini­cjować za pomocą funkcji srand, której argu­mentem jest wartość typu unsigned int stano­wiąca tzw. zarodek lub ziarno (ang. seed). Aby za każdym urucho­mieniem programu zarodek był inny, często określa się go jako liczbę sekund, jaka upłynęła od 1 stycznia 1970 roku, zwracaną przez funkcję time (plik nagłówkowy time.h lub ctime):

srand((unsigned)time(NULL));

Niezainicjowany generator daje taki sam ciąg liczb za każdym uruch­omieniem programu, co można wykorzy­stać podczas testo­wania programu.

Program w C++

Jednym ze sposobów tworzenia grafiki na ekranie monitora kompute­rowego jest składanie obrazu z podsta­wowych elementów grafi­cznych, takich jak punkty i odcinki, okręgi i elipsy, łamane i wielokąty, a także wypeł­nianie obszarów zadanym kolorem lub wzorcem. Na tej zasadzie działają proste programy konso­lowe korzysta­jące z biblioteki WinBGI. Rysunek wyswie­tlają w odrębnym oknie grafi­cznym będącym normalnym oknem w Windows z paskiem tytułowym i ramką otacza­jącą obszar roboczy stano­wiący powierz­chnię ryso­wania interpre­towaną jako fragment pierwszej ćwiartki prosto­kątnego układu współ­rzędnych z początkiem (0,0) w lewym górnym rogu, osią x skiero­waną w prawo i osią y w dół. Współ­rzędne punktów są liczbami całko­witymi, obszar roboczy jest domyślnie czarny, a wyima­ginowany pisak ma kolor biały.

Poniżej przedstawiony jest kod źródłowy programu realizu­jącego grę w chaos w oknie o rozmiarze obszaru roboczego 640x480 pikseli. Wysokość trójkąta równobo­cznego równa 440 pikseli została tak dobrana, by cały rysunek mieścił się w obszarze roboczym z margi­nesem 20 pikseli od góry i dołu (podstawa 508 pikseli, margi­nesy boczne po 66 pikseli). Tablice inicjali­zowane x i y zawierają współ­rzędne wierz­chołków trójkąta, zmienne a i b – współ­rzędne bieżą­cego punktu wiodącego, w indeks wyloso­wanego wierzchołka, a k – numer kolejnej iteracji. Program otwiera okno graficzne, losuje początkowy punkt wiodący należący do obszaru roboczego, wyznacza i rysuje za pomocą funkcji putpixel 50000 punktów wiodących w kolorze jasnotur­kusowym (LIGHTCYAN), a po wybraniu przez użytko­wnika dowolnego znaku na klawia­turze zamyka okno graficzne i kończy działanie. Faktycznie iteracja wykonywana jest ponad 50000 razy. Celem doda­tkowych pięciu począ­tkowych kroków jest pominięcie rysowania punktów, które mogą leżeć na zewnątrz trójkąta, zaburzając obraz końcowy.

#include <graphics.h>
#include <cstdlib>
#include <ctime>

int x[] = {320, 66, 574}, y[] = {20, 459, 459};
int n = 50000;

int main()
{
    srand((unsigned)time(NULL));
    initwindow(640, 480);
    int a = rand() % getmaxx();
    int b = rand() % getmaxy();
    for (int k = -5; k < n; k++)
    {
        int w = rand() % 3;
        a = (a + x[w]) / 2;
        b = (b + y[w]) / 2;
        if (k >= 0)
            putpixel(a, b, LIGHTCYAN);
    }
    getch();
    closegraph();
    return 0;
}

Rysunek utworzony przez program na ekranie monitora uświa­damia, jak zawodna może być intuicja. Wygene­rowany obraz przedstawia tzw. trójkąt Sierpiń­skiego. Jest on zbiorem punktów wyjątkowo uporządko­wanym, niemającym – wydawa­łoby się – nic wspólnego z chaosem i losowością. Obiekty tego typu nazywane są fraktalami. Ich podsta­wową cechą jest samopodo­bieństwo przeja­wiające się w tym, że część fraktala jest podobna do całości.

Przekazywanie parametrów przez wartość i referencję

Pojęcia parametr i argument są często używane zamiennie. Wypada zatem wyjaśnić, że słowo parametr powinno być stosowane dla zmiennej zadekla­rowanej w nagłówku funkcji, zaś argument dla faktycznej danej przeka­zywanej do para­metru w wywołaniu funkcji. Czasami dla takiego rozróż­nienia używa się bardziej sugesty­wnych zwrotów parametr formalnyparametr aktualny lub też argument formalnyargument aktualny. Podczas wywo­łania funkcji parametry aktualne są podsta­wiane w miejsce formalnych, po czym następuje przejście jej wykonania. Typy parame­trów aktu­alnych powinny być zgodne z typami odpowiada­jących im parame­trów formalnych. W języku C++ wyróżnia się dwa rodzaje przeka­zywania (podsta­wiania) para­metrów (argu­mentów):

Przekazywanie przez wartość polega na przesłaniu wartości parametru aktual­nego do odpowie­dniego parametru formal­nego, który jest trakto­wany jak zmienna lokalna zadekla­rowana na początku funkcji. Zmiana wartości takiej zmiennej wewnątrz funkcji nie ma już żadnego związku z para­metrem aktualnym. Ponieważ podsta­wienie wartości występuje najczęściej, wybierane jest domyślnie, gdy rodzaj przeka­zywania parame­trów nie został podany.

W poniższym przykładzie w momencie wywołania funkcji proc wartość 2 parametru aktual­nego p zostaje przypisana parame­trowi formal­nemu x i na tym kończy się związek pomiędzy tymi parame­trami. Zwiększenie wartości x o 10 nie powo­duje więc zmiany wartości p. Wynika stąd, że wyświe­tlanym wynikiem jest 2.

#include <stdio.h>

void proc(int x)
{
    x += 10;
}

int main()
{
    int p = 2;
    proc(p);
    printf("Wynik: %d\n", p);
    return 0;
}

Przekazywanie przez referencję polega na przesłaniu do funkcji refe­rencji do zmiennej (adresu obszaru pamięci przydzie­lonego zmiennej) pełniącej rolę para­metru aktualnego. Oznacza to, że parametr formalny zajmuje tę samą pamięć co parametr aktualny i zmiana jego wartości jest w istocie zmianą wartości orygi­nalnej zmiennej. Przekazy­wanie przez refe­rencję wymaga umieszczenia znaku & przed parametrem formalnym.

W sformułowanym ponownie przykładzie parametr formal­ny x został poprzedzony znakiem &. Zatem przekazana do funkcji proc zmienna p o wartości 2 jest utożsa­miana wewnątrz funkcji z para­metrem x, przez co zwiększenie wartości x o 10 jest w rzeczywi­stości zwiększe­niem wartości p o 10. Wyświe­tlanym wynikiem jest więc 12.

#include <stdio.h>

void proc(int &x)
{
    x += 10;
}

int main()
{
    int p = 2;
    proc(p);
    printf("Wynik: %d\n", p);
    return 0;
}

Wypada przy okazji dopowiedzieć, że w języku C parametry można przeka­zywać jedynie przez wartość. Jak zatem wywołana funkcja ma zmienć wartość zmiennej należącej do funkcji wywołu­jącej? Jedynym sposobem na osiągnięcie tego celu jest przeka­zanie wskaźnika na zmienną, której wartość ma być zmieniona. Ilustruje to poniższy przykład.

#include <stdio.h>

void proc(int *x)
{
    *x += 10;
}

int main()
{
    int p = 2;
    proc(&p);
    printf("Wynik: %d\n", p);
    return 0;
}

Operator & daje adres zmiennej, zatem &p jest wskaźni­kiem na zmienną p. Jego wartość zostaje przeka­zana do para­metru x funkcji proc zadekla­rowanego jako wskaźnik. Zmienna *x wskazywana przez wskaźnik x zajmuje więc tę samą pamięć co zmienna p, toteż zwiększenie wartości *x o 10 jest de facto zwiększe­niem wartości p o 10. Z tego wynika, że wyświe­tlanym wynikiem jest 12.

Algorytm IFS

Wiele obrazów fraktalnych można wygenerować iteracyjnie, korzy­stając z tzw. układu itero­wanych odwzo­rowań (ang. Iterated Function System – IFS). W przy­padku trójkąta Sierpiń­skiego układ IFS składa się z trzech odwzorowań, które punktom (x, y) o współ­rzędnych rzeczy­wistych przyporzą­dkowują punkty (x', y') według następu­jących wzorów:

Każde z nich przekształca kwadrat jedno­stkowy [0,1]x[0,1] w odrębny kwadrat o boku dwukro­tnie mniej­szym zawarty w tym kwa­dracie jedno­stkowym (rys.). Star­tując od dowol­nego punktu płaszczyzny, można za pomocą powyż­szego układu odwzo­rować go w obraz 3 punk­towy, który w nastę­pnym kroku można odzwo­rować w obraz 32 punk­towy, a ten z kolei w obraz 33 punk­towy itd. Taki algorytm jest jednak niepra­ktyczny, gdyż wymaga zapamię­tania bardzo dużej liczby punktów, która wzrasta trzykro­tnie wraz z przejściem do nastę­pnego kroku.

Aby uniknąć kłopotów związanych z zapamię­taniem dużej liczby punktów obrazu, algorytm stosujemy nie do obrazów, lecz do pojedyn­czych punktów, wprowa­dzając element chaosu. Miano­wicie w każdym kroku wybieramy losowo jedno z trzech odwzo­rowań i za jego pomocą przekształ­camy poprzedni punkt. Na początku wybieramy losowo punkt należący np. do kwadratu [0,1]x[0,1]. Następnie losujemy jedno odwzoro­wanie spośród f0, f1, f2 i przekształ­camy ten punkt przez wyloso­wane odwzoro­wanie. Losowanie odwzoro­wania i przekształ­canie punktu powta­rzamy wiele razy. Otrzy­many ciąg punktów, po pomi­nięciu wyświe­tlania ich niewiel­kiej liczby na początku, by nie zabu­rzały obrazu końcowego, tworzy trójkąt Sierpiń­skiego zawarty w kwa­dracie [0,1]x[0,1]. Przedsta­wienie go na ekranie monitora kompute­rowego wymaga stoso­wnego przeska­lowania i przesu­nięcia.

Zmodyfikowany algorytm IFS najwygodniej jest zapisać w języku C++ w postaci funkcji, której dwa parametry x i y typu double są przeka­zywane przez refe­rencję. Funkcja dostaje w nich współ­rzędne punktu, a po wyzna­czeniu nowego punktu poprzez wyloso­wane odwzoro­wanie zwraca w nich jego współ­rzędne. Wyboru wyloso­wanego wariantu obliczeń można dokonać za pomocą podwójnej konstru­kcji if-else:

void ifs(double &x, double &y)
{
    int los = rand() % 3;
    if (los == 0)
    {
        x = 0.5 * x;
        y = 0.5 * y;
    }
    else if (los == 1)
    {
        x = 0.5 * x + 0.5;
        y = 0.5 * y;
    }
    else
    {
        x = 0.5 * x + 0.25;
        y = 0.5 * y + 0.5;
    }
}

Wielowariantowe decyzje można również podejmować, korzy­stając z instru­kcji switch, która sprawdza, czy wartość pewnego wyrażenia pasuje do jednej ze stałych wyszczegól­nionych po słowie kluczowym case (przypadek). Jeżeli tak, dalsze wyko­nanie programu rozpo­czyna się od miejsca oznaczo­nego tą stałą. Oto taka sama funkcja, w której użyto instru­kcji switch zamiast if-else:

void ifs(double &x, double &y)
{
    switch(rand() % 3)
    {
        case 0:
            x = 0.5 * x;
            y = 0.5 * y;
            break;
        case 1:
            x = 0.5 * x + 0.5;
            y = 0.5 * y;
            break;
        case 2:
            x = 0.5 * x + 0.25;
            y = 0.5 * y + 0.5;
    }
}

Wartością wyrażenia w powyższej instrukcji switch mogą być tylko stałe 0, 1 i 2, dlatego zawiera ona trzy człony case określa­jące warianty obliczeń współrzę­dnych kolej­nego punktu. Instrukcja break jest bardzo ważna, gdyż powoduje natychmia­stowe wyjście z instrukcji switch. Jej brak spowodo­wałby, że po wyko­naniu instrukcji związa­nych z jednym przypadkiem nastąpi­łoby przejście do wykonania instrukcji związanych z nastę­pnym przypadkiem. Na przykład gdyby w funkcji ifs pominąć obie instrukcje break, działa­łaby ona poprawnie tylko w przy­padku wyloso­wania liczby 2.

Przechodzenie od jednego do drugiego przypadku w instrukcji switch bywa niekiedy przy­datne. Sytuacja taka ma np. miejsce w poniż­szej funkcji zwraca­jącej liczbę dni miesiąca m roku r (alterna­tywnym rozwią­zaniem jest funkcja dmax zawarta w module obli­czeń kalenda­rzowych):

int dmies(int m, int r)
{
    switch(m)
    {
        case 2:             // luty
            if ((r % 4 == 0 && r % 100 != 0) || r % 400 == 0)
                return 29;
            else
                return 28;
        case 4:             // kwiecień
        case 6:             // czerwiec
        case 9:             // wrzesień
        case 11:            // listopad
            return 30;
        default:            // pozostałe miesiące
            return 31;
    }
}

Tym razem do opuszczania instrukcji switch użyto instrukcji return, która dodatkowo kończy funkcję i określa jej wartość zwracaną do punktu wywo­łania. Przypadek default zostanie wykonany wtedy, gdy żadna ze stałych występu­jących po słowie case nie jest zgodna z war­tością zmiennej m pełniącej rolę wyra­żenia w instrukcji switch.

Program w C++ (wersja 2)

W zaprezentowanej poniżej drugiej wersji programu genero­wania trójkąta Sierpiń­skiego wykorzy­stano funkcję ifs realizu­jącą jeden krok itera­cyjny zmodyfi­kowanego algo­rytmu IFS. Otrzymy­wane w kolejnych 50000 krokach punkty, oprócz pięciu dodatko­wych na początku, są wyświe­tlane w kolorze niebieskim (BLUE) na białym tle (WHITE) obszaru roboczego okna grafi­cznego o nazwie Trójkąt Sierpiń­skiego. Operacja ta wymaga przekształ­cenia współ­rzędnych punktu (x, y) leżącego w kwadracie [0,1]x[0,1] na współ­rzędne punktu (x', y') obszaru robo­czego o rozmiarze 640x480 pikseli. Uwzglę­dniając marginesy lewy i prawy o szero­kości 66 pikseli oraz dolny i górny 20 pikseli, a także odwrotny kierunek osi y układu ekranowego, otrzy­mujemy następujący związek między starymi i nowymi współ­rzędnymi:

Współczynniki skalujące 508 i 440 wyrażają w pikselach, podobnie jak w pierwszej wersji programu, długości boków prosto­kąta, w którym mieści się równo­boczny trójkąt Sierpiń­skiego.

#include <graphics.h>
#include <cstdlib>
#include <ctime>

int n = 50000;

void ifs(double &x, double &y)
{
    switch(rand() % 3)
    {
        case 0:
            x = 0.5 * x;
            y = 0.5 * y;
            break;
        case 1:
            x = 0.5 * x + 0.5;
            y = 0.5 * y;
            break;
        case 2:
            x = 0.5 * x + 0.25;
            y = 0.5 * y + 0.5;
    }
}

int main()
{
    srand((unsigned)time(NULL));
    initwindow(640, 480, "Trójkąt Sierpińskiego");
    setbkcolor(WHITE);
    cleardevice();
    double x = double(rand()) / RAND_MAX;
    double y = double(rand()) / RAND_MAX;
    for (int k = -5; k < n; k++)
    {
        ifs(x, y);
        if (k >= 0)
            putpixel(int(508 * x) + 66, 459 - int(440 * y), BLUE);
    }
    getch();
    closegraph();
    return 0;
}

Poniższy rysunek prezentuje wynik wykonania programu.


Opracowanie przykładu: listopad/grudzień 2018