02_rekurze

pozice na cílovou 

• Jak přenést všechny disky až na spodní ?

• výška pyramidy = výška pyramidy -1
• zavolám stejný algoritmus

• Nepřipomíná vám to něco?

Hanojské věže - algoritmus

Vstup:

počet disků
označení pozicí: Zdroj, Pomocná, Cíl

Algoritmus:

Pokud je více jak jeden disk

Přesun(počet disků-1; pozice Zdroj, Cíl, Pomocný)

Zbývající samostatný disk ze Zdroj do Pomocný

Pokud je více jak jeden disk

Přesun(počet disků-1; pozice Cíl, Pomocný, Zdroj)

Hanojské věže - příklad

XIX      I       I

XXIXX     I       I

XXXIXXX    I       I

0->2

I       I

I

XXIXX     I       I

XXXIXXX    I      XIX

0->1

I       I

I

I

I

I

XXXIXXX  XXIXX    XIX

2->1

I       I

I

I

XIX      I

XXXIXXX  XXIXX     I

0->2

I       I

I

I

XIX      I

I

XXIXX  XXXIXXX

1->0

I       I

I

I

I

I

XIX    XXIXX  XXXIXXX

1->2

I       I

I

I

I

XXIXX

XIX      I    XXXIXXX

0->2

I       I

XIX

I       I

XXIXX

I       I

XXXIXXX

Hornerovo schéma

• použití

• zjištění hodnoty polynomiální funkce v bodě

• při převodu mezi číselnými soustavami

• hodnota polynomu

𝑓 𝑥 = 𝑎𝑛𝑥𝑛 + 𝑎𝑛−1𝑥𝑛−1 + ⋯ + 𝑎1𝑥 + 𝑎0

• v tomto vyčíslení je (n-1) násobení a (n-1) sčítání. Dále je nutné 

získat mocniny x (při iterativním počítání dalších n operací; při 

každé mocnině n^2/2).

• při úpravě Hornerových schématem:

𝑓 𝑥 = (. . ((𝑎𝑛𝑥 + 𝑎𝑛−1)𝑥 + ⋯ + 𝑎1)𝑥 + 𝑎0

• zůstane počet násobení a sčítání, není ale nutné počítat mocniny. 

Tím se také ušetří pomocná proměnná.

• Převeďte tento algoritmus na rekurentní