Türme von Hanoi (4Stäbe) < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | ( "Turm von Hanoi" mit vier Stäben) Es seien n Scheiben auf einen von vier
Stäben, so dass jede Scheibe auf einer größeren Scheibe liegt. Das Ziel ist, allen Scheiben
auf eine der leeren Stäben zu bringen, wobei dieselben Regeln wie im Fall mit drei Stäben
zu beachten sind.
Man beschreibe eine Rekursion, die das Problem so löst, dass alle Stäbe benutzt werden
und man zeige mit Induktion eine Formel für die benötigte Anzahl von Schritten. |
Hallo erstmal,
Der Turm von Hanoi mit drei Stäben lässt sich ja mit [mm] 2^n-1 [/mm] Schritten lösen und mit Induktion beweisen..
Doch wie stelle ich das ganze mit den selben Bedingungen, nur mit vier Stäben an (also Rekursion bilden und mit Induktion die Formel beweisen)?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:06 So 19.11.2017 | | Autor: | abakus |
Spiele es erst mal durch mit 2,3,4,5,6 Scheiben.
Wie viele Schritte brauchst du jeweils?
|
|
|
| |
|
Bei 2 Scheiben, drei Schritte, bei drei Scheiben 5 Schritte, bei vier Scheiben 12 Schritte, bei 5 Scheiben x Schritte, bei 6 Scheiben x Schritte.
Und bei 5 und 6 komme ich schon nicht mehr mit dem Mitzählen und gleichzeitig vorstellen was passiert hinter her.
Wie hilft mir das aber weiter?
|
|
|
|
![[]](/images/popup.gif){kind=small}
mathematischen Basteleine