Türme von Hanoi: Anzahl der Züge

Question

wie kann ich zeigen dass $$2^n-1$$ Züge notwendig für die Lösung des Problems der Türme von Hanoi sind? 

Answer 1

durch vollst. Ind. schlage ich vor.

Comments

Induktionsanfang: 

Wenn wir eine Scheibe haben, müssen wir es zu den richtigen Stab transportieren. Also brauch man mindestens einen Zug.

Induktionsbehauptung:

Wir behaupten dass wenn wir n Scheben haben brauchen wir mindestens $$2^n-1$$ Züge.

Induktionsschritt: 

Wenn wir n+1 Scheiben haben, was kann man sagen um zu zeigen dass man mindestens $$2^{n+1}-1$$ Züge brauch egal welchen Algorithmus man anwendet?

---

Es nicht egal,welchen Algorithmus man anwendet. Es wird hier vom optimal effizientesten ausgegangen.

das gibt es ja als onlinegame - teste doch einfach mal

---

Der Lehrer hat gesagt dass wir zeigen sollen dass es für jeden möglichen Algorithmus gilt. Wir sollen nicht einen bestimmten Algorithmus benutzen.

---

Da liegt sicher ein Missverständnis vor. Mit "jedem" geht das bestenfalls schlechter bis schlimmstenfalls gar nicht.

---

Um n + 1 Scheiben zu transportieren Transportieren wir n Scheiben von der untersten erstmal auf einen anderen Stab. Dann legen wir die unterste Scheibe um und transportieren dann die n zuerst wegtransportierten auf diese umgelegte Scheibe drauf.

2^{n + 1} - 1 = (2^n - 1) + 1 + (2^n - 1)

2 * 2^n - 1 = 2 * 2^n - 1

wzbw.

---

Also kann man es generell sagen?

Der Lehrer hat gesagt man muss auch zum Beispiel den Fall berücksichtigen dass es wir m Scheiben auf einen Stab haben und n Scheiben auf einen anderen Stab haben.

---

Der Lehrer hat gesagt man muss auch zum Beispiel den Fall berücksichtigen dass es wir k Scheiben auf einen Stab haben und m Scheiben auf einen anderen Stab haben. 

(Ich habe die Symbole m und n geändert, da n die Anzahl der ganzen Scheiben sind.)

---

Das wären Zwischenzustände die auch nicht durch deine Formel oben abgedeckt werden.

Das generelle Problem lautet: Transferiere einen Turm mit n Scheiben von einem zum Anderen Stab unter zuhilfenahme eines dritten Stabes.

Aber du siehst ja in meiner Formel das ich auch einen Teilturm mit n Scheiben bewege. Das ist dann quasi ein Oberer Teilturm.

---

Wenn man in der Induktionsbehauptung, behauptet dass "wenn wir i Scheiben haben brauchen wir mindestens 2^i-1 Züge  (2 <= i <= n)", anstatt "wenn wir n Scheben haben brauchen wir mindestens 2^n-1 Züge" würde das nicht auch für ein Algorithmus gelten das erstmal z.B. m Scheiben transportiert und dann die restlichen? Oder macht das kein Unterschied?

---

Ich verstehe jetzt nicht ganz wo das Problem liegt ? Es ist egal ob du i oder n nimmst. Aber du solltest laut Aufgabenstellung zeigen dass 2^n - 1 Züge notwendig sind.

Möchtest du jetzt die Aufgabenstellung abändern?

---

Ich habe einen Algorithmus geschrieben und bei der Induktion habe ich diesen bestimmten Algorithmus beschrieben. Dann hat der Lehrer gesagt dass ich nicht einen bestimmen Algorithmus beschreiben soll. Es soll nämlich für alle mögliche Algorithmen gelten, auch z.B. für einen mit dem man in einen Zeitpunkt k Scheiben auf einen Stab hat und m Scheiben auf einen anderen Stab hat.

---

Es soll nämlich für alle mögliche Algorithmen gelten, auch z.B. für einen mit dem man in einen Zeitpunkt k Scheiben auf einen Stab hat und m Scheiben auf einen anderen Stab hat. 

Der Algorithmus bleibt ja immer der gleiche. Wenn du k Scheiben auf einem und m Scheiben auf einem anderen Stab hast ist noch die Frage ob auf dem einen die m untersten Scheiben und auf dem anderen die k obersten Scheiben liegen. Das muss ja auch nicht so sein. Man setzt hier halt nur später an. Das ist also quasi ein Zwischenzustand der noch nicht vollständig transferiert ist. 

Wie gesagt musste dann genau definiert werden wie die Scheiben nun vorliegen.

---

Also kann ich es folgenderweise formulieren?

Wenn man eine Scheibe hat, müssen wir die mindestens einmal transportieren. Also brauchen wir mindestens 1 Zug.

Wenn wir n Scheiben haben, behaupten wir dass wir mindestens 2^n-1 Züge brauchen, um die Scheiben zu bewegen.

Wenn wir n+1 haben, müssen wir folgendes machen:

Wir müssen die ersten n Scheiben mit mindestens 2^n-1 Züge von den ersten Stab weg transporieren.

Dann bewegen wir die grösste Scheibe, also die n+1.te, mindestens einmal, um ihn zu den richtigen Stab zu transportieren.

Dann transportieren wir wieder die n Scheiben auf die n+1.te mit mindestens 2^n-1 Züge.

Also, insgesamt brauchen wir mindestens (2^n-1)+1+(2^n-1)=2 *2^n-1=2ⁿ⁺¹-1 Züge um n+1 Scheiben zu transportieren.

Ist es richtig? Oder kann man besser formulieren?

Answer 2

Um n + 1 Scheiben zu transportieren Transportieren wir n Scheiben von der untersten erstmal auf einen anderen Stab. Dann legen wir die unterste Scheibe um und transportieren dann die n zuerst wegtransportierten auf diese umgelegte Scheibe drauf.

2^{n + 1} - 1 = (2^n - 1) + 1 + (2^n - 1)

2 * 2^n - 1 = 2 * 2^n - 1 

wzbw.

Comments

Beschreibt diese Methode die Scheiben zu transportieren nicht einen bestimmten Algorithmus?

---

Da steckt natürlich ein Algorithmus dahinter. Aber generell hat man hier keinen Algorithmus beschrieben sondern nur das Umlegen von Scheiben gezählt.

---

Ich habe die Türme aus Hanoi in meiner Spielesammlung. Aber wenn du sie nicht hast gibt es gute Versionen für Android.

https://play.google.com/store/apps/details?id=drv.games.timon