Türme von Hanoi [gelöst] |
| 15.06.2004, 21:15 | Mazze | Auf diesen Beitrag antworten » |
Türme von Hanoi [gelöst]
Geschichte Ein Mönch im Kloster zu Hanoi bekam die Aufgabe 64 scheiben vom ersten Turm auf den dritten zu legen. Es gab 3 Türme und 64 Scheiben die alle unterschieldich groß sind und geordnet vorliegen. Folgende Regeln: 1. Es darf immer nur eine Scheibe bewegt werden. 2. Es dürfen nur kleinere Scheiben auf größere Gelegt werden 3. Die Scheiben müssen komplett und geordnet auf Turm 3 liegen Hier ein Bild  http://www.mathematische-basteleien.de/hanoi01.gifSo nun die Frage: Wieviele Züge muss der Mönch machen um alle 64 Scheiben auf Turm 3 zu bekommen? (Bedenkt es handelte sich der Legende nach um massive Steinplatten) Tip: Versucht ein allgemeines Schema für die Bewegung zu abstrahieren und dann stellt eine Funktion auf 
viel spaß Anmerkung: Man kann natürlich die Zahlreichen Dokumentationen des "Phänomens" im internet bewundern, aber hat nur halb soviel Spaß dann ; ) |
||
| 02.07.2004, 10:07 | KnightMove | Auf diesen Beitrag antworten » |
2^64-1 |
||
| 05.07.2004, 08:07 | Mazze | Auf diesen Beitrag antworten » |
Ja so ist es, stellt euch den armen mönch vor, sagen wir er brauchte 1 min für einen Zug. Das dauert länger als die Erde alt ist. ~3,5*10^13 Jahre wenn ich richtigumgerechnet hab. Mein Rechner is bei der umsetzung des problems bei 47 Scheiben gescheitert. (bzw. mir hats dann zu lang gedauert) |
||
| 22.07.2004, 03:20 | Xmas | Auf diesen Beitrag antworten » |
also für n=1,2,3,4,5,...... x=(2^n)-1 also der mönch darf 2^64 -1 mal umschichten ^^ das sind 18.446.744.073.709.551.615 also rund 18,5 trilionen mal lol der arme der wird sicher :P |
||
| 23.07.2004, 14:11 | Philipp-ER | Auf diesen Beitrag antworten » |
Noch der Beweis: Der Induktionsanfang für n=1 ist trivialerweise richtig. Seien n+1 Scheiben gegeben. Durch 2^n-1 Züge werden die n kleineren Scheiben auf Stift 2 gelegt, durch einen Zug die größte Scheibe auf Stift 3 und durch weitere 2^n-1 Züge die kleineren ebenfalls auf Stift 3, womit die Aufgabe erfüllt ist. Dafür werden insgesamt 2^n-1+1+2^n-1=2*2^n-1=2^(n+1)-1 Züge benötigt, damit ist die Formel bewiesen. |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
|
