Turm von Hanoi in C++

1. Turm von Hanoi
2. Lösung des Turmproblems von Hanoi
3. C++-Programm für das Problem des Turms von Hanoi

Dieser Artikel wird das Problem des Turms von Hanoi und seine rekursive Lösung in C++ kurz erläutern.

Turm von Hanoi

Der Turm von Hanoi ist ein mathematisches Puzzle mit drei Stäben und mehreren Scheiben, die sich um die Stäbe bewegen können. Die Scheiben werden in absteigender Reihenfolge der Größe von oben nach unten angeordnet und bilden einen Stapel.

Das Ziel besteht darin, alle Scheiben in der (letzten) Zielstange zu bewegen, wobei die Reihenfolge gleich bleibt, aber einige Regeln eingehalten werden:

1. Sie können jeweils nur eine Festplatte verschieben.
2. Eine Disk kann nicht auf eine Disk gelegt werden, die kleiner ist als sie selbst.

Nach diesen Regeln müssen Sie die Scheiben von der ersten Stange oder dem ersten Stift zur letzten Stange bewegen. Die Mindestanzahl an Zügen, die erforderlich ist, um diese Aufgabe zu lösen, ist 2^n -1, wobei n die Anzahl der Scheiben ist.

Dies ist im Bild unten dargestellt:

Jetzt müssen Sie diese drei Scheiben in Peg A mit Hilfe von Peg B zum Ziel Peg C verschieben.

Lösung des Turmproblems von Hanoi

Es kann sowohl iterative als auch rekursive Lösungen für dieses Problem geben, aber wir werden hier die rekursive Lösung besprechen, da iterativ von der Anzahl der Festplatten abhängt. Nehmen wir für die rekursive Lösung an, dass sich m Scheiben auf Stift A befinden.

1. Die gleiche grundlegende Methode wird verwendet, um m-1-Discs von Peg A nach Peg B zu übertragen. Vorausgesetzt, es verstößt nicht gegen die Regeln, ist die Scheibe m nun die oberste Scheibe auf Peg A.
2. Bewegen Sie die Scheibe m von Peg A zum Zielpflock, d. h. Peg C, was ein einfacher Vorgang ist und den allgemeinen Regeln folgt.
3. Bewegen Sie auf die gleiche Weise die m-1-Scheiben, die wir gerade auf Peg B gelegt haben, von Peg B zum Zielpflock, d. h. Peg C, damit sie auf die gelegt werden können Scheibe m, ohne irgendwelche Beschränkungen zu brechen.
4. Wiederholen Sie diese Schritte, bis Sie das Ausgangsgehäuse erreichen.
5. Der Exit-Fall besteht darin, 0 Platten zu verschieben, d. h. alle Platten befinden sich im Zielstift.

C++-Programm für das Problem des Turms von Hanoi

Das C++-Programm zur Lösung dieses Problems ist unten dargestellt:

void TowerOfHanoi(int m, string first, string middle, string last) {
  cout << "Current iteration " << m << endl;
  if (m == 1) {
    cout << "Moving Disc from " << first << " to " << last << endl;
  } else {
    TowerOfHanoi(m - 1, first, last, middle);
    cout << "Moving disc " << m << " from " << first << " to " << last << endl;
    TowerOfHanoi(m - 1, middle, first, last);
  }
}
int main() {
  int di = 3;
  TowerOfHanoi(di, "PegA", "PegB", "PegC");
}

Dies ergibt die folgende Ausgabe:

Beachten Sie, dass wir in der Funktion TowerOfHanoi die Funktion zweimal für jede Iteration abrufen. Zuerst bewegen wir uns vom ersten Stift zur Mitte und dann von der Mitte zum letzten.

Dadurch entsteht der folgende Baum:

main
  |--> TowerOfHanoi(3, ...)
  |      |
  |      |--> TowerOfHanoi(2, ...)
  |      |     |
  |      |     |--> TowerOfHanoi(1, ...)
  |      |     |--> TowerOfHanoi(1, ...)
  |      |<----|
  |      |--> TowerOfHanoi(2, ...)
  |      |     |
  |      |     |--> TowerOfHanoi(1, ...)
  |      |     |--> TowerOfHanoi(1, ...)
  |      |<----|
  |<-----|
  |