Przeczytaj

Dzięki funkcjom rekurencyjnymrekurencjarekurencyjnym możemy uzyskać różne znane fraktalefraktalfraktale. Są to między innymi:

zbiór Cantora,
płatek Kocha,
dywan Sierpińskiego,
drzewo binarne.

Do tworzenia takich obrazów w języku Python doskonale nadaje się moduł turtleturtleturtle.

Ważne!

W funkcjach będziemy wykorzystywać obiekt klasy Turtle do utworzenia obiektu żółwia. Ponieważ funkcja rekurencyjna wywołuje samą siebie wielokrotnie, obiekt żółwia musi być do niej przekazany jako jeden z parametrów. W przeciwnym razie wyniki działania funkcji rekurencyjnej mogłyby być nieprzewidywalne.

from turtle import Turtle
zlw = Turtle() #definicja obiektu żółwia

def funkcja_rekurencyjna(obiekt_zolwia, ...):
    pass

# wywołanie
funkcja_rekurencyjna(zlw, ...)

Algorytm opisowy do generowania dywanu Sierpińskiego

Dywan Sierpińskiego otrzymujemy z kwadratu przez podzielenie go na dziewięć mniejszych kwadratów (3 x 3). Następnie środkowy kwadrat zostaje zamalowany. Ponownie rekurencyjnie wywołujemy tę funkcję dla każdego z pozostałych kwadratów.

Przykład 1

Spróbujmy zdefiniować algorytm tworzenia geometrycznej prezentacji:

dywan_sierpinskiego(stopien, dlugosc_boku)

    jeśli stopien jest równy 0
        narysuj kwadrat o dlugosc_boku w kolorze turkusowym
        zakończ
    w innym przypadku
        narysuj kwadrat o dlugosc_boku w kolorze białym
        powtórz 4 razy
            powtórz 2 razy
                wywołaj dywan_sierpinskiego(stopien-1, dlugosc_boku/3)
                przesuń się do przodu o dlugosc_boku/3

            przesuń się do przodu o dlugosc_boku/3
            obróć się w prawo o 90 stopni

Na podstawie powyższego opisu zapiszemy kod funkcji:

def dywan_sierpinskiego(z, stopien, dl_bok):

    def kwadrat(bok, kolor):
        z.color(kolor)
        z.begin_fill()
        for i in range(4):
            z.forward(bok)
            z.right(90)
        z.end_fill()

    if stopien == 0:
        kwadrat(dl_bok, 'black')
        return None
    else:
        kwadrat(dl_bok, 'white')
        for i in range(4):
            for j in range(2):
                dywan_sierpinskiego(z, stopien-1, dl_bok/3)
                z.forward(dl_bok/3)
            z.forward(dl_bok/3)
            z.right(90)

Efekt wykonania algorytmu wygląda następująco:

# poniższe wiersze niezbędne są dla wykonania
from turtle import Turtle
zl = Turtle()

# przenosimy żółwia w konkretne miejsce układu współrzędnych
# aby narysowany obraz dobrze mieścił się w oknie
zl.penup()
zl.goto(-300,300)
zl.pendown()

dywan_sierpinskiego(zlw, 3, 500)

R11c8pYfgKo8V

Zdjęcie ukazuje efekt wykonania algorytmu. Dywan Sierpińskiego w kształcie kwadratu. Z środka został usunięty zbiór w kształcie kwadratu, następnie dla kolejnych części usuwane są coraz mniejsze zbiory w kształcie kwadratów. — Dywan Sierpińskiego - efekt po wykonaniu kilku pierwszych kroków
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Algorytm opisowy do generowania zbioru Cantora

Zbiór Cantora to odcinek, z którego wycinamy część środkową, pozostawiając odcinki pierwszej i trzeciej części. Następnie analogicznie postępujemy z każdą z pozostałych części. W każdym kolejnym kroku liczba części odcinka zwiększa się dwukrotnie, a długość narysowanych odcinków maleje. Kolejne kroki narysowane jeden pod drugim tworzą układ fraktalny.

Przykład 2

Spróbujmy zdefiniować algorytm tworzenia geometrycznej prezentacji:

