Arbeitsblatt: Arbeitsblatt - Türme von Hanoi

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