counterto - Di 28.03.06 18:46
Titel: 3 Türme [Klassisches Informatik Problem]

---

hallo an die großen Denker da draussen!,

ich suche schon seit längerem eine Formel um folgendes auszurechnen.
Kurz zu dem Problem:
Man hat 3 Türme; anfangs sind 3 holzstücke (unterschiedlicher größer) auf dem mittlerem Turm gestapelt. Nun soll man mit möglichst wenigen Versuchen versuchen, diese Holzstapel auf einen anderen Turm zu stapeln. Hierbei muss folgendes beachtet werden: Man darf immer nur ein Holzstapel bewegen, man darf keinen größeren Holzstapel auf einen kleineren legen, nur umgekehrt, d.h. groß-mittel-klein (nicht aber: mittel-groß-klein.) Ich denke bis hierhin kann man das verstehen. Im Anhang ist ein Bild. (ein Bild sagt mehr als 1000 Worte.)
Für 3 Holzstapel ist das noch recht einfach zu lösen. man braucht 7 Versuche.

jetzt aber wieder zu meiner Fragesetllung: Wie viel Versuche braucht man denn bei 4,5,6,7 usw. Holzstapeln? => Hierfür suche ich eine Formel.


ich hoffe ihr könnt mir helfen!

Gausi - Di 28.03.06 18:56

---

Das sind die "Türme von Hanoi", die du da beschreibst. man braucht (2^n)-1 Schritte, um den Turm zu verschieben.

counterto - Di 28.03.06 19:03

---

danke danke danke

wusste ich nicht

Jakob Schöttl - Fr 19.05.06 19:17

---

hierzu mal ne frage, wenn nochmal jemand bei diesem thema vorbeischaut:

Wenn ihr einen stapel mit z. B. 6 hölzchen habt, dann müsst ihr also auch genausoviel (6) Türme haben, oder?

Gausi - Fr 19.05.06 19:20

---

Nein. Die Anzahl der Türmchen, die man zum verschieben benötigt, ist immer drei: Der Quellturm, der Zielturm und einer zum Zwischenstapeln.
Theoretisch kann man das auch mit 1000 Scheiben und 3 Stapeln machen. Aber ob dazu die Zeit ausreicht, die unser Universum existiert...:nixweiss:

Balmung der blaue Gott - Fr 19.05.06 19:20

---

bokaj hat folgendes geschrieben:

hierzu mal ne frage, wenn nochmal jemand bei diesem thema vorbeischaut: Wenn ihr einen stapel mit z. B. 6 hölzchen habt, dann müsst ihr also auch genausoviel (6) Türme haben, oder?

Nein nur drei (sonst wär das doch viel zu einfach).
Ich such mal den Link zu 'nem guten Tutorial darüber...
http://www.dsdt.info/tutorials/rekursion/

Jakob Schöttl - Fr 19.05.06 20:02

---

Noch ne frage:

darf (vorallem bei mehr als 3 stäbchen) ein langes unten liegen, und darüber eins liegen, das zwar kürzer ist, aber nicht (unbedingt) das nächstkleinere zu dem ist das unten liegt?

Ich weiß schwierig formuliert, mir fällt aber nichts besseres ein!

Gausi - Fr 19.05.06 21:38

---

Ja.