Arbeitsblatt: Arbeitsblatt - Türme von Hanoi

Material-Details

Einführendes Arbeitsblatt zur Beweisprinzip der vollständigen Induktion
Mathematik
Höhere Mathematik (Gymnasialstufe)
11. Schuljahr
2 Seiten

Statistik

152084
666
1
13.10.2015

Autor/in

Christian Schmitz
Land: Deutschland
Registriert vor 2006

Downloads Arbeitsblätter / Lösungen / Zusatzmaterial

Die Download-Funktion steht nur registrierten, eingeloggten Benutzern/Benutzerinnen zur Verfügung.

Textauszüge aus dem Inhalt:

Einschub: Vollständige Induktion B1 Die Türme von Hanoi In einem Tempel in Hanoi sind 3 Stangen aufgestellt, auf deren erster 100 jeweils verschieden große Silberscheiben der Größe nach geordnet liegen. Jeder Pilger muss eine Scheibe auf eine andere Stange setzten, aber so, dass keine Scheibe auf einer kleineren liegt. Wenn durch die Pilger alle Scheiben von der 1. Stange zur 3. Stange (der Größe nach geordnet) gewandert sind, dann bricht einer Weissagung zufolge die Ewigkeit an. 1. 2. 3. Problem: Wie groß ist die Mindestanzahl z(n zum Umschichten von Scheiben n * )von der 1. Stange auf die 3. Stange? Lösung: induktives Verfahren Zugfolge Anzahl z(n) der nötigen Züge 1 2 3 4 5 . n0 n0 1 Ergebnis: Günstiger: B1 Die Türme von Hanoi Lösungsblatt In einem Tempel in Hanoi sind 3 Stangen aufgestellt, auf deren erster 1000 jeweils verschieden große Silberscheiben der Größe nach geordnet liegen. Jeder Pilger muss eine Scheibe auf eine andere Stange setzten, aber so, dass keine Scheibe auf einer kleineren liegt. Wenn durch die Pilger alle Scheiben von Stange 1 nach Stange 3 (der Größe nach geordnet) gewandert sind, dann bricht einer Weissagung zufolge die Ewigkeit an. 1. 2. 3. Problem: Mindestanzahl z(n zum Umschichten von Scheiben n * )von Stange 1 auf Stange 3 Lösung: induktives Verfahren Zugfolge Anzahl z(n) der nötigen Züge 1 z(1) 1 2 z(2) 1 1 1 3 2 z(1) 1 3 Züge 3 z(3) 3 1 3 2 z(2) 1 3 Züge 1 Zug 7 Züge 4 z(4) 7 1 7 2 z(3) 1 7 Züge 1 Zug 5 z(n 0 2 z(n 0 1) 1 . n0 n0 1 z(n 0 1) 2 z(n 0 1 0 Scheiben auf die 2. Stange n 0 1 ). Scheibe auf die 3. Stange 0 Scheiben auf die 3. Stange Ergebnis: Rekursionsgleichung: z(n 0 1) 2 z(n 0 1 Berechne z(1); berechne damit z(2); berechne damit z(3); . Günstiger: Finde eine Gleichung für z(n), in der z(n-1) nicht nötig ist. Beweise deren Gültigkeit durch vollständige Induktion. z(1) 1 21 1 ( 2) 3 2 2 1 z(3) 7 2 3 1 (4) 15 2 4 1 z(5) 31 2 5 1 vermutlich: für alle * gilt: z(n 2 1