Mathematische Inhalte:

Rekursive Funktionen

Die Problemlösefähigkeit, die als zentrale Schlüsselqualifikation verstärkt eingefordert wird, kann an Spielen lustbetont ausgebildet werden.

Ein aus Scheiben bestehender Turm soll versetzt werden. Es dürfen nur kleinere Scheiben auf größere abgelegt werden. Was ist die optimale Strategie?

Rekursive Folgen

1 Stunde

Visual Basic, Programm hanoi.exe

Bei den Türmen von Hanoi besteht die Aufgabe darin, die Scheiben von der linken Säule auf die rechte zu befördern. Dies soll man mit möglichst wenig Zügen und in kurzer Zeit erreichen. Es gelten folgende Regeln:

1. Es dürfen nur Scheiben bei einem der drei Stäbe abgelegt werden!
2. Es darf immer nur eine und zwar die oberste Scheibe bewegt werden!
3. Es darf keine größere auf eine kleinere Scheibe gelegt werden!

Mit Hilfe dieses Spiels können im Unterricht die Schlüsselqualifikationen Problemlösefähigkeit und Teamarbeit geübt werden. Obwohl es sich um eine geschlossenes Problem mit einer optimalen Strategie handelt, ist die Problemstellung anfangs schwer durchschaubar.
Wehe dem Spieler, der ohne Planung wild zu stapeln beginnt! Schnell wird er sich in einem Scheibenchaos verlieren! Entscheidend ist, ob der erste Zug des Gesamtproblems und die ersten Züge der einzelnen Teilprobleme, in die sich der Gesamtturm zerlegen lässt, richtig gesetzt werden. So verwundert es nicht, dass gute Problemlöser sich dadurch auszeichnen, dass sie für die ersten Turmzüge mehr Zeit aufwenden aks für die verbleibenden Zwischenturmzüge. In der theoretischen Psychologie wird diese Gedächtnisleistung im Strategieindex operationalisiert:
         S = T/Z
wobei T die durchschnittliche Zeit für erste Teilturmzüge und Z die durchschnittliche Zeit für Zwischenturmzüge ist.
Für gute Problemlöser gilt: S > 1

Was ist nun die optimale Strategie, wie muss der erste Zug gesetzt werden? Soll der Turm T_n mit n Scheiben versetzt werden, muss es eine Situation geben, in der der Turm T_n-1 in der Mitte steht, damit die Scheibe 1 auf den rechten Stab versetzt werden kann. Dann wird der Turm T_n-1 auf die Scheibe 1 versetzt. Also: Scheibe 2 in die Mitte, Scheibe 3 nach rechts, usw. Insgesamt: Scheibe n ungerade nach rechts, Scheibe n gerade in die Mitte.
Somit erhält man auch als Rekursion für die Zuganzahl: Z_n = Z_n-1 + 1 + Z_n-1 = 2·Z_n-1 + 1.
Mit Rekursionsbeginn Z₁ = 1 erhält man (mit vollständiger Induktion) die geschlossene Form
         Z_n = 2ⁿ – 1.
Bei n = 5 Scheiben sind das 31 Züge, bei n = 10 Scheiben 1023 Züge, bei n = 15 Scheiben 32767 Züge, die Anzahl der Züge wächst exponentiell wie bei der Schachanekdote.