Rekursionsformel, Türme von Hanoi

Question

Aufgabe:

Das Spiel die Türme von Hanoi besteht aus drei gleich
großen Stäben A, B und C, auf die mehrere gelochte Scheiben gelegt werden, alle
verschieden groß. Zu Beginn liegen alle Scheiben auf Stab A, der Größe nach geordnet,
mit der größten Scheibe unten und der kleinsten oben. Ziel des Spiels ist
es, den kompletten Scheibenstapel von A nach C zu versetzen. Dabei dürfen nie
größere Scheiben oberhalb von kleineren Scheiben liegen. Finden Sie eine Rekursionsformel
für die Anzahl Spielzüge, um n Scheiben von A nach C zu versetzen.

Problem/Ansatz:

Angenommen es liegen drei Ringe im Stab A. Dann ist der erste Schritt, den obersten nach C zu befördern. Danach den mittleren nach B, dann den obersten von C nach B. Dann den Untersten von A nach C. Danach den obersten von B nach A, Dann den mittleren von B nach C, dann den obersten von A nach C. Das sind dann insgesamt 8 Schritte.

Wie komme ich jetzt davon auf die Rekursionsformel?

Comments

Das sind dann insgesamt 8 Schritte.

Nein, das waren nur 7.

Die größte Scheibe wurde einmal bewegt, die mittlere zweimal und die kleinste viermal.

Wenn es 4 Scheiben sind, müssen zuerst die oberen drei Scheiben als Dreieturm auf eine andere Position gebracht werden

(in 7 Schritten),

dann muss die größte Scheibe umgesetzt werden

(1 Schritt),

dass muss der Dreierturm auf die größte Scheibe umgesetzt werden

(in 7 Schritten).

Man braucht also zweimal 7 Schritte und einen weiteren.

PS: Die gleiche sinngemäß gleiche Erklärung hat Werner gerade geliefert.

Answer 1

Wie im letzten Problem bezeichen \( \varphi(n) \) die Anzahl an Zügen. Wenn du schon weisst, wie du das Spiel mit \( n \) Ringen gewinnen kannst, wie kannst du dann eine Strategie für \( n+1 \) Ringe erhalten? Naja, du könntest z.B. erst das Ganze mit den ersten \( n \) Ringen lösen und als Zielstab \( B \) wählen. Als nächstes beförderst du den \( n+1 \) ten Ring von \( A \) nach \( C \) und löst dann das Ganze nochmal mit den \( n \) Ringen auf \( B \). Somit ergibt sich
\( \begin{aligned} \varphi(n+1) &=\underbrace{\varphi(n)}_{\text {erstes Mal lösen }}+\underbrace{1}_{n+1 \text { ten Ring bewegen }}+\underbrace{\varphi(n)}_{\text {zweites Mal lösen }} \\ &=2 \varphi(n)+1 \end{aligned} \)

Comments

Das erste \( \varphi(n) \) (erstes Mal lösen), damit ist dann gemeint, dass der oberste Ring von A nach B wandert, oder?

Oder ist damit gemeint, dass zuerst der oberste von A nach B wandert, dann der darunter von A nach C, und dann der von C nach B?

---

Das erste \( \varphi(n) \) (erstes Mal lösen), damit ist dann gemeint, dass der oberste Ring von A nach B wandert, oder?

Nein - damit ist gemeint, dass die \(n\) obersten Ringe - also alle bis auf den untersten - als eine Einheit von A nach B wandern.

---

He? Wie soll das denn gehen? Man kann doch immer nur einen gleichzeitig bewegen, oder nicht? Ich glaube, ich habe die Aufgabe dann völlig falsch verstanden.

Es geht also um die Züge insgesamt, pro Einheit quasi, und nicht, um die einzelnen Ringe als quasi je 1 Zug?

---

He? Wie soll das denn gehen? Man kann doch immer nur einen gleichzeitig bewegen, oder nicht? Ich glaube, ich habe die Aufgabe dann völlig falsch verstanden

Du hast die Aufgabe schon richtig verstanden.

Starten wir mal mit 4 Ringen (\(n+1=4\)). Dann überlegt man sich zunächst, wie man die 3 obersten nach B bekommt. Dazu müssen die 2 obersten erst nach C und dazu wiederum der oberste (die #1) nach B.

Jetzt #2 nach C und #1 obendrauf. Nun kann man #3 von A nach B legen und der 'Berg' aus #2 und #1 wandert nun von C nach B, indem #1 erst nach A, #2 nach B und #1 oben auf B drauf.

Nun ist die Hälfte geschafft. Die obersten 3 liegen auf B (\(\varphi(3)=7\)). Jetzt #4 nach C (1 Schritt) und dann den 'Berg' von B wieder mit 7 Schritten von B über A nach C wandern lassen.

In Kürze waren das soviel Schritte$$\varphi(4)= \underbrace{\varphi(3)}_{\underbrace{\varphi(2)}_{\varphi(1)+1+\varphi(1)} + 1 + \varphi(2)} + 1 + \varphi(3)$$

---

Ich kann das zwar fast alles nachvollziehen, aber das selbst zu reproduzieren, würde mir schwer fallen.

Bei der Formel unten. Jetzt erkenne ich die Gemeinsamkeit.

Für \( \varphi(4) \) gilt   \( \varphi(3) \) + 1 + \( \varphi(3) \)

Für \( \varphi(3) \) gilt \( \varphi(2) \) + 1 + \( \varphi(2) \)

Wobei dann bei \( \varphi(4) \) die \( \varphi(3) \) Sieben Schritte darstellt, oder? Dann +1 für den 4. Ring, und dann nochmal 7 Schritte mit \( \varphi(4) \), um den Turm zurückzubauen?

\( \varphi(n) \)  = \( \varphi(n-1) \) + 1 + \( \varphi(n-1) \) ?

---

.. ist alles richtig!

Hinweis: \(\varphi(1)=1\) und \(\varphi(n)=2^n-1\)

---

Danke!

Warum \(\varphi(n)=2^n-1\)?

Dann wäre ja bei:

 \( \varphi(2) \) = \( \varphi(1) \) + 1 + \( \varphi(1) \)

\( \varphi(2) \) = 2^2 -1 = 3.

ja,stimmt, das passt.

---

Warum \(\varphi(n)=2^n-1\)?

Warum nicht? ;-)

Probier's aus. $$\begin{array}{r|r}n& \varphi(n)\\\hline 1& 1\\ 2& 3\\ 3& 7\\ 4& 15\\ 5& 31\\ 6& 63\\ 7& 127\\ 8& 255\\ 9& 511\\ 10& 1023\end{array}$$

Du kannst ja mal versuchen, es mittels Vollständige Induktion zu beweisen.

Answer 2

Rekursionsformel für die Anzahl Spielzüge, um n Scheiben von A nach C zu versetzen: a₁==1, a_n+1=2a_n+1. ....