analyse
Het is vrij makkelijk aan te tonen dat het aantal benodigde zetten hiervoor gelijk is aan 2N-1, waarbij N het aantal schijven is. Het is een geliefd probleem in programmeercursussen, omdat het zeer elegant op recursieve wijze op te lossen is.
De oplosfunctie kan in pseudocode zo worden geformuleerd:
functie hanoi (aantal, bronstok, doelstok); {
- als (aantal gelijk is aan 1),
- plaats dan de schijf op bronstok naar doelstok;
- anders
- hanoi ((aantal-1), bronstok, derde stok);
- hanoi (1, bronstok, doelstok));
- hanoi (aantal -1, derde stok, doelstok);
} Hieraan is ook meteen te zien dat de oplossing voor 1 schijf 1 zet vergt, en voor een grotere toren 1 + tweemaal die van de 1 schijf kleinere toren.
1 schijf -> 1 zet 2 schijven -> 2*1 + 1 = 3 zetten 3 schijven -> 2*3 + 1 = 7 zetten 4 schijven -> 2*7 + 1 = 15 zetten
Het aantal zetten is steeds het dubbele aantal van de vorige stapel + 1. Bij met de hand oplossen geldt de volgende regel: bij het verplaatsen van een (sub)torentje naar een andere stok moet men de eerste zet naar die doelstok doen bij een oneven aantal schijven, en naar de derde stok bij een even aantal schijven. (Het 'subtorentje' is steeds het grootst mogelijk aan te geven torentje zonder ontbrekende schijven erin).
oorsprong
Het spel is uitgevonden door de Franse wiskundige Edouard Lucas in 1883. Er is een legende over een Hindoe-tempel waarvan de priesters, de Brahmanen, zich bezighouden met het verplaatsen van een toren van 64 gouden schijven. Volgens de legende komt de wereld tot een einde als het werk af is. Het is niet duidelijk of Lucas deze legende bedacht heeft of er alleen door is geïnspireerd.
Aannemend dat de priesters 1 schijf per seconde zouden verplaatsen, zou het ongeveer 264 - 1, is ongeveer 1.8×1019 seconden duren de puzzel af te maken. Dit komt overeen met ongeveer 580.000.000.000 jaar, ruwweg veertig maal langer dan de geschatte leeftijd van het universum.
Asimov
Isaac Asimov heeft dit spel als onderwerp van een van zijn korte verhalen genomen, waarbij ook weer een aantal monniken in een klooster in het verre oosten al eeuwenlang bezig zijn een stapel schijven van 64 hoog te verplaatsen. Als het af is, houdt het universum volgens de overlevering op te bestaan. Twee computerprogrammeurs schrijven het programma en...
externe links
Geschiedenis: JAVA simulatie:
