IB111 – cv. 9
Rekurze
Miroslav Kadlec
Obsah
● Opakování rekurze
● Faktoriál
● Fibonacciho posloupnost
● Hanojské věže
● Fraktály
● Co to je
● Jak to nakreslíme
Opakování rekurze
● Obecně umíme něco spočítat/vyjádřit/provést
● Pro malou hodnotu/počet (případně hodnoty)
– Tyto případy napíšeme do kódu přímo, explicitně
● Pro větší hodnotu výpočet provést s použitím výsledku
výpočtu pro menší hodnotu
● Faktoriál
● fact(0) = 1
● fact(x) = x * fact(x – 1)
● Fibonacci
● fib(0) = 0, fib(1) = 1
● fib(x) = fib(x – 1) + fib(x - 2)
Hanojské věže
● Definice úlohy
● Máme 3 kůly, na něž lze navlékat disky (A, B, C)
● Máme X různě velkých disků
● Na počátku jsou disky navlečeny na prvním kůlu, největší je
dole a každý menší je o něco výš, tvoří jakousi pyramidu
● Úkol
● Přesunout všechny disky na třetí kůl tak, aby byly stejně
uspořádány.
● Pravidla
● Vždy přesouváme jen 1 disk najednou
● Vždy můžu vzít jen nejvyšší disk z některého kůlu
● Nikdy nemůžeme položit větší disk na menší
Hanojské věže
● Jak budeme postup reprezentovat?
● Vypisovat jen "tahy" (A -> C znamená přesun
nejvyššího kotouče z A)
– pak si musíme počítačem nalezený postup v hlavě projít
a zkontrolovat
● Vypisovat i stav
● Postup – analýza pro malé počty pater
● Umíme zapsat případ s jen 1 patrem?
● Jak vypadá případ se 2 patry?
Hanojské věže
● U případu se 3 patry
● Využijme přesun dvoupatrové pyramidy, kterou už
umíme
– 1) přesuneme horní dvoupatrovou z A na B
– 2) přesuneme největší disk z A na C
– 3) přesuneme dvoupatrovou z B na C
● To nejspíš půjde, ok, umíme i třípatrovou
● U případu s X patry
– 1) přesuneme horní (X-1)patrovou z A na B
– ...
Fraktály
● Na pohled celkem složité obrazce s poměrně jednoduchou
matematickou strukturou
● Díky této struktuře se dají generovat rekurzivní funkcí
● Příklad – strom
● Pro délky > minimální délka větvě:
– 1) kreslím čáru
– 2) pootočím se a vykreslím strom s menší délkou
– 3) pootočím se a vykreslím 2. strom s menší délkou
– 4) pootočím se a vrátím se zpět po čáře z bodu 1)
● Pro délky < minimální délka větvě:
– Nekreslím nic
● Navíc – vložme do kreslení stromu náhodnost tak, aby byl
méně pravidelný, ale pořád připomínal strom
Fraktály
● Kochova vločka
● Má definovanou velikost a hloubku zanoření (= do
jakých detailů kreslíme)
– Velikost můžeme definovat napevno tak, aby se nám
vždycky vešla na plátno
– Hloubka:
● Hloubka == 0
– Pouze rovná čára
Fraktály
● Hloubka == X
– Vždycky vykreslíme kochovu křivku s
● Menší hloubkou
● Menší velikostí
● Vhodně zatočíme
– A to samé ještě 3x
● Kochovu křivku můžeme vnímat jako třetinu "celé
kruhové" sněhové vločky