Příběh: V jednom indickém chrámu mají tři věže — Věž zrození, Věž života a Věž zkázy. Uvnitř každé z nich je kůl, na kterém je navlečeno několik zlatých disků. Ve všech třech věžích je dohromady 64 disků. Každý disk je jinak široký. Disky smí být na kůlu navlečeny pouze tak, že menší a užší disk leží na širším. Jinak to prý přinese smůlu. Proto každý kůl spolu s disky vypadá jako kužel.

Při stvoření chrámu byly všechny disky navlečeny na jeden kůl ve Věži stvoření. Kněží, kteří v chrámu přebývají, každý den přesunou jeden disk (víc jich přesunout nesmí) tak, aby se jim co nejdříve podařilo přesunout všechny disky na kůl ve Věži zkázy. Jinak by se zastavilo plynutí života. Stará legenda říká, že až se jim to podaří, tak nastane konec světa.

Úkol pro Vás: Dokázali byste napsat program, který kněžím vypíše instrukce, jak mají disky přesunovat? Už jsou z toho celí zmatení a moc by jim to pomohlo. Na začátku jsou všechny disky navlečeny na první kůl a máte je přestěhovat na poslední kůl.

Pokud se budeme držet zásady rozděl a panuj, tak zkusíme problém rozložit na podproblémy, jejichž vyřešení přehodíme na někoho jiného (třeba na rekurzi). Abychom mohli největší disk přesunout na správné místo, tak nejprve necháme všechny menší disky přestěhovat na třetí odkládací tyčku. Pak přesuneme největší disk. Na závěr necháme všechny odložené disky přesunout nad největší disk.

Hanoj($n,$ $odkud,$  $pres,$  $kam$ )
      if $n\geq 1$ then 
            Hanoj($n-1,$  $odkud,$  $kam,$  $pres$ ) 
            Vypiš("Přeneste disk z ",odkud," do  ", kam) 
            Hanoj($n-1,$  $pres,$  $odkud,$  $kam$ )

Jaká je časová složitost tohoto algoritmu? Ta je úměrná tomu, kolikrát budou muset kněží přenést nějaký disk. Označme celkový počet přenesení disků pomocí $T(n)$. Z uvedeného algoritmu je vidět rekurence $T(n)=2T(n-1)+1$. Rekurenci můžeme vyřešit například postupným rozepisováním. Dostaneme \begin{align*} & T(n) = 2T(n-1)+1 = 2(2(T(n-2)+1)+1 = \\ &= 2(2(2\cdots(2T(1)+1)\cdots +1)+1)+1 = 2^n+2^{n-1}+\cdots+2+1=2^{n+1}. \end{align*}

Takže časová složitost algoritmu Hanoj je exponenciální. Legenda říká, že disků je $64$. Jestliže byl chrám založen zhruba před $3000$ lety, dokážete určit kdy nastane konec světa? Má smysl se toho obávat?