Zur Themenübersicht     

Türme von Hanoi

Bei den Türmen von Hanoi geht es darum, Steine verschiedener
Größe von einem Platz zu einem Anderen zu transportieren.

Hierbei gelten die folgenden Regeln:

Ein Beispiel mit drei Steinen

Ausgangsposition
Dieses ist die Ausgangsposition.

Alle Steine sind übereinander gestapelt, kein Stein liegt auf einem Kleineren.

Ausgangsposition

Zwischenspeicher

Endposition

Schritt #1
Der kleinste Stein wird von Position 1 (Ausgangsposition)
zu Position 3 (Endposition) verlegt.

Ausgangsposition

Zwischenspeicher

Endposition

Schritt #2
Der mittlere Stein wird von Position 1 (Ausgangsposition)
zu Position 2 (Zwischenspeicher) verlegt.

Wie sich sehen läßt, muß erst ein Turm der Höhe 1 transportiert werden, um einen Turm der Höhe 2 zu transportieren.

Ausgangsposition

Zwischenspeicher

Endposition

Schritt #3
Der kleinste Stein wird von Position 3 (Endposition)
zu Position 2 (Zwischenspeicher) verlegt.

Zu diesem Zeitpunkt liegt ein Turm der Höhe 2 im Zwischenspeicher.

Wie sich sehen läßt, muß erst ein Turm der Höhe 2 transportiert werden, um einen Turm der Höhe 3 zu transportieren.

Ausgangsposition

Zwischenspeicher

Endposition

Schritt #4
Der große Stein wird von Position 1 (Ausgangsposition)
zu Position 3 (Endposition) verlegt.

Ausgangsposition

Zwischenspeicher

Endposition

Schritt #5
Der kleinste Stein wird von Position 2 (Zwischenspeicher)
zu Position 3 (Ausgangsposition) verlegt.

Ausgangsposition

Zwischenspeicher

Endposition

Schritt #6
Der mittlere Stein wird von Position 2 (Zwischenspeicher)
zu Position 3 (Endposition) verlegt.

Ausgangsposition

Zwischenspeicher

Endposition

Schritt #7
Der kleinste Stein wird von Position 1 (Ausgangsposition)
zu Position 3 (Endposition) verlegt.

Alle Steine sind hiermit mit Hilfe des Zwischenspeichers
den Regeln entsprechend verlagert worden.

Ausgangsposition

Zwischenspeicher

Endposition

Prinzip der Prozedur Hanoi
Nach einigem Herumprobieren mit verschieden großen Stapeln findet man heraus, daß man ein großes Problem mit vielen Steinen in immer kleiner werdende Subprobleme lösen kann. Die Aufgabe mit vier Steinen teilt sich in zwei Aufgaben mit drei Steinen, wovon jede Aufgabe mit drei Steinen sich in je zwei Aufgaben mit zwei Steinen unterteilt, welche sich wiederum in je zwei Aufgaben mit je einem Stein splitten lassen.

So muß um einen Stapel mit n Steinen zu transportieren, erst ein Stapel mit n-1 Steinen transportiert werden. Dieser läßt sich jedoch erst nach dem Transfer des daraufliegenden Stapels von n-2 Steinen transportieren usw.

Wie sich leicht erkennen läßt, bietet sich durch Rekursion ein Weg, um die Lösung des Ur-Problems zu verschieben, bis kleinere, einfachere Probleme gelöst sind.

Hierbei wird der originale Turm Schritt für Schritt vom Ausgangsplatz über den Zwischenspeicher zur Endposition verlagert.
Transport von 5 Scheiben
Dieses ist die Ausgangssituation beim Transport von 5 Steinen

Zuerst müssen Türme der Höhen 1, 2, 3 und 4 transpotiert werden, um den Transfer von Scheibe 5 zur Endposition zu ermöglichen.

Ausgangsposition

Zwischenspeicher

