Konvergenz von Folgen < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:20 Do 03.11.2005 | | Autor: | AriR |
Das folgende Problem ist auch als T¨urme von Hanoi
bekannt. Gegeben seien n Scheiben unterschiedlichen Durchmessers, die der Gr¨oße nach zu einem Turm
aufgeschichtet sind, wobei die Gr¨oße der Scheiben nach oben hin abnimmt. Es existieren drei Pl¨atze 0, 1
und 2. Der Ausgangsturm befindet sich auf Platz 0. Die Aufgabe besteht nun darin, unter Verwendung des
Hilfsplatzes 2 den Turm auf den Platz 1 umzuschichten. Dabei sind stets zwei Bedingungen einzuhalten:
Es darf in jedem Schritt nur eine Scheibe, und zwar die oberste eines Turms, bewegt werden.
Zu keiner Zeit darf eine gr¨oßere Scheibe auf einer kleineren liegen.
L¨osen Sie nun die folgenden Aufgaben:
(a) Stellen Sie sowohl die Ausgangs- als auch die Endsituation des Problems f¨ur n = 4 graphisch dar.
(b) Geben Sie eine optimale L¨osungsstrategie f¨ur T¨urme mit n = 1, n = 2 und n = 3 Scheiben an. Wie
viele Schritte werden ben¨otigt?
(c) Versuchen Sie nun, eine optimale Strategie f¨ur n = 4 T¨urme zu finden, indem Sie sich nach M¨oglichkeit
auf die bisher gefundenen L¨osungswege abst¨utzen. Sie sollten dabei nicht mehr als 15 Schritte
ben¨otigen.
(d) Nehmen Sie Stellung zu der Behauptung: Das Verfahren ist verallgemeinerbar. Man kann eine
L¨osung f¨ur n Scheiben bereits aus einer L¨osung f¨ur n−1 Scheiben gewinnen. Zeigen Sie exemplarisch,
dass diese Behauptung f¨ur n = 4 und n = 5 Scheiben jeweils G¨ultigkeit hat.
hey leute diese fragen sind gestellt und ich hab auch alle bis auf d), nur da hab ich etwas schwierigkeiten mit.
habt ihr da vieleicht eine Ahnung?? Hatte mir überlegt, dass man zB bei n=5 (also bei 5 steinen) den größten stein außer acht lässt und das selbe durchführt für die restlichen 4, als wenn man nur 4 stein hätte aber das klappt auch irgendwie nicht =(.. wäre froh, wenn mir da einer helfen könnte oder auf den richtigen gedanken bringt. danke ari
|
|
|
![[]](/images/popup.gif){kind=small}
http://www.matheprisma.uni-wuppertal.de/Module/Rekurs/Seite05.htm