i

Erarbeitung - Anzahl der Züge

Zur Orientierung

Ziel ist es jetzt, die (minimale) Anzahl an von Zügen (das sind die Scheibenbewegungen) zu bestimmen, die man beim Umschichten eines n-Scheiben-Turm benötigt.

Zustand vorherZustand nachher
Türme von Hanoi - AnfangszustandTürme von Hanoi - Endzustand

Wir beginnen mit einer Beschreibung des Umschichtverfahrens.

Das Umschichtverfahren beschreiben

Dir ist sicherlich Folgendes aufgefallen:

  • Es ist ganz einfach, einen 1-Scheiben-Turm umzuschichten.
  • Wenn man einen 1-Scheiben-Turm umschichten kann, dann kann man dieses Verfahren benutzen, um einen 2-Scheiben-Turm umzuschichten.
  • Wenn man einen 2-Scheiben-Turm umschichten kann, dann kann man dieses Verfahren benutzen, um einen 3-Scheiben-Turm umzuschichten.
  • Wenn man einen 3-Scheiben-Turm umschichten kann, dann kann man dieses Verfahren benutzen, um einen 4-Scheiben-Turm umzuschichten.
  • Wenn man einen 4-Scheiben-Turm umschichten kann, dann kann man dieses Verfahren benutzen, um einen 5-Scheiben-Turm umzuschichten.
  • ...

Die folgende Übersicht verdeutlicht dieses Rückführungsverfahren für einen 5-Scheiben-Turm.

Türme von Hanoi - AnfangszustandTürme von Hanoi - Anfangszustand
Bewege einen 5-Scheiben-Turm zum Endstapel Bewege einen 4-Scheiben-Turm zum Hilfsstapel
Türme von Hanoi - Anfangszustand
Bewege 1 Scheibe zum Endstapel
Türme von Hanoi - Anfangszustand
Bewege einen 4-Scheiben-Turm zum Endstapel
Türme von Hanoi - AnfangszustandTürme von Hanoi - Anfangszustand

Aufgabe 1

Erläutere das Rückführungsverfahren am Beispiel Umschichtung eines 5-Scheiben-Turms.

Die Anzahl der Züge bestimmen

Wir richten den Fokus jetzt auf die Anzahl der Züge.

Aufgabe 2

(a) Beginne mit den einfachsten Fällen: Umschichtung eines 1-ScheibenTurms und Umschichtung eines 2-Scheiben-Turms. Bestimme die zugehörigen Zuganzahlen a1 und a2. Diese Werte kann man sofort angeben.

(b) Bestimme anschließend a3. Dazu musst du wissen, wie man einen 3-Scheiben-Turm umschichtet.

(c) Bestimme auch a4. Nutze die Strategie zur Lösung des Umschichtungsproblems.

Hilfe - Umschichtung eines 4-Scheiben-Turms
Türme von Hanoi - AnfangszustandTürme von Hanoi - Anfangszustand
Bewege einen 4-Scheiben-Turm zum Endstapel
Anzahl der Züge: ...
Bewege einen 3-Scheiben-Turm zum Hilfsstapel
Anzahl der Züge: ...
Türme von Hanoi - Anfangszustand
Bewege 1 Scheibe zum Endstapel
Anzahl der Züge: 1
Türme von Hanoi - Anfangszustand
Bewege einen 3-Scheiben-Turm zum Endstapel
Anzahl der Züge: ...
Türme von Hanoi - AnfangszustandTürme von Hanoi - Anfangszustand

(d) Bestimme analog a5. Notiere die Zahlenfolge a1;a2;a3;a4;a5;....

Zur Kontrolle

1;3;7;15;31;...

(e) Fällt dir bei der Zahlenfolge a1;a2;a3;a4;a5;... eine Gesetzmäßigkeit auf? Nutze sie, um a64 zu bestimmen.

Zur Kontrolle
a64=18446744073709551615

(f) Die Mönche von Benares benötigen zum Transport von 1 Scheibe 1 Minute. Wie lange brauchen sie, um einen 64-Scheiben-Turm umzuschichten? Vergleiche diese Zeit mit dem Alter des Universums, das ca. 13.8 Milliarden Jahre beträgt. Wann ist demnach der Weltuntergang zu befürchten?

Suche

104.2.1.2.1.2
o-mathe.de/gr/folgen/folgenkonzept/tuermevonhanoi/lernstrecke/erarbeitung2
o-mathe.de/104.2.1.2.1.2

Rückmeldung geben