Die Türme von Hanoi - Algorithmus

Wissenschaft Mathematik
#1

Wieder einmal eine Aufgabe, an der ich mir die Zähne ausbeiße…

Die Türme von Hanoi. Das Spiel „Die Türme von Hanoi“ besteht aus 3 Spielfeldern, auf denen n element N Scheiben paarweise verschiedener Größe gestapelt werden können. Zu Beginn des Spiels sind alle Scheiben auf einem der Spielfelder der Größe nach gestapelt (die unten liegende Scheibe ist die größte). Ziel des Spiels ist es, den Anfangsstapel auf ein anderes Feld zu versetzen, so dass er dort wieder in der gleichen Stapel-Reihenfolge liegt. Dazu darf in jedem Spielzug die oberste Scheibe eines beliebigen Turms auf einen anderen Turm, der keine kleinere Scheibe enthält, gelegt werden.

Aufgabe dazu: Geben Sie einen Algorithmus an (Papierform genügt), der dieses Problem löst, und beweisen Sie die Korrektheit Ihres Algorithmus. Stellen Sie eine Formel für die Anzahl der notwenigen Züge auf und beweisen Sie diese mit vollständiger Induktion.

Also…das Prinzip des Spiels ist mir bewusst und ich weiß auch, wie ich die Scheiben verrücken muss (15mal), damit der Stapel am Ende auf einem anderen Feld ist…allerdings tu ich mir mit den konkreten Aufgaben echt schwer :frowning: Würde mich sehr über Hilfe freuen! Mein Prof erklärt nämlich leider so gut wie nichts…

Danke im Voraus! :smile:

#2

Hallo.

Für die Türme von Hanoi kannst du einen rekursiven Algorihmus definieren, indem du einen Turm der Höhe n als einen Turm der höhe n-1 auf einer weiteren Scheibe betrachtest. Wir definieren uns also:
Hanoi(n, A, B, C) als den Algorithmus, der einen Turm der Höhe n von A nach B bringt und dabei C als zwischenablage nutzt. Ausserdem haben wir move(A,B), der eine einzelne Scheibe von A nach B bewegt.
Hanoi(0, A, B, C) sieht dann folglich so aus:

Da wir einen Turm der höhe 0 haben, gibt es nichts zu bewegen. So simpel das ist, haben wir damit die Abbruchbedingung der Rekursion geschaffen und können definieren:
Hanoi(n, A, B, C) = { Hanoi(n-1, A, C, B); move(A,B); Hanoi(n-1, C, A, B) }
Was bedeutet das also? Ich formuliere es einmal natürlichsprachlich:
Um einen Turm aus N scheiben von A nach B zu bringen, bewege ich zunächst einen Turm der Höhe n-1 von A nach C. Anschließend liegt nur noch die größte Scheibe auf A, die ich direkt nach B bewege. Dann bewege ich wieder den Turm der Höhe n-1 von C nach A zurück.
Das Problem wird also immer wieder auf das Verschieben eines kleineren Turms reduziert.

An dieser Definition des Algorithmus können wir uns auch die funktion moves(h) defineren, die einer Turmhöhe h die Anzahl nötiger Verschiebungen (also aufrufe von move()) zuordnet. Diese lautet, vollständig analog zum Algorithmus definiert, so:
moves(0) = 0
moves(h) = moves(h-1) + 1 + moves(h-1) = 2 * moves(h-1) + 1

Wenn wir uns nun die Entwicklung anschauen:moves(0) = 0, moves(1) = 1, moves(2) = 3, moves(3) = 7, moves(4) = 15, …
könnten wir auf die Idee kommen, dass gilt: moves(h) = 2^h  -1

Dass dem so ist, kannst du mittels vollständiger Induktion nachweisen. Wenn du damit Probleme hast, kann ich dir auch damit gerne weiterhelfen, aber ich schätze das dürfte ziemlich leicht werden.

#3

Vielen Dank! Das hat mir sehr weitergeholfen :wink:

#4

na…da haste doch schon ne super antwort…das ist das wunder der induktion…smile…
grüsse…