Türme von Hanoi Induktion

Question

es geht um eine Induktionsaufgabe bezüglich der Türme von Hanoi. Die Aufgabe ist ja alt und schon bekannt, daher hier meine Abwandlung: Ich habe einen Algorithmus gegeben und soll nun beweisen, dass dieser das Umlegen der Türme in Minimalzeit berechnet.

Mein Ansatz für die Induktion wäre es, einmal zu zeigen, dass der Algorithmus mindestens eine Laufzeit von 2^n-1 hat und danach mit einer zweiten Induktion zu zeigen, dass der Algorithmus höchstens eine Laufzeit von 2^n-1 hat. Ist das grundsätzlich richtig?

Mir fehlt nämlich komplett der Ansatz, da wir bis dato nur herkömmliche (einfache) Induktionen gemacht haben. Hat jemand Rat?

Comments

Kann es sein, dass das, was du "Laufzeit" nennst, die Anzahl der Spielzüge ist?

---

Mein Ansatz für die Induktion wäre es, einmal zu zeigen, dass der Algorithmus mindestens eine Laufzeit von 2^n-1 hat und danach mit einer zweiten Induktion zu zeigen, dass der Algorithmus höchstens eine Laufzeit von 2^n-1 hat. Ist das grundsätzlich richtig?

Den ersten Teil brauchst du nicht zeigen. Es langt zu zeigen, dass der Algorithmus höchstens eine Laufzeit von 2^n - 1 hat. Dazu musst du aber wissen das 2^n - 1 die beste Laufzeit ist.

Dazu brauchst du eventuell die Anzahl Spielzüge die man braucht um einen fertigen Turm der Höhe n zu versetzen. Diesen baut man rekursiv auf.

Einen Turm der Höhe 1 versetze ich in einem Schritt.

Bei einem Turm der Höhe n versetze ich einen Turm der Höhe n - 1, dann eine einzelne Scheibe und dann erneut einen Turm der Höhe n - 1.

N(1) = 1

N(2) = 2*1 + 1 = 3

N(3) = 2*3 + 1 = 7

N(4) = 2*7 + 1 = 15

Vermutung

N(n) = 2^n - 1

---

Danke dir Der_Mathecoach.

Also lege ich zunächst mittels Annäherung die Vermutung fest auf die Laufzeit und beweise diese im Folgenden durch Induktion?

LG,

Nico