| Autor |
Beitrag |
    
el ramon
| | Veröffentlicht am Mittwoch, den 21. November, 2001 - 08:06: | 
|
FŸr das Spiel "Turm von Hanoi" benštigt man ein Brett, auf dem drei StŠbe A, B und C senkrecht stehen, und n runde Scheiben von verschiedener Gršsse, die in der Mitte ein Loch haben. Alle Scheiben sind auf A gesteckt und zwar so, dass keine Scheibe auf einer kleineren
Scheibe liegt. Die Aufgabe besteht darin, alle Scheiben auf B umzuschichten, wobei immer nur eine Scheibe auf eine kleinere gelegt werden darf. C dient zur Zwischenlagerung. Ermittle die Anzahl der dazu mindestens nštigen Umlegungen U(n) und beweise dies. |
Lola
| | Veröffentlicht am Mittwoch, den 21. November, 2001 - 12:14: |
|
Hallo el ramon,
Hast Du wirklich keinen besseren Titel gefunden? |
Thomas
| | Veröffentlicht am Mittwoch, den 21. November, 2001 - 12:24: |
|
ich nehme an, dir ist in der Aufgabenstellung ein Fehler unterlaufen, es muss doch immer eine kleinere auf einer grösseren Scheibe zu liegen kommen (?)
Also, wir stellen uns n Scheiben auf Stab A aufgestappelt vor, und zwar mit abnehmendem Radius nach oben. Das Ziel ist es, diese n Scheiben von Stab A auf B zu bringen, wenn nötig mit Umweg über C, sodass aber nie eine Scheibe grösseren Durchmessers auf eine kleineren Durchmessers zu liegen kommt.
für n=1 Scheiben, braucht man 1 Schritt, um von A auf B zu kommen
für n=2 Scheiben, braucht man 3 Schritte, um von A auf B zu kommen, nämlich zuerst die kleinere Scheibe auf C, die grössere auf B, dann von C auf B, also 3 Schritte
für n=3 Scheiben, braucht man 7 Schritte, um von A auf B zu kommen, nämlich die oberen beiden Scheiben auf C, dafür braucht man 3 Schritte (s. n=2 Scheiben), dann die unterste Scheibe auf Stab B und dann die anderen beiden Scheiben von C auf B, was wieder 3 Schritte braucht
Somit kommt man bald mal zu der Vermutung, dass es für n Scheiben 2^n-1 Schritte braucht, was zuerst natürlich noch bewiesen werden muss, dies mit Vollständiger Induktion:
Erwartung: für n+1 Scheiben braucht man 2^(n+1)-1 Schritte
Beweisführung:
man braucht 2^n-1 Schritte, um die ersten n Scheiben auf C zu bringen (analoge Überlegung wie bei n=3 Scheiben), dann 1 Schritt, um die unterste, übrig bleibende Scheibe von A auf B zu bringen, dann wieder 2^n-1 Schritte, um die n Scheiben von C auf B zu bringen, also im ganzen:
2^n-1 + 1 + 2^n-1 = 2*2^n-1 = 2^(n+1)-1, was mit der Erwartung bestens übereinstimmt
q.e.d. |
chnueschu
| | Veröffentlicht am Mittwoch, den 21. November, 2001 - 12:49: |
|
hi Thomas, hi el ramon.
dieses problem kann man mit einem kleinen umweg über eine rekursion lösen und muss dadurch nichts beweisen.
ich gehe davon aus, dass Thomas recht hat und kleinere scheiben auf grössere zu liegen kommen.
man kann sich folgende rekursion einfach überlegen:
U(n)=2*U(n-1)+1
-> um n scheiben auf B zu bringen brauche ich U(n-1) Züge, um die oberen n-1 scheiben auf C zu stellen. dann stelle ich verbleibende scheibe von A nach B (das entspricht der +1 in der formel). schliesslich braucht ich noch einmal U(n-1) Züge, um den turm von C nach B (auf die eine scheibe) zu stellen. und fertig.
das problem ist jetzt nur, dass du wahrscheinlich keine rekursive formel willst...
setze S(n)=U(n)+1.
dann ist S(0)=0+1=1.
wir setzen jetzt die rekursionsformel ein:
S(n)=(2*U(n-1)+1)+1=2*U(n-1)+2=2*(U(n-1)+1)=2*S(n-1)
damit können wir S(n) explizit definieren als:
S(0)=1
S(n)=2^n (n>1)
wir haben ja S(n)=U(n)+1 gesetzt. also ist
U(n)=S(n)-1=2^n-1
damit bin ich beim selben resultat wie Thomas.
gruss chnüschu. |
chnueschu
| | Veröffentlicht am Mittwoch, den 21. November, 2001 - 12:49: |
|
hi Thomas, hi el ramon.
dieses problem kann man mit einem kleinen umweg über eine rekursion lösen und muss dadurch nichts beweisen.
ich gehe davon aus, dass Thomas recht hat und kleinere scheiben auf grössere zu liegen kommen.
man kann sich folgende rekursion einfach überlegen:
U(n)=2*U(n-1)+1
-> um n scheiben auf B zu bringen brauche ich U(n-1) Züge, um die oberen n-1 scheiben auf C zu stellen. dann stelle ich verbleibende scheibe von A nach B (das entspricht der +1 in der formel). schliesslich braucht ich noch einmal U(n-1) Züge, um den turm von C nach B (auf die eine scheibe) zu stellen. und fertig.
das problem ist jetzt nur, dass du wahrscheinlich keine rekursive formel willst...
setze S(n)=U(n)+1.
dann ist S(0)=0+1=1.
wir setzen jetzt die rekursionsformel ein:
S(n)=(2*U(n-1)+1)+1=2*U(n-1)+2=2*(U(n-1)+1)=2*S(n-1)
damit können wir S(n) explizit definieren als:
S(0)=1
S(n)=2^n (n>1)
wir haben ja S(n)=U(n)+1 gesetzt. also ist
U(n)=S(n)-1=2^n-1
damit bin ich beim selben resultat wie Thomas.
gruss chnüschu. |
|
