Erarbeitung - Anzahl der Züge
Zur Orientierung
Ziel ist es jetzt, die (minimale) Anzahl
Zustand vorher | Zustand nachher |
---|---|
![]() | ![]() |
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.
![]() | ![]() |
Bewege einen 5-Scheiben-Turm zum Endstapel | Bewege einen 4-Scheiben-Turm zum Hilfsstapel |
![]() | |
Bewege 1 Scheibe zum Endstapel | |
![]() | |
Bewege einen 4-Scheiben-Turm zum Endstapel | |
![]() | ![]() |
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
(b) Bestimme anschließend
(c) Bestimme auch
(d) Bestimme analog
(e) Fällt dir bei der Zahlenfolge
(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?