Tornen i Hanoi
Från Rilpedia
Tornen i Hanoi (Tornet i Hanoi) är ett matematiskt problem som också finns i skepnad som 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. De är sorterade i storleksordning med den största underst. Det går ut på att flytta över hela stapeln till högra pinnen likadant sorterad. Mellanpinnen är bara hjälppinne. Varje drag består i att flytta en skiva till en annan pinne med den 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 (positivt heltal).
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 rekursion. 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
- matematiskt spel
- Hanoi (staden)
