Was bitteschön sind die Türme von Hanoi? Nunja, das ist eigentlich schnell erklärt. Bei den Türmen von Hanoi handelt es sich um 3 Türme, wobei auf einen dieser Türme 64 Goldscheiben liegen, diese 64 Scheiben sollen also auf einen der anderen 2 Türme verschoben werden. Die eigentliche Geschichte handelt von einem Mönch, dem wenn es gelingen würde alle 64 Scheiben zu verschieben, dass dann das Ende der Welte gekommen wäre. Dabei gelten folgende Regeln:
Die Frage ist nun, wie setzt man das so um, dass man es in einer Programmiersprache verwenden kann. Dazu wurde ein rekursiver Algorithmus gefunden, der wie folgt aussieht:
funktion bewege (Zahl i, Stab a, Stab b, Stab c) {
falls (i > 0) {
bewege(i-1, a, c, b);
verschiebe oberste Scheibe von a nach c;
bewege(i-1, b, a, c);
}
}
In anbetracht der Komplexität und Aufwendigkei 64 Scheiben nach diesen Regeln auf einen anderen Turm zu verschieben, ist die Funktion sehr sehr einfach (was man vielleicht nicht erwartet hätte).
Ich habe vor etwas längerer Zeit ein PHP-Script dazu geschrieben, welches auch noch die einzelnen Verschiebungen anzeigt (also Scheibe $x nach Turm $y verschieben). Das Script ist aber auf 12 Scheiben beschränkt, da es ansonsten zuviel Speicher des Browsers kosten würde.
Das Script ist hier zu finden.