Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Die Türme von Hanoi
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> Die Türme von Hanoi
 
Autor Nachricht
nico123
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 30.10.2005
Beiträge: 224

BeitragVerfasst am: 27 Okt 2006 - 19:46:44    Titel: Die Türme von Hanoi

Hier mal eine interessante aufgabe!


Das Spiel Türme von Hanoi besteht aus drei Stäben A, B und C, auf die
n gelochte Scheiben gelegt werden, alle verschieden groß. Zu Beginn liegen
alle Scheiben auf Stab A, der Größe nach geordnet, mit der größten Scheibe
unten und der kleinsten oben. Ziel des Spiels ist es, den kompletten
Scheiben-Stapel von A nach C zu versetzen.
Bei jedem Zug darf die oberste Scheibe eines beliebigen Stabes auf einen
der beiden anderen Stäbe gelegt werden, vorausgesetzt, dort liegt nicht
schon eine kleinere Scheibe. Folglich sind zu jedem Zeitpunkt des Spieles
die Scheiben auf jedem Feld der Größe nach geordnet.
Beweisen Sie mit vollständiger Induktion, daß das Ziel des Spiels mit
(2^n) − 1 Zügen zu schaffen ist.


Zuletzt bearbeitet von nico123 am 28 Okt 2006 - 10:17:01, insgesamt einmal bearbeitet
take
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 03.11.2005
Beiträge: 1018

BeitragVerfasst am: 27 Okt 2006 - 20:14:43    Titel:

Wie willst Du es schon bei 3 Scheiben mit 2*3 - 1 = 5 Zügen schaffen?
Die ersten beiden Züge werden benötigt, um die Scheiben auf die 3 Stangen zu verteilen, damit man an die größte herrankommt. Beim 3. Zug muss man nun die kleinste auf die mittlere Scheibe legen, damit das Spiel sinnvoll weiter geht. Beim 4. Zug wird nun die größte Scheibe nach C bewegt. Nun liegen aber noch die mittlere und darauf die kleinste auf B. Wie sollen beide nun in einem Zug auf C kommen?
Hiob
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 04.05.2005
Beiträge: 1379

BeitragVerfasst am: 27 Okt 2006 - 21:41:06    Titel:

nico123 hat folgendes geschrieben:
Hier mal eine interessante aufgabe!
Ja, die is nich schlecht, nich schwer, aber nich schlecht. Zumindest, wenn man den Schreibfehler entfernt hat.
(2n-1∧n=3)⇒2n-1=
take hat folgendes geschrieben:
2*3 - 1 = 5
Alrighty then... 2^n-1?
riwe
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 02.10.2006
Beiträge: 279
Wohnort: linz

BeitragVerfasst am: 27 Okt 2006 - 22:41:13    Titel:

ja richtig ist: in 2^n-1 zügen machbar.
beweisidee: betrachte die n+1 scheiben als 2 scheibenpakete, die oberen n und die größte untere, und die bleibt einfach liegen, bis die oberen n umgeschaufelt sind, dann legt man die unterste um, und dann die n anderen wieder auf sie drauf,
daher brauchst du für (n + 1) scheiben 2(2^n - 1)+ 1 züge.
werner
nico123
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 30.10.2005
Beiträge: 224

BeitragVerfasst am: 28 Okt 2006 - 10:08:07    Titel:

aber wie schreibe ich das jetzt mathematisch korrekt auf? ihr habt natürlich recht...... war ein tippfehler!
riwe
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 02.10.2006
Beiträge: 279
Wohnort: linz

BeitragVerfasst am: 28 Okt 2006 - 11:12:15    Titel:

riwe hat folgendes geschrieben:
ja richtig ist: in 2^n-1 zügen machbar.
beweisidee: betrachte die n+1 scheiben als 2 scheibenpakete, die oberen n und die größte untere, und die bleibt einfach liegen, bis die oberen n umgeschaufelt sind, dann legt man die unterste um, und dann die n anderen wieder auf sie drauf,
daher brauchst du für (n + 1) scheiben 2(2^n - 1)+ 1 züge.
werner


aus dem da zitierten hast du die rekursionsformel:
z(n+1) = 2z(n)+1 mit z(1) = 1
z(n) anzahl der züge bei n scheiben.
z(1) = 1, z(2) = 3, z(3)=7....=> vermutung z(n) = 2^n -1
in die rekursionsformel eingesetzt, ergibt
z(n+1) =2*(2^n-1)+1 = 2^(n+1) -1.
werner
nico123
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 30.10.2005
Beiträge: 224

BeitragVerfasst am: 28 Okt 2006 - 11:51:42    Titel:

in deiner letzten zeile steht jetzt aber:

z(n+1) = 2^(n+1)-1

irgendwas stimmt da nicht...... aber ich habe es jetzt verstanden! vielen dank!
Hiob
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 04.05.2005
Beiträge: 1379

BeitragVerfasst am: 28 Okt 2006 - 12:32:11    Titel:

Vollständige Induktion, weißt Du?
riwe
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 02.10.2006
Beiträge: 279
Wohnort: linz

BeitragVerfasst am: 28 Okt 2006 - 13:03:43    Titel:

nico123 hat folgendes geschrieben:
in deiner letzten zeile steht jetzt aber:

z(n+1) = 2^(n+1)-1

irgendwas stimmt da nicht...... aber ich habe es jetzt verstanden! vielen dank!

doch da stimmt schon alles.
aber schön, wenn du es verstanden hast! Embarassed
werner
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> Die Türme von Hanoi
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum