Phänomenta: staunen – forschen – begreifen

Turm von Hanoi
Können Sie die Platten nach und nach einzeln von einem Stab auf den anderen legen, ohne dass jemals eine größere über einer kleineren Platte liegt?

Mit 31 Schritten lässt sich das Problem lösen, wenn 5 Scheiben umgestapelt werden müssen. Das bekannte Knobelspiel ist schon sehr alt, aber immer wieder aktuell. So ist es eine Grundaufgabe für angehende Informatiker ein möglichst kurzes, so genanntes rekursives Programm zu schreiben, das dieses Problem löst.

Wird übrigens nur eine Scheibe mehr verwendet, so steigt die Zahl der benötigten Züge schon auf 63. Bei 64 Scheiben sind es 9.223.372.036.854.775.808 Züge, allgemein sind es 2 hoch (Anzahl der Scheiben -1) Züge.

Lösungsstrategie (rekursiv, Pseudocode):

Rezept R ("Versetze Turm T auf Ziel Z"):

Wenn der aktuelle Turm T nur noch 1 Scheibe groß ist
setze ihn direkt auf das aktuelle Ziel Z: fertig.
sonst
1. versetze (mit demselben Rezept R) den Teilturm TT, der aus allen außer der untersten Scheibe des aktuellen Turms besteht, zu dem Zwischenziel ZZ, das nicht das Ziel Z für T ist,
2. lege dann die verbliebene unterste Scheibe von T an das Ziel Z und
3. versetze (mit demselben Rezept R) den vorher versetzten Teilturm TT nun auf die soeben nach Z versetzte untere Scheibe!

Bitte beachten Sie unseren Disclaimer