Spielereien · Spiele und Rätsel
Türme von Hanoi
Auf Stab A liegt ein Turm aus Scheiben. Er soll auf Stab C umziehen. Du darfst immer nur eine Scheibe bewegen, und nie darf eine größere Scheibe auf einer kleineren liegen. Mit drei Scheiben geht das schnell. Aber wie viele Züge braucht man bei acht Scheiben, und wie kann man das vorhersagen?
So gehst du vor
- 1Wähle die Zahl der Scheiben. Ziehe die oberste Scheibe eines Stabs mit dem Finger auf einen anderen Stab.
- 2Vergleiche deine Züge mit der Mindestzahl.
- 3Tippe auf „Rekursion ansehen“, um den Ablauf Schritt für Schritt oder automatisch zu sehen. Rechts stehen die offenen Aufrufe.
Zahl der Scheiben
Deine Züge
0
Mindestzahl
7
Mindestzahl: 2n − 1 = 23 − 1 = 7
Aufträge
- Löse den Turm für 1, 2, 3 und 4 Scheiben mit möglichst wenigen Zügen. Notiere die Zugzahlen. Wie hängt die Zugzahl bei n + 1 Scheiben von der Zugzahl bei n Scheiben ab?
- Sieh dir die Rekursion mit drei Scheiben an. Bei welchem Zug bewegt sich Scheibe 3? Wo liegen in diesem Moment alle kleineren Scheiben? Warum muss das so sein?
- Begründe mit der Rekursion, warum für die Mindestzahl Z(n + 1) = 2 · Z(n) + 1 gilt. Zeige dann, dass Z(n) = 2n − 1 diese Gleichung erfüllt.
- Zähle bei vier Scheiben im Ablauf, wie oft sich jede Scheibe bewegt. Was fällt dir auf?
- Eine alte Legende erzählt von 64 goldenen Scheiben. Mönche legen jede Sekunde eine Scheibe um. Schätze zuerst, dann rechne: Wie lange dauert das?