Erarbeitung - Umschichtverfahren
Zur Orientierung
Wir bearbeiten hier das folgende Umschichtungsproblem: Gegeben ist ein Turm mit $n$ (z.B. $n = 5$) Scheiben im Stapel A. Schichte die Scheiben unter Berücksichtigung der Transportregeln so um, dass der Turm schließlich im Stapel C entsteht. Benutze B als Hilfsstapel.
| Zustand vorher | Zustand nachher |
|---|---|
|
|
Lösungsideen entwickeln
Hier kannst du experimentell Lösungsideen zum Umschichtungsproblem zu den Türmen von Hanoi entwickeln. Benutze hierzu das unten bereitgestellte Simulationsapplet.
Aufgabe 1
(a) Beim Problemlösen ist es oft günstig, mit einfachen Fällen zu beginnen. Löse das Umschichtungsproblem zunächst für $n = 3$ Scheiben.
(b) Erhöhe dann Schritt für Schritt die Anzahl der Scheiben. Tipp: Wenn man einen 4-Scheiben-Turm umschichten will, dann ist es günstig, wenn man weiß, wie man einen 3-Scheiben-Turm umschichtet.
(c) Formuliere eine Strategie, wie man beim Umschichten der Scheiben vorgehen sollte.
Aufgabe 2
Wenn du das Umschichten von Türmen beherrschst, dann beschäftige dich mit der Anzahl der benötigten Züge. Gesucht ist die minimale Anzahl von Zügen (das sind die Scheibentransporte), die man benötigt, um einen Turm mit 3 (bzw. 4, 5, 6, ...) Scheiben umzuschichten.
| AZ | ZZ 1 | ZZ 2 | EZ |
|---|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
Dir ist sicherlich aufgefallen, dass es einfach ist, einen kleinen Turm umzuschichten. Je größer der Turm wird, desto länger dauert es und desto schwieriger ist es auch, die richtige Abfolge an Zügen zu finden. Es hilft deshalb, erst kleine Türme zu betrachten und nach einem Muster zu suchen, wie man mit der Lösung für einen kleinen Turm auch einen größeren Turm umschichten kann.
