Tornen i Hanoi

Från Wikipedia
Hoppa till: navigering, sök
Tornen i Hanoi
Animation av Tornen i Hanoi

Tornen i Hanoi (Tornet i Hanoi) är ett matematiskt problem som också finns i skepnad av spel eller patiens.

Problemet/spelet består av tre vertikala pinnar fästa på en platta. På den vänstra pinnen sitter n stycken platta cirkulära skivor med hål i. Dessa skivor är olika stora och sorterade i storleksordning med den största underst. Spelet går ut på att flytta över hela stapeln till högra pinnen likadant sorterad. Mellanpinnen är bara hjälppinne. Varje drag utgörs av att flytta en skiva till en annan pinne med restriktionen att man får inte lägga en större skiva på en mindre. På en tom pinne får man lägga vilken skiva som helst. Problemet är lösbart oavsett värdet på n (ett naturligt tal).

Den optimala lösningen (dvs minsta möjliga antalet drag) med n stycken skivor är 2n - 1 drag. Denna formel kan härledas med hjälp av en rekursiv differensekvation. Det finns ingen känd formel för minsta möjliga antalet drag om man generaliserar spelet till att innefatta godtyckligt antal (≥3) pinnar.

Det finns också en patiens inspirerad av detta problem (se även kortspel).

Se även[redigera | redigera wikitext]