zbiór_cantora(długość_linii, wycięcie, liczba_linii)

    jeśli liczba_linii jest równa 0
        narysuj_odcinek_długości długość_linii
    w przeciwnym wypadku
        nowa_długość = długość_linii * ( ( 1 - wycięcie ) / 2 )
        przenieś_pisak
        zbiór_cantora(nowa_długość, wycięcie, liczba_linii - 1)
        przenieś_pisak o odległość ( długość_linii * wycięcie )
        zbiór_cantora(nowa_długość, wycięcie, liczba_linii - 1)

Opierając się na powyższym algorytmie, wykonamy implementację w języku Python. W tym celu wykorzystamy moduł turtle:

def zbior_cantora(z, dlugosc_linii, wyciecie, liczba_linii):
    if liczba_linii == 0:
        z.pd()
        z.fd(dlugosc_linii)
        z.pu()
    else:
        nowa_dlugosc = dlugosc_linii * (1-wyciecie)/2
        zbior_cantora(z, nowa_dlugosc, wyciecie, liczba_linii -1)
        z.fd(dlugosc_linii * wyciecie)
        zbior_cantora(z, nowa_dlugosc, wyciecie, liczba_linii -1)

Powyższy kod nie spowoduje jednak wyrysowania fraktala – brakuje w nim poleceń, które wywołałyby rysowanie na różnych poziomach. Musimy zatem napisać dodatkową funkcję, która pomoże w tworzeniu obrazu:

def fraktal_cantora(z, dlugosc_lini, ile):
    for i in range(ile):
        zbior_cantora(z, dlugosc_lini, 1/3, i)
        z.back(dlugosc_lini)
        z.lt(90)
        z.back(100 / ile - 1)
        z.rt(90)

Kod niezbędny do wyrysowania fraktala i wygenerowania obrazu to:

# poniższe wiersze niezbędne są dla wykonania
from turtle import Turtle
zlw = Turtle()

# wykonaj obraz
fraktal_cantora(zlw, 300, 5)

RiYi70fnyGR2o1

Zbiór Cantora - efekt po wykonaniu kilku pierwszych kroków. Jest to Linia, która w kolejnych rzędach dzieli się na dwie równe części. — Zbiór Cantora – efekt po wykonaniu kilku pierwszych kroków
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Algorytm opisowy do generowania płatka Kocha

Płatek Kocha powstaje w wyniku podziału odcinka na trzy części i usunięcia środkowej, a w jej miejsce wstawieniu trójkąta równobocznego o boku długości usuniętego odcinka. Taki algorytm stosujemy dla każdego fragmentu odcinka bazowego, a następnie dla każdego fragmentu każdego kolejnego pododcinka – i tak dalej. Taka figura może mieć nieskończoną długość, gdyż każdy podział tworzy cztery razy więcej odcinków niż poprzedni.

Przykład 3

Spróbujmy zdefiniować algorytm tworzenia geometrycznej prezentacji:

platek_kocha(stopien, dl_bok)

    bok(stopien, dl_bok)
        jeśli stopien wynosi 0 narysuj_odcinek_dlugosci dl_bok
        w innym przypadku
            bok(stopien-1, dl_bok/3)
            obróć żółwia w lewo o 60 stopni
            bok(stopien-1, dl_bok/3)
            obróć żółwia w prawo o 120 stopni
            bok(stopien-1, dl_bok/3)
            obróć żółwia w lewo o 60 stopni
            bok(stopien-1, dl_bok/3)

    obróć żółwia w prawo o 30 stopni
    powtórz 3 razy
        bok(stopien, dl_bok)
        obróć żółwia w prawo o 120 stopni

    obróć żółwia w lewo o 30 stopni

Na podstawie takiego opisu zapiszemy kod funkcji:

def platek_kocha(z, stopien, dl_bok):

    def bok(stopien, dl_bok):
        if stopien == 0:
            z.forward(dl_bok)
        else:
            bok(stopien-1, dl_bok/3)
            z.left(60)
            bok(stopien-1, dl_bok/3)
            z.right(120)
            bok(stopien-1, dl_bok/3)
            z.left(60)
            bok(stopien-1, dl_bok/3)

    z.right(30)
    for i in range(3):
        bok(stopien, dl_bok)
        z.right(120)

    z.left(30)

A oto efekt wykonania algorytmu:

# poniższe wiersze niezbędne są dla wykonania
from turtle import Turtle
zlw = Turtle()

