| Autor |
Beitrag |
    
Alex (Paint)
| | Veröffentlicht am Dienstag, den 23. Januar, 2001 - 10:12: | 
|
Hallo kann mir jemand helfen?
Habe folgende Aufgabe gestellt bekommen und habe keinen blassen Schimmer!
Prove that Towers of Hanoi can be solves for any number n € N of discs by reducing the case of n discs to the case of n - 1 discs. Before doing this you must find a formal describtion of the statement "ToH can be solved for any number n of discs".
Kann mir jemand helfen? |
joerg
| | Veröffentlicht am Dienstag, den 23. Januar, 2001 - 21:07: |
|
Hallo Alex:
Ich denke, man sollte das Problem folgendermaßen angehen: Wenn man den Turm mit n Platten verlegt hat, ist der Unterschied zur Platte n+1 folgender:Wenn man von drei Stäben ausgeht, auf denen die Platten verteilt sind, würde man n Platten z.B. von links nach rechts bewegen (Mitte bleibt leer) und dann die Platte n+1 in die Mitte bewegen, um dann die ersten n Platten ebenfalls in die Mitte zu setzen. Demnach müßte man für n+1 Platte einen Zug mehr als doppelt so viele wie für
n Platten brauchen.
Für n Platten werden übrigen 2^n+1 Züge benötigt, warum weiß ich im Moment nicht mehr, habe ich aber mal gelesen, und für mein eigenes Modell mit 5 Platten stimmt's auch. Das war jetzt sicher nicht unbedingt super mathematisch, aber immerhin ein Denkanstoß!
Gruß
Jörg |
Hans (Birdsong)
| | Veröffentlicht am Freitag, den 26. Januar, 2001 - 16:42: |
|
Hallo :
Die Ueberlegung von Joerg ist vollkommen richtig.
Bezeichnet man die Anzahl der Bewegungen mit A(n),
so laeuft das auf die Rekursionsformel
A(n+1) = 2 A(n) + 1
hinaus. Zusammen mit der Anfangsbedingung A(1) = 1
findet man dann der Reihe nach
n | 1 2 3 4 5
----------------------- etc.
A(n)| 1 3 7 15 31
Man vermutet die explizite Formel
A(n) = 2^n - 1
deren Beweis leicht durch vollstaendige Induktion
zu erbringen ist.
Hans |
Devender
| | Veröffentlicht am Donnerstag, den 13. Dezember, 2001 - 17:03: |
|
Hallo !!
Ich bäuchte das Delphi Script für das spiel Towers of Hanoi , da ich darüber ein Referat halten sol, aber nicht so viel ahnung habe !
Hoffe ihr könnt mir weiter helfen ! |
|
