Hanojské věže

Typické využití rekurzivní funkce

Animace

Hanojské věže je matematický hlavolam, který vymyslel francouzský matematik Édouard Lucas v roce 1883. Skládá se ze tří kolíků (věží). Na začátku je na jednom z nich nasazeno několik kotoučů různých poloměrů, seřazených od největšího (vespod) po nejmenší (nahoře). Úkolem řešitele je přemístit všechny kotouče na druhou věž (třetí přitom využije jako pomocnou pro dočasné odkládání) podle následujících pravidel:

V jednom tahu lze přemístit jen jeden kotouč.
Jeden tah sestává z vzetí vrchního kotouče z některé věže a jeho položení na vrchol jiné věže.
Je zakázáno položit větší kotouč na menší.

Vypráví se legenda, že někde ve Vietnamu nebo Indii stojí klášter nebo chrám, v němž jsou hanojské věže se 64 zlatými kotouči. Mniši (kněží) každý den v poledne za zvuku zvonů slavnostně přemístí jeden kotouč (v jiných verzích probíhá přemisťování nepřetržitě). V okamžiku, kdy bude přemístěn poslední kotouč, nastane konec světa. Vyřešení tohoto hlavolamu pro 64 kotoučů však vyžaduje \(2^{64}−1=18\,446\,744\,073\,709\,551\,615\) tahů, takže i kdyby mniši stihli provést jeden tah každou sekundu (a postupovali nejkratším možným způsobem), trvalo by jim vyřešení celého hlavolamu přibližně 600 miliard let. Při jednom tahu denně pak 50,5 biliard let (\(5 \cdot 10^{16}\)).


<?php
    function presun($n, $odkud, $kam, $kudy){
        if($n==1) {        
            $i = $i++;
            echo "$odkud > $kam <br>"; 
        } else {
            presun($n-1, $odkud, $kudy, $kam);
            presun(1, $odkud, $kam, $kudy);
            presun($n-1, $kudy, $kam, $odkud);
        }  
    }

    $kotoucu = 3; //počet kotoučů
    $celkem = 2**$kotoucu-1;
    echo "<p>Počet kotoučů: $kotoucu.<br>Bude potřeba $celkem tahů.</p>";
    presun($kotoucu, "levý", "pravý", "prostřední");
?>