Spielen Sie das klassische Turm von Hanoi-Puzzle online. Bewegen Sie Scheiben zwischen Stäben unter Einhaltung der Regeln. Wählen Sie Ihre Schwierigkeit und lösen Sie es in minimalen Zügen. Kostenlos, keine Registrierung.
Der Turm von Hanoi ist ein mathematisches Puzzle, das 1883 vom französischen Mathematiker Édouard Lucas erfunden wurde. Es besteht aus drei Stäben und einer Anzahl von Scheiben unterschiedlicher Größe, die auf jeden Stab geschoben werden können. Das Puzzle beginnt mit den Scheiben in aufsteigender Größenordnung auf einem Stab gestapelt, und das Ziel ist es, den gesamten Stapel auf einen anderen Stab zu verschieben, unter Einhaltung bestimmter Regeln. Die minimale Anzahl an Zügen, die zum Lösen des Puzzles erforderlich sind, ist 2^n − 1, wobei n die Anzahl der Scheiben ist.
Die minimale Anzahl an Zügen, um den Turm von Hanoi mit n Scheiben zu lösen, ist 2^n − 1. Zum Beispiel: 3 Scheiben = 7 Züge, 4 Scheiben = 15 Züge, 5 Scheiben = 31 Züge, 6 Scheiben = 63 Züge, 7 Scheiben = 127 Züge und 8 Scheiben = 255 Züge.
Ja. Der Beweis verwendet mathematische Induktion. Um n Scheiben von Stab A zu Stab C zu bewegen, müssen Sie zuerst n−1 Scheiben zu Stab B bewegen (T(n−1) Züge), dann die größte Scheibe zu Stab C bewegen (1 Zug), dann die n−1 Scheiben von Stab B zu Stab C bewegen (weitere T(n−1) Züge). Dies ergibt die Rekurrenz T(n) = 2T(n−1) + 1, die sich zu T(n) = 2^n − 1 löst.
Nein. Die minimale Anzahl an Zügen (2^n − 1) ist bewiesen, dass sie sowohl notwendig als auch ausreichend ist. Jede Lösung erfordert mindestens diese viele Züge, und es gibt eine Strategie, die genau diese Anzahl erreicht.
Für das physische Puzzle mit 8 Scheiben können geübte Löser es in unter 2 Minuten schaffen. Im kompetitiven Programmieren können Computer es sofort für jede praktische Anzahl von Scheiben mit dem rekursiven Algorithmus lösen.