| Autor |
Beitrag |
    
Beast
| | Veröffentlicht am Freitag, den 03. November, 2000 - 18:59: | 
|
Hallo...
Könnt ihr mir bei dem Beweis des Problems des Turm von Hanoi helfen ?
Aufgabe :
Wir haben drei Tische T1,T2 und T3. Auf dem Tisch T1 liegen neN \ {0}
untersch. große Scheiben übereinander.
Diese sind der Größe nach so geordnet, daß die größte Scheibe ganz unten
liegt. Es soll dieser Stapel auf einen der beiden anderen Tische gebracht
werden. Dabei müsseb aber die folgenden Punkte beachtet werden :
1) Bei jedem Schritt darf nur eine Scheibe bewegt werden. Insbesondere heißt
dies, daß immer nur die oberste Scheibe eines Stapels bewegt werden darf.
2) Eine Scheibe darf nur auf einen Tisch bzw. auf einen Stapel von Scheiben
gelegt werden
3) Es darf keine Scheibe auf eine kleinere Scheibe gelegt werden
Mir fehlt dabei der Ansatz...ich komm einfach nicht drauf. Wäre echt toll,
wenn mir mal einer dabei helfen.
Bin echt dankbar für Lösungsansätze, Lösungen *g und allem anderen....
danke schonmal,
Oliver
- MCSE -
email : beast@thabeast.de
http : www.thabeast.de |
Matroid (Matroid)
| | Veröffentlicht am Samstag, den 04. November, 2000 - 21:32: |
|
Hi Oliver,
sei a(n) die Anzahl der Schritte um n Scheiben von T1 nach T2 umzulegen (unter Einhaltung der genannten Regeln).
Die Scheiben liegen also zu Anfang auf T1 absteigend nach Größe sortiert. Die größte Scheibe unten.
Um den Turm nach T2 umzulegen, muß man ja erreichen, daß die größte Scheibe auf T2 ganz unten zu liegen kommt.
Nun kann man aber die größte Scheibe erst bewegen, wenn darüber keine anderen Scheiben mehr liegen. Also: um die größte Scheibe von T1 nach T2 legen zu können, müssen vorher alle anderen Scheiben (das sind n-1 Stück) von T1 weggelegt werden. Alle n-1 kleineren Scheiben müssen also auf T3 liegen. Da niemals eine größere Scheibe über einer kleineren Scheibe liegen kann, liegen dann also n-1 Scheiben auf T3. Wieviel Schritte braucht man, um n-1 Scheiben von T1 nach T3 umzulegen? Das ist a(n-1).
Also ist a(n) = a(n-1) + 1 + a(n-1)
Das erste a(n-1) ist die Anzahl der Schritte um die oberen n-1 Scheiben von T1 nach T3 zu räumen (aus dem Weg zu räumen). Die 1 ist der eine Schritt die größte Scheibe von T1 nach T2 zu legen.
Das letzte a(n-1) ist die Anzahl der Schritte die n-1 Scheiben von T3 nach T2 umzulegen.
Damit haben wir jetzt eine Rekursionsformel:
a(n) = 2*a(n-1) + 1
Diese Rekursion ist für den Induktionsschritt ganz wesentlich.
Nun müssen wir uns aber auch überlegen, wie denn wohl die Formel für a(n) in Abhängigkeit von n aussehen soll.
Für die ersten n=1,2,3 gilt
a(1) = 1
a(2) = 2 * 1 + 1 = 3
a(3) = 2 * 3 + 1 = 7
a(4) = 2 * 7 + 1 = 15.
Das erlaubt nun die Vermutung, daß a(n) = 2n - 1
Dies ist dann mittels Induktion und unter Verwendung der Rekursionsformel zu zeigen.
Also: der Lösungsansatz ist die Überlegung, die ich zum Finden der Rekurionsformel benutzt habe.
Gruß
Matroid |
Bodo
| | Veröffentlicht am Samstag, den 04. November, 2000 - 21:35: |
|
Du wirst hier finden, was Du suchst:
Turm von Hanoi: Beweisführung
Bodo |
|
