Turm von Hanoi < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:30 Mi 20.10.2010 | | Autor: | ella87 |
| Aufgabe | Wir ändern die Regeln des Turms von Hanoi:direkte Übergänge von Stapel 1 zu Stapel 3 und umgekehrt sind nun nicht mehr erlaubt.
(a)Zeichne den Graphen der zum Spiel mit 2 Scheiben gehört.
(b)Zeige, dass das Spiel für jede Anzahl von Scheiben eine Lösung hat, das heißt, dass alle Scheiben von Stapel 1 auf Stapel 3 gebracht werden können.
(c)Wieviele Züge sind nötig für das Spiel mit n Scheiben? |
Hallo!
Das Prinzip hab ich verstanden. Den Graph zu (a) auch schon gezeichnet. Ich kann ja mal beschreiben:
man hat quasi eine Pyramide (oder eher ein Dreieck)
33
*
32 **** 31
*
12 21
* * *
11 13 **** 23 *** 22
und um den Turm von Stapel 1 nach Stapel 3 zu buxieren, muss man alle möglichen (d.h. erlaubten Züge durchlaufen).
"23" heißt übrigens große Scheibe auf Stab 2 und kleine Scheibe auf Stapel 3.
zu (b):
ich versage. Das Prinzip bleibt klar. Für 3 Scheiben kann man auch noch den Graphen zeichnen, aber dann...und wie zeigen? Vermutung: Indution. Problem: wie aufschreiben???
und (c):
Man hat [mm]3^n[/mm] Ecken, also benötigt man [mm]3^n-1[/mm] Züge.
aber die (b)....
Wäre für Hilfe echt Dankbar
(Bemerkung: Indution hatten wir noch nicht in der VL)
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:10 Mi 20.10.2010 | | Autor: | abakus |
> Wir ändern die Regeln des Turms von Hanoi:direkte
> Übergänge von Stapel 1 zu Stapel 3 und umgekehrt sind nun
> nicht mehr erlaubt.
> (a)Zeichne den Graphen der zum Spiel mit 2 Scheiben
> gehört.
> (b)Zeige, dass das Spiel für jede Anzahl von Scheiben
> eine Lösung hat, das heißt, dass alle Scheiben von Stapel
> 1 auf Stapel 3 gebracht werden können.
> (c)Wieviele Züge sind nötig für das Spiel mit n
> Scheiben?
> Hallo!
>
> Das Prinzip hab ich verstanden. Den Graph zu (a) auch schon
> gezeichnet. Ich kann ja mal beschreiben:
>
> man hat quasi eine Pyramide (oder eher ein Dreieck)
> 33
> *
> 32 **** 31
> *
> 12 21
> * * *
> 11 13 **** 23 *** 22
>
> und um den Turm von Stapel 1 nach Stapel 3 zu buxieren,
> muss man alle möglichen (d.h. erlaubten Züge
> durchlaufen).
> "23" heißt übrigens große Scheibe auf Stab 2 und kleine
> Scheibe auf Stapel 3.
>
> zu (b):
> ich versage. Das Prinzip bleibt klar. Für 3 Scheiben kann
> man auch noch den Graphen zeichnen, aber dann...und wie
> zeigen? Vermutung: Indution. Problem: wie aufschreiben???
>
> und (c):
> Man hat [mm]3^n[/mm] Ecken, also benötigt man [mm]3^n-1[/mm] Züge.
>
> aber die (b)....
> Wäre für Hilfe echt Dankbar
> (Bemerkung: Indution hatten wir noch nicht in der VL)
Hallo,
"früher" haben wir alle (n-1) Scheiben auf dem Mittelplatz "zwischengelagert" um die unterste Scheibe von 1 auf 3 zu legen.
Das (1 auf 3) geht jetzt nicht mehr.
Also muss alles auf 3 zwischengelagert werden, um die große Scheibe von 1 auf 2 zu legen. Dann den Restturm von 3 auf 1 bringen (um auf 3 Platz zu machen für die große Scheibe). Dazu muss die zweitgrößte Scheibe auf 1, aber nicht direkt, sondern mit Zwischenablage auf 2. Damit dort Platz ist, müssen die n-2 kleinsten Scheiben auf 1 zwischengelagert werden....
Wir verallgemeinern:
Die Scheibe mit der Nummer n kann auf ein Nachbarfeld gebracht werden, wenn der Turm mit der Nummer 1 bis n-1 auf das übernächste Feld gebracht werden kann; das ist möglich, wenn man diesen Teilturm erst komplett auf den Nachbarplatz und erst von dortaus auf den Zielplatz umsetzten kann.
Diese unterste (n-1)-Scheibe kann man umsetzten, wenn man den (n-2)-Turm umsetzten kann.
Den kann man umsetzen, wenn man den (n-3)-Turm umsetzten kann,
Den kann man umsetzen, wenn...
...
Den Teilturm aus den zwei kleinsten Scheiben kann man umsetzten, wenn man die oberste Scheibe versetzen kann (und das kann man natürlich).
Da man immer kleine Teiltürme umsetzt und die größeren Scheiben so lange liegen lässt, bis der Turm aus den kleineren Scheiben komplett versetzt ist, gibt es kein Hindernis zum Umsetzten des gesamten Turms.
Gruß Abakus
|
|
|
|
