Zum Inhalt springen

Wiki-Quellcode von Lösung Türme von Hanoi

Zuletzt geändert von akukin am 2023/11/24 09:36
Zeige letzte Bearbeiter
1 Für die Lösung der Aufgabe beginnt man mit kleinen n und betrachtet dann immer eine Scheibe mehr.
2 Es bietet sich z. B. an, mit {{formula}}N(n){{/formula}} die Anzahl der optimalerweise benötigten Züge für eine Pyramide der Höhe {{formula}}n{{/formula}} zu bezeichnen.
3
4
5 {{formula}}N(1)=1{{/formula}}: triviales Problem
6 {{formula}}N(2)=3{{/formula}}: Die kleine Scheibe wird auf 2 gelegt, die große auf 3 und dann die kleine auf 3.
7 {{formula}}N(3)=7{{/formula}}: 1→3; 1→2; 3→2; 1→3; 2→1; 2→3; 1→3
8 {{formula}}N(4)=15{{/formula}}: 1→2; 1→3; 2→3; 1→2; 3→1; 3→2; 1→2; 1→3; 2→3; 2→1; 3→1; 2→3; 1→2; 1→3; 2→3
9
10
11
12 Nach einigen {{formula}}n{{/formula}} sieht man:
13
14 * Für einen Turm mit {{formula}}n{{/formula}} Etagen wird zunächst analog vorgegangen wie für {{formula}}n-1{{/formula}} Etagen, mit dem Unterschied, dass der Turm abzüglich der untersten Etage auf Stab 2 verschoben wird und nicht auf Stab 3. Hierfür benötigt man so viele Züge wie für den Fall {{formula}}n-1{{/formula}}.
15 * Im Anschluss wird die unterste Scheibe von 1 nach 3 bewegt, was einen weiteren Zug benötigt.
16 * Zuletzt wird der zuvor nach 2 verschobene Turm der Höhe {{formula}}n-1{{/formula}} auf die Scheibe auf Stab 3 verschoben. Hierfür benötigt man abermals so viele Züge wie für den Fall {{formula}}n-1{{/formula}}
17
18 Es gilt also offenbar {{formula}}N(1)=1{{/formula}} und {{formula}}N(n)=2⋅N(n-1)+1{{/formula}}
19 (% style="width: min-content; white-space: nowrap" class="border" %)
20 |1|2|3|4|5|6|7|8|9|10
21 |1|3|7|15|31|63|127|255|511|1023
22
23 Man sieht: {{formula}} N(n) = 2^n – 1 {{/formula}}