Endposition
Transport eines Turms der Höhe 1, wie weiter oben beschrieben (Schritt #1)

Ausgangsposition

Zwischenspeicher

Endposition
Danach folgt der Transfer eines Turms der Höhe 2, um den Transport von Scheibe 3 (dunkelblau) zu ermöglichen, wie weiter oben beschrieben (Schritte #2 und #3).

Ausgangsposition

Zwischenspeicher

Endposition
Nun kann wie in Schritt #3 beschrieben die 3. Scheibe transportiert werden.

Ausgangsposition

Zwischenspeicher

Endposition
Wenn dann ein Turm der Höhe 3 wie in den Schritten #1 bis #7 transportiert worden ist, sieht das ganze so aus.

Ausgangsposition

Zwischenspeicher

Endposition
Dann wird die 4. Scheibe in den Zwischenspeicher verlegt.

Ausgangsposition

Zwischenspeicher

Endposition
Nun wird ein weiteres Mal ein Turm der Höhe 3 transportiert, und zwar von der Endposition in den Zwischenspeicher.

Die Rollen von den verschiedenen Positionen sind bei dieser Aufgabe (dem Transport eines Turms der Höhe 3 von der Endposition zum Zwischenspeicher) vertauscht: Die Endposition dient als Ausgangsposition, die Ausgangsposition als Zwischenspeicher und der Zwischenspeicher als Endposition.

Ausgangsposition

Zwischenspeicher

Endposition
Jetzt kann der unterste Stein (Stein #5) von der Ausgangsposition zur Endposition hin verschoben werden.

Ausgangsposition

Zwischenspeicher

Endposition
Was nun folgt, ist der Transport eines Turms der Höhe 4 vom Zwischenspeicher zur Endposition, was wiederum den vorherigen Transport von einem Turm der Höhe 3 vorraussetzt, wodurch der Transport von einem 2er-Turm erforderlich ist usw.

Nun wird also ein Turm der Höhe 3 wie in Schritt #1 bis #7 weiter oben beschrieben, vom Zwischenspeicher zur Ausgangsposition transportiert, wobei die Endposition als Zwischenspeicher dient. Dieser Transport ist notwendig, um den Transport der darunterliegenden Scheibe #4 (hellgrün) zu ermöglichen.

Ausgangsposition

Zwischenspeicher

Endposition
Nachfolgend ist der Transfer der 4. Scheibe vom Zwischenspeicher zur Endposition.

Ausgangsposition

Zwischenspeicher

Endposition
Was nun noch übrig bleibt, ist nur noch ein Transport eines Turms der Höhe 3 vom Zwischenspeicher zur Endposition. Die Ausgangsposition fungiert hierbei als Zwischenspeicher.

Ausgangsposition

Zwischenspeicher

Endposition

Entwicklung der Prozedur Hanoi
Wenn die rekursive Prozedur Hanoi und die Anzahl der Steine NDisks heißt, so sieht so der Prozedurkopf aus.

OriginPole, SparePole und FinalPole stehen für die Ausgangsposition, den Zwischenspeicher und die Endposition.

 Hanoi(NDisks, OriginPole, SparePole, FinalPole);
Beim ersten rekursiven Aufruf müssen NDisks - 1 vom OriginPole (Ausgangsposition) zum SparePole (Zwischenspeicher) transportiert werden.

Die Aufgaben von FinalPole (Endposition) und SparePole (Zwischenspeicher) sind hierbei vertauscht worden.

 Hanoi(NDisks - 1, OriginPole, FinalPole, SparePole);
Nachdem nun der unterste Stein frei auf der Ausgangsposition (OriginPole) liegt und die Endposition leer ist, kann man ihn durch Aufruf der Prozedur MoveDisk (Prozedur zum bewegen von einzelnen Steinen) verlagern. MoveDisk(OriginPole, FinalPole);
Was nun übrigbleibt ist der Transport von NDisks - 1 Steinen vom Zwischenspeicher (SparePole) zur Endposition (FinalPole).

Bei diesem Aufruf sind die Rolle von SparePole (Zwischenspeicher) und vom OriginPole (Ausgangsposition), welcher nun als Zwischenspeicher dient, vertauscht.

 Hanoi(NDisks - 1, SparePole, OriginPole, FinalPole);
Was nun noch eingebaut werden muß, ist eine Überprüfung, die zum Abbruch der Prozedur sorgt, damit es keine Fehler gibt.

So muß am Beginn der Prozedur nebenstehende Abfrage stehen.

 Hanoi(...)
Begin
  If NDisks > 1 Then Begin
Der gesamte Code sähe damit so aus.

Die Positionen werden mit den Zahlen 1 (OriginPole, Ausgangsposition), 2 (SparePole, Zwischenspeicher) und 3 (FinalPole, Endposition) bezeichnet.

 Procedure Hanoi(NDisks : Word; OriginPole, SparePole, FinalPole : Byte);
Begin
  If NDisks > 1 Then Begin
    Hanoi(NDisks - 1, OriginPole, FinalPole, SparePole);
    MoveDisk(OriginPole, FinalPole);
    Hanoi(NDisks - 1, SparePole, OriginPole, FinalPole);
  End
  Else
    MoveDisk(OriginPole, FinalPole);
End; { of Hanoi }
Außerdem kann man das Ganze noch um eine Variable kürzen, indem man die jeweils benötigte Position berechnet. Procedure Hanoi(NDisks : Word; OriginPole, FinalPole : Byte);
Begin
  If NDisks > 1 Then Begin
    Hanoi(NDisks - 1, OriginPole, 6 - OriginPole - FinalPole);
    MoveDisk(OriginPole, FinalPole);
    Hanoi(NDisks - 1, 6 - OriginPole - FinalPole, FinalPole);
  End
  Else
    MoveDisk(OriginPole, FinalPole);
End; { of Hanoi }

Best viewed with Netscape @ 1024x768

Zur Themenübersicht  
Zum Seitenanfang 
Zur vorigen Seite         Zur nächsten Seite  

© M. Möhrke 2000. All rights reserved.