platek_kocha(zlw, 3,200)

R1Ap30iRUGOu5

Płatek Kocha – efekt po wykonaniu kilku pierwszych kroków. Jest to figura w kształcie płatka śniegu, stworzona z jednej krzywej z ostrymi krawędziami. — Płatek Kocha – efekt po wykonaniu kilku pierwszych kroków
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Algorytm opisowy do generowania drzewa binarnego

Drzewo binarne to odcinek, który dzieli się na dwa kolejne, każdy rysowany pod kątem 45 stopni w lewo i 45 stopni w prawo. W ten sposób powstaje swego rodzaju „korona drzewa”. W kolejnym module tego e‑materiału znajdziesz prezentację multimedialną, dzięki której dokładnie prześledzisz proces powstawania tego fraktala.

Przykład 4

Spróbujmy zdefiniować algorytm tworzenia geometrycznej prezentacji:

drzewo_binarne(stopien, dlugosc_pnia)
    jesli stopien wynosi 0 to
        narysuj pień o długości dlugosc_pnia
        wróć do punktu początkowego
        zakończ
    w innym przypadku
        narysuj pień o długości dlugosc_pnia
        obróć żółwia w lewo o 45 stopni
        drzewo_binarne(stopien - 1, dlugosc_pnia / 2)
        obróć żółwia w prawo o 90 stopni
        drzewo_binarne(stopien - 1, dlugosc_pnia / 2)
        obróć żółwia w lewo o 45 stopni
        cofnij żółwia o dlugosc_pnia

Na podstawie powyższego opisu zapiszemy kod funkcji:

def drzewo_binarne(z, stopien, dl_bok):
    if stopien == 0:
        pozycja = z.pos()
        z.forward(dl_bok)
        z.goto(pozycja)
    else:
        pozycja = z.pos()
        z.forward(dl_bok)
        z.left(45)
        drzewo_binarne(z, stopien-1, dl_bok/2)
        z.right(90)
        drzewo_binarne(z, stopien-1, dl_bok/2)
        z.left(45)
        z.goto(pozycja)

Efekt wykonania algorytmu wygląda następująco:

# poniższe wiersze niezbędne są dla wykonania
from turtle import Turtle
zlw = Turtle()

# przenosimy żółwia w konkretne miejsce układu współrzędnych
# aby narysowany obraz dobrze mieścił się w oknie
zlw.penup()
zlw.goto(-20,-20)
zlw.pendown()
zlw.left(90)

drzewo_binarne(zlw, 3, 50)

RrBjln6KuCTGg

Drzewo binarne - efekt po wykonaniu kilku pierwszych kroków. Od korzenia, jedna linia dzieli się na dwie. Linie te dzielą się na dwie w każdym kolejnym kroku wykonania algorytmu. — Drzewo binarne - efekt po wykonaniu kilku pierwszych kroków
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Już wiesz

Podsumujmy najważniejsze elementy tego e‑materiału.

Fraktale to figury geometrycznie nieskończenie samopodobne.
Możemy przygotować funkcje rekurencyjne i wizualizować je za pomocą modułu turtle.
Obiekt żółwia przy funkcjach rekurencyjnych musimy tworzyć poza przestrzenią nazwprzestrzeń nazwprzestrzenią nazw funkcji.

Słownik

fraktal

(łac. fractus – złamany, cząstkowy, ułamkowy) obiekt składający się z coraz bardziej złożonych detali, z których każdy jest podobny do całości

przestrzeń nazw

(ang. namespace) miejsce w pamięci operacyjnej, w której jest przechowywana dana zmienna; najczęściej przestrzeń nazw wiąże się z funkcją, a zmienne używane w niej są widoczne tylko w obrębie tej przestrzeni – jest to „zakres obowiązywania” tych zmiennych

rekurencja

proces polegający na wywoływaniu funkcji przez siebie samą do momentu rozwiązania określonego zadania

turtle

(z ang. żółw) moduł (standardowa biblioteka) w języku Python realizujący grafikę żółwia

Wprowadzenie

Prezentacja multimedialna

Algorytm opisowy do generowania dywanu Sierpińskiego

Algorytm opisowy do generowania zbioru Cantora

Algorytm opisowy do generowania płatka Kocha

Algorytm opisowy do generowania drzewa binarnego

Słownik