Aufgabe 1: Die Türme von Hanoi (10 Punkte)

Nach einer alten Legende standen vor langer Zeit vor einem Tempel in Hanoi drei Säulen: Eine aus Kupfer (A), eine aus Gold (B) und eine aus Silber (C). Auf der kupfernen Säule befanden sich hundert verschieden große Scheiben, wobei die Scheiben in ihrer Größe nach oben hin immer kleiner wurden.

Ein alter Mönch hatte sich die Aufgabe gestellt, alle Scheiben von der kupfernen zur goldenen Säule zu tragen. Da die Scheiben sehr schwer waren, konnte der Mönch immer nur eine Scheibe gleichzeitig transportieren. Da die Säulen ihm gleichzeitig als Treppe diente, durfte bei der Umschichtung nie eine größere auf eine kleinere Scheibe gelegt werden!

$\includegraphics[scale=0.7]{turme01.ps}$

Der Mönch bemerkte sehr schnell, daß er beim Transport der Scheiben auch die silberne Säule benötigte, da er ja immer nur eine Scheibe gleichzeitig tragen konnte. Nach einigen Tagen Meditation bekam er auf einmal die Erleuchtung. Die Aufgabe kann in drei Teilaufgaben zerlegt werden:

Teil 1 : Transportiere den Turm bestehend aus 99 oberen Scheiben von der kupfernen (A) zur silbernen Säule (C)

Teil 2 : Transportiere die übriggebliebene 100ste Scheibe (ganz unten) von der kupfernen (A) zur goldenen Säule (B)

Teil 3 : Transportiere den Turm mit den 99 Scheiben von der silbernen (C) zur goldenen Säule (B)

Damit ist aber das Problem der Größe n auf ein Problem der Größe n-1 zurückgeführt (Rekursion) und kann gelöst werden, da die Lösung des Problems für die Größe 1 bekannt ist (Rekursionsanfang).

Das Problem

$\includegraphics[scale=0.9]{turme02.ps}$

ist äquivalent zu

$\includegraphics[scale=0.9]{turme03.ps}$

Beispiel mit 3 Scheiben:

$\includegraphics[scale=0.9]{turme04.ps}$

Ihre Aufgabe ist es nun, das Problem in einen rekursiven Algorithmus zu fassen und auszugeben, wie die Scheiben bewegt werden müssen. Beispielausgabe für 3 Scheiben:

Trage Scheibe 1 von a nach b

Trage Scheibe 2 von a nach c

Trage Scheibe 1 von b nach c

Trage Scheibe 3 von a nach b

Trage Scheibe 1 von c nach a

Trage Scheibe 2 von c nach b

Trage Scheibe 1 von a nach b

Hier nochmals der Algorithmus in etwas formalerer Form:

Problem:
Bewege einen Turm mit n Scheiben von Säule A nach Säule B mit Hilfssäule C
Rekursionsanfang (n = 1):
Falls nur noch eine Scheibe auf Säule A vorhanden ist, dann trage diese Scheibe von Säule A nach Säule B
Rekursionsschritt (n > 1):
- Falls mehr als eine Scheibe auf Säule A vorhanden ist, dann bewege einen Turm von n-1 Scheiben von Säule A nach Säule C mit Hilfssäule B
- Trage anschließend die einzige noch auf Säule A liegende Scheibe von Säule A nach Säule B
- Bewege im letzten Schritt den Turm mit n-1 Scheiben von Säule C nach Säule B mit Hilfssäule A

Viel Erfolg!

Hans Braxmeier