Datenstruktur & Algorithmen - Turm von Hanoi

Der Turm von Hanoi ist ein mathematisches Puzzle, das aus drei Türmen (Heringen) und mehr als einem Ring besteht.

Diese Ringe sind unterschiedlich groß und in aufsteigender Reihenfolge gestapelt, dh der kleinere sitzt über dem größeren. Es gibt andere Variationen des Puzzles, bei denen die Anzahl der Festplatten zunimmt, die Anzahl der Türme jedoch gleich bleibt.

Regeln

Die Mission besteht darin, alle Festplatten in einen anderen Turm zu verschieben, ohne die Reihenfolge der Anordnung zu verletzen. Einige Regeln für den Turm von Hanoi sind:

• Es kann immer nur eine Scheibe zwischen den Türmen bewegt werden.
• Nur die "obere" Festplatte kann entfernt werden.
• Keine große Festplatte kann über einer kleinen Festplatte liegen.

Es folgt eine animierte Darstellung des Lösens eines Tower of Hanoi-Puzzles mit drei Scheiben.

Das Puzzle des Turms von Hanoi mit n Scheiben kann mindestens gelöst werden 2ⁿ−1Schritte. Diese Präsentation zeigt, dass ein Puzzle mit 3 Scheiben genommen hat2³ - 1 = 7 Schritte.

Algorithmus

Um einen Algorithmus für Tower of Hanoi zu schreiben, müssen wir zunächst lernen, wie dieses Problem mit einer geringeren Anzahl von Festplatten gelöst werden kann, z. B. → 1 oder 2. Wir markieren drei Türme mit dem Namen, source, destination und aux(nur um das Verschieben der Festplatten zu erleichtern). Wenn wir nur eine Festplatte haben, kann diese problemlos vom Quell- zum Zielstift verschoben werden.

Wenn wir 2 Festplatten haben -

• Zuerst verschieben wir die kleinere (obere) Festplatte in den Aux Peg.
• Dann verschieben wir die größere (untere) Festplatte zum Zielstift.
• Und schließlich verschieben wir die kleinere Festplatte vom Aux zum Ziel-Peg.

Jetzt sind wir in der Lage, einen Algorithmus für Tower of Hanoi mit mehr als zwei Festplatten zu entwerfen. Wir teilen den Plattenstapel in zwei Teile. Die größte Festplatte (n- ^te Festplatte) befindet sich in einem Teil und alle anderen (n-1) Festplatten befinden sich im zweiten Teil.

Unser oberstes Ziel ist es, die Festplatte zu bewegen nvon der Quelle zum Ziel und legen Sie dann alle anderen (n1) Festplatten darauf. Wir können uns vorstellen, dasselbe für alle gegebenen Festplattensätze rekursiv anzuwenden.

Die folgenden Schritte sind:

Step 1 − Move n-1 disks from source to aux
Step 2 − Move nth disk from source to dest
Step 3 − Move n-1 disks from aux to dest

Ein rekursiver Algorithmus für Tower of Hanoi kann wie folgt gesteuert werden:

START
Procedure Hanoi(disk, source, dest, aux)

   IF disk == 1, THEN
      move disk from source to dest             
   ELSE
      Hanoi(disk - 1, source, aux, dest)     // Step 1
      move disk from source to dest          // Step 2
      Hanoi(disk - 1, aux, dest, source)     // Step 3
   END IF
   
END Procedure
STOP

Klicken Sie hier, um die Implementierung in der C-Programmierung zu überprüfen .