Zielgerichtet spielen
Herausforderung ist, den Überblick zu behalten, so dass
die Zwischenschritte das Spiel wirklich weiter bringen. Bei wenigen Scheiben ist
dies einfach, ab n=4/5 wird es schon etwas kniffliger. Die folgende Abbildung
zeigt den Zwischenstand für 4 Scheiben nach 5 Zügen: (1AB, 2AC, 1BC, 3AB, 1CA)

Der Turm von 1-3 muss erst auf dem Hilfsbauplatz
aufgebaut werden, dann die Scheibe 4 auf den Zielbauplatz versetzt und
nachfolgend der Turm von 1-3
ebenfalls dort aufgebaut werden.
In der Ausgangssituation und immer, wenn man die
Scheibe 1 wieder setzt (was ausgesprochen oft der Fall ist ;-) ) ist immer die
Frage, welches der richtige Bauplatz ist. Es gibt begabte Leute, die dies intuitiv richtig
machen, andere (so wie ich) brauchen dafür eine Regel: Wenn n
ungerade ist, kommt die 1 auf den Zielbauplatz, sonst auf den Hilfsbauplatz.
Also für n=4 zu Beginn die 1 von A nach B setzen. In Zwischensituationen
hilft die Regel auch, den Überblick zu behalten, nur wechseln jeweils Ausgangsbauplatz
(wo die 1 dann aktuell steht), Zielbauplatz (wo der Teilturm aktuell
hin muss) und
Hilfsbauplatz.
Zurück zum Programm - zurück zum
Spiel
Wie arbeitet das Programm?
Wie kann man das am elegantesten für einen Computer programmieren? Die Strategie des Spiels ist, immer zunächst
den Turm von 1
bis n-1 auf den Hilfsbauplatz B zu versetzen, dann die größte Scheibe (n) von A nach C , und dann wiederum
den Teilturm bis n-1 von B nach C.
Wie mache ich die Zwischenschritte, um den Turm bis n-1
auf den Hilfsbauplatz zu setzen?
Nun, ganz
einfach, zunächst den Turm bis n-2 auf den Zielbauplatz, dann Scheibe n-1 auf
den Hilfsbauplatz, dann den Turm bis n-2 auf den Hilfsbauplatz.
Aha... Und wie geht das für n-3? Bei großen n bin ich ja
noch lange nicht fertig!
Naja, immer so weiter. Wir nehmen einfach an, wir können
das schon für n-1 und zählen n runter bis 1. 1 können wir versetzen, fertig. In
Pseudocode geschrieben:
Funktion Hanoi (n, Quelle, Ziel, Hilfe) {
wenn n=1
{
setze 1 von Quelle auf
Ziel;
}
sonst
{
Hanoi (n-1, Quelle,
Hilfe, Ziel);
setze n von Quelle
auf Ziel;
Hanoi (n-1, Hilfe, Ziel,
Quelle);
}
Dabei ruft die Funktion Hanoi() sich selbst immer wieder
auf, das nennt man Rekursion. Um erfolgreich zu sein, muss dies
terminieren, also irgendwann zuende sein. Da n herunter gezählt wird, ist das der Fall, man muss nur dafür
sorgen, dass n eine natürliche Zahl ungleich Null ist.