01. Stunde: Erarbeitung
Der Turm von Hanoi
DIe Geschichte von dem Mathematiker EDOUARD LUCAS (1842-1891)
Der indische Gott Brahma soll in einem Tempel einen Turm errichtet haben, der aus 64 runden Gold-plättchen besteht, die auf einer Nadel stecken und nach oben immer kleiner werden. Er wird heute der Turm von Hanoi genannt. Neben der Nadel mit dem Turm gibt es noch zwei weitere leere Nadeln. Brahma gab seinen Priestern die Anweisung:
„Baut den Turm auf einer leeren Nadel neu auf. Beachtet dabei die Umlegeregeln:
1. Es darf bei jeder Umlegung jeweils nur ein Plättchen bewegt werden. 2. Ein Plättchen darf nur auf eine leere Nadel oder auf ein größeres Plättchen gelegt werden."Aufgabe 1: Ausprobieren
Hier kannst du experimentell Lösungsideen zum Umschichtungsproblem zu den Türmen von Hanoi entwickeln. Benutze hierzu das unten bereitgestellte Simulationsapplet.
Starte mit 1 Scheibe und steigere dich bis auf 3 Scheiben. Führe jeweils den Umbau durch und ergänze die Tabelle:
| Anzahl der Plättchen n | 1 | 2 | 3 |
|---|---|---|---|
| Anazhl der Umlegungen |
Der Turm von Hanoi
Ziehe eine Scheibe auf einen anderen Turm.
Aufgabe 2: Muster erkennen
Betrachtet euren Weg für 3 Plättchen. Überlegt:
a) Welchen Teilschritt kennt ihr schon aus dem Fall mit 2 Plättchen?
b) Wie könnt ihr den Umbau von 3 Plättchen in drei Etappen zerlegen, von denen zwei euch schon bekannt sind?
Nutzt diese Beobachtung, um ohne weiteres Ausprobieren die Anzahl der Umlegungen für 4 Plättchen vorherzusagen. Prüft eure Vorhersage anschließend praktisch.Ziel
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.
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.
- ...
Aufgabe 2: Anzahl der Züge bestimmen
a) Beginne mit den einfachsten Fällen: Umschichtung eines 1-Scheiben-Turms und Umschichtung eines 2-Scheiben-Turms. Bestimme die zugehörigen Zuganzahlen a1 und a2.
b) Bestimme anschließend 𝑎3. Dazu musst du wissen, wie man einen 3-Scheiben-Turm umschichtet.
c) Bestimme auch 𝑎4. Nutze die Strategie zur Lösung des Umschichtungsproblems.