02_rekurze

Robot2

Je slovo palindrom?

• Palindrom - text, který je stejný při čtení zepředu i 

zezadu

• Obecně tedy test symetrie, může být i s tolerancí
• Předávání tří parametrů - rychlé plnění zásobníku, dá se 

zmenšit počet parametrů ?

Palindrom (text, začátek, delka)

Pokud je delka 1 nebo 0 znaků vrať true

Pokud nejsou první a poslední stejné vrať false

Zavolej fci Palindrom (text, začátek+1, delka-2)

Půlení intervalů

• je možné ji považovat za grafickou metodu
• hledání kořenů rovnic (průsečík s nulou), nebo pro extrémy
• průsečík s nulou – máme-li kladnou a zápornou hodnotu (spojité 

rovnice), musí mezi nimi být průsečík s nulou (kořen)

• vypočteme hodnotu uprostřed stávajících a nahradíme jí tu se 

stejnou polaritou hodnoty

• ukončení při dostatečně přesném přiblížení k průsečíku s nulou

• našli jsme přímo nulu

• ukončení pro hodnotu y v dané toleranci od nuly („strmé“ průsečíky)

• ukončení pro danou vzdálenost krajních bodů od sebe („ploché“ 

průsečíky)

• ukončení z důvodu velkého množství kroků

Půlení intervalů - algoritmus

vstup – dvě souřadnice x a funkce y = f(x)

vypočteme hodnoty v krajních bodech x

tolerance hodnota = velká

dokud tolerance hodnoty = velká

-vypočti souřadnici x uprostřed mezi

krajními body

-vypočti hodnotu y v tomto bodě

-nahraď krajní bod, který má hodnotu se 

stejným znaménkem, vypočteným středem

-spočítej novou tolerance hodnoty

výsledek je x s menší hodnotou

Hanojské věže

• Demonstrace úlohy:

• máme tři pozice a na první je pyramida ze 4 (například) 

disků

• úkolem je přesunout disky na poslední pozici
• podmínky řešení

• disky přenášíme po jednom
• nesmíme umístit větší disk na menší

• Zkuste tuto úlohu vyřešit
• Jak postupovat?

Hanojské věže

• Možné řešení:

• přenes všechny disky až na spodní disk na pomocnou 

pozici

• přesuň zbývající spodní disk na cílovou pozici
• přenes disky (přenášené v prvním kroku) z pomocné