Türme von Hanoi (3D)
Über diese App
Das klassische Rekursionsrätsel im Raum: Scheibenzahl wählen, vom Algorithmus optimal lösen lassen (2ⁿ−1 Züge) oder selbst ziehen — Stab für Stab wird die rekursive Idee T(n)=2·T(n−1)+1 sichtbar.
Das Rätsel und seine rekursive Lösung
Ein Turm aus n Scheiben soll von Stab A nach Stab C wandern. Es darf immer nur eine Scheibe bewegt werden, und nie darf eine größere auf einer kleineren liegen. Die rekursive Idee: Um n Scheiben zu versetzen, bringt man zuerst die oberen n − 1 Scheiben auf den Hilfsstab B, bewegt dann die größte Scheibe mit einem einzigen Zug nach C und setzt schließlich die n − 1 Scheiben von B auf C. Daraus folgt T(n) = 2 · T(n − 1) + 1, also genau 2ⁿ − 1 Züge. Weniger geht nicht.
Was die App zeigt
Drei Stäbe und ein Scheibenturm im Raum, aus mehreren Blickwinkeln betrachtbar: Standardblick, frontal, Aufsicht oder nah an Start- und Zielstab. Ein Statusfeld zählt die Züge, nennt das Minimum 2ⁿ − 1 und den letzten Zug. Beim automatischen Lösen läuft die optimale rekursive Lösung ab; man sieht, dass die kleinste Scheibe in jedem zweiten Zug wandert und die größte nur ein einziges Mal.
Selbst ausprobieren
Stelle mit dem Regler 3 bis 8 Scheiben ein und versuche den Turm selbst zu versetzen, oder lass den Algorithmus lösen, im Ganzen oder Zug für Zug, in wählbarem Tempo. Vergleiche deinen Zugzähler mit dem Minimum. Mit 8 Scheiben sind es schon 255 Züge, jede weitere Scheibe verdoppelt die Arbeit.
Häufige Fragen
- Wie viele Züge braucht man für die Türme von Hanoi?
- Mindestens 2ⁿ − 1 Züge für n Scheiben: 7 bei 3 Scheiben, 15 bei 4, 255 bei 8. Jede zusätzliche Scheibe verdoppelt die Zahl der Züge und addiert einen.
- Wie funktioniert der rekursive Algorithmus für die Türme von Hanoi?
- Um n Scheiben von A nach C zu bringen, verschiebt man rekursiv n − 1 Scheiben von A nach B, bewegt die größte Scheibe von A nach C und verschiebt dann die n − 1 Scheiben rekursiv von B nach C. Der Basisfall ist eine einzelne Scheibe, die direkt bewegt wird.
- Warum ist 2ⁿ − 1 die minimale Zugzahl?
- Die größte Scheibe muss mindestens einmal bewegt werden, und dafür müssen alle n − 1 kleineren Scheiben auf dem dritten Stab liegen, vorher und nachher. Das erzwingt T(n) ≥ 2 · T(n − 1) + 1 mit T(1) = 1, und diese Rekursion ergibt genau 2ⁿ − 1.
- Was kann ich in der Hanoi-App machen?
- Du wählst 3 bis 8 Scheiben, ziehst selbst oder lässt die optimale Lösung komplett oder Zug für Zug ablaufen. Zugzähler, Minimum und letzter Zug stehen live daneben, und du kannst die Kamera frei drehen oder Ansichten wie die Aufsicht wählen.
Fach: Informatik
Mehr aus Informatik
- Ackermann-Funktion
- Aufzug-Simulator
- Binär-Werkstatt
- Binäre vs. lineare Suche
- Collatz-Problem (3n+1)
- CPU-Innenleben
- Das Innere austauschen
- Ein Frame in 16 Millisekunden — wie eine Game-Engine ein Bild rechnet (3D)
Eine VisuApp von heyprof: interaktiv, kostenlos im Browser, ohne Anmeldung. Was ist eine VisuApp? · Alle Apps