Türme von Hanoi

1883 erfand der französische Mathematiker Edouard Lucas das Problem der Türme von Hanoi.

Ziel des Spieles: Alle Scheiben vom Turm ganz links sollen auf den Turm ganz rechts bewegt werden.

Bedingungen:
  1. Man kann nur eine Scheibe pro Zug verschieben.
  2. Eine größere Scheibe darf nie auf einer kleineren Scheibe liegen.
Zum Verschieben einer Scheibe:
  • Klick zuerst auf den Turm, von dem die oberste Scheibe entfernt werden soll.
  • Klick dann auf den Turm, auf den die Scheibe platziert werden soll.

Um zu starten, gib ein mit wie vielen Scheiben du starten möchtest.

Anzahl der Scheiben:
Bitte gib eine positive Zahl zwischen 1 und 10 ein.

Was wäre die optimale Anzahl an Zügen?

Notwendige Züge:

Erklärung:

Das Türme von Hanoi-Spiel besteht aus drei Stäben und einer Reihe von Scheiben unterschiedlicher Größe, die auf einem der Stäbe gestapelt sind. Das Ziel des Spiels besteht darin, alle Scheiben von einem Ausgangsstab zu einem Zielstab zu bewegen, wobei die folgenden Regeln beachtet werden müssen:

Nur eine Scheibe kann gleichzeitig bewegt werden. Eine größere Scheibe darf niemals auf einer kleineren Scheibe liegen. Die optimale Strategie, um das Türme von Hanoi-Spiel zu lösen, folgt einem rekursiven Algorithmus, der wie folgt funktioniert:

Wenn nur eine Scheibe auf dem Ausgangsstab liegt, bewege sie direkt auf den Zielstab. Andernfalls führe die folgenden Schritte aus:

  • Bewege n-1 Scheiben vom Ausgangsstab auf den Zwischenstab, unter Verwendung des Zielstabs.
  • Bewege die größte Scheibe vom Ausgangsstab auf den Zielstab
  • Bewege die n-1 Scheiben vom Zwischenstab auf den Zielstab, unter Verwendung des Ausgangsstabs.
Dieser Algorithmus wird dann wiederholt, bis alle Scheiben erfolgreich auf den Zielstab verschoben wurden.

Die optimale Strategie für das Türme von Hanoi-Spiel ist bekannt als "Teilen und Erobern". Durch das Aufteilen des Problems in kleinere Teilprobleme und die Verwendung von Rekursion wird sichergestellt, dass alle Scheiben in der richtigen Reihenfolge bewegt werden, ohne gegen die Regel zu verstoßen. Die Anzahl der Schritte, die für das Lösen des Spiels benötigt werden, beträgt 2^n - 1, wobei n die Anzahl der Scheiben ist.

Es ist wichtig zu beachten, dass die optimale Strategie für das Türme von Hanoi-Spiel aufgrund der Eigenschaften des Spiels mathematisch bewiesen wurde und unabhängig von der Anzahl der Scheiben immer funktioniert.