ich hoffe ihr kennt den Turm von Hanoi.
Bei meiner Frage geht es aber darum einen Scheibenstapel von einer Stange in einzelnen Zügen auf eine andere Stange umzustapeln–allerdings gibt es hier vier Stangen.
-§ Scheiben lassen sich in 5 Zügen,4 Scheiben lassen sich in 9 Zügen umstapeln.Probiere es.
Nun möchte ich wissen,wie viele Züge sind für 5,6,7 und 8 Scheiben nötig?(kleinstmögliche Anzahl von Zügen angeben)Gibt es eine mathematische Gleichung für die Egebnisse?
Wer kann mir helfen?
Hallo,
bei dem von Dir vermutlich verwendeten Schema läuft es auf die Regel zuege(n)=2*zuege(n-2)+3 hinaus (n ist dabei die Anzahl der Scheiben und zuege(1)=1, zuege(2)=3). Das Schema stapelt zunächst die obersten n-2 Scheiben der Ausgangsstange (z.B. A) auf eine verfügbare Stange (z.B. B), dann von den verbleibenden 2 Scheiben des Ausgangsstapel (A) die oberste auf die weitere verfügbare Stange (z.B. C), danach die letzte Scheibe des Ausgangsstapels auf die Zielstange (z.B. D), die ehemals zweioberste (von Stange C) auf die Zielstange (D) und letzlich die n-2 Scheiben (von Stange B) auf die Zielstange (D). Beim Umstapeln der n-2 Scheiben ergibt sich ein gleichwertiges Problem, da keine der beteiligten Scheiben größer als eine schon auf den Stangen befindliche ist. Das Rekursionsschema kann sicher auch geschlossen angegeben werden (schau ich mir morgen an) aber die wirklich interessante Frage (die ebenfalls erst morgen dran ist), ist ob die so erzielte Anzahl von Zügen wirklich minimal ist.
Gruss
Enno
Hallo,
dazu splittet man am besten zuege in gerade und ungerade Scheibenzahlen und erhält:
zuege(2*k)=3*(2k-1)=3*2k-3
zuege(2*k+1)=2k+2-3=4*2k-3
für ein natürliches k>=0. Das ganze ließe sich natürlich auch direkt zu
zuege(n)=(3+(n mod 2))*2n/2-3
verwursten (mit „mod 2“ Rest der Division durch 2 und „/2“ ganzzahlige Division durch 2).
Gruss
Enno
Wg. Minimalität
Hallo,
bekomme ich vor meinen Urlaub nicht mehr hin. Wer sich damit beschäftigen will. M.M. fährt man besser mit einer iterativ beschriebenen Lsg.-Strategie (z.B. Abwandlung des Buneman-Levy Algorithmus für die „original“ Problem mit 3-Stangen oder manuelles Aufdröseln der rekursiven Vorschrift). Evtl. könnte man nun zeigen, daß jede Abweichung von diesem Schema keine Schritte einspart (und meistens sogar mehr produziert). Damit wäre gezeigt, daß die durch das Schema notwendigen Schritte minimal sind.
Gruss
Enno