Hier entstehen die Türme von Hanoi in Millisekunden!

Gewidmet Harry Paul zum 91. Geburtstag

English version

In der Informatik gelten die Türme von Hanoi (Wiki) als ein Paradebeispiel für ein Problem, das sich nur rekursiv (oder iterativ) lösen lässt. Die Zeit für die Berechnung einer bestimmten Position n wächst also exponentiell mit O(2n). In diesem Artikel wird eine explizite Lösung vorgestellt, mit der man jede Position n mit der gleichen Rechenzeit O(1) berechnen kann. Diese explizite Lösung wird in allen Animationen verwendet.

 

Für 10 Scheiben sieht das Umsortieren so aus (oben wird die Zahl der Züge angezeigt, mit 1 Sekunde Pause für Mersenne-Zahlen):

 

Angenommen die Mönche haben vor genau 91 Jahren damit begonnen, eine Scheibe pro Sekunde zu bewegen. Dann sehen die Positionen der Scheiben zu den Zeiten 91a-45s bis 91a+45s so aus (die oberste Scheibe (1) wird in jedem zweiten Zug bewegt, usw.):

Oder mit Scheiben: Die Startposition 0 (vor genau 91a) wird 5 Sekunden angezeigt, dann geht es im Sekundentakt weiter wie oben, also mit 91a-45s:

Herzlichen Glückwunsch!

 

© 11.02.2022, Dr. Michael Komma (VGWORT)

Methode: Explizite Berechnung der Position der Scheiben zu vorgegebener Anzahl der Züge. Rechenzeit pro Position 50ms. Zum Vergleich: Die Zeit für rekursive Berechnung der Position 91*365*24*3600 = 2869776000 beträgt 6.7h.

Details: Die Standardprozedur zur rekursiven Berechnung der Positionen der Scheiben sieht in Maple so aus: 

> zug := proc (k, x, y, z) if `<`(0, k) then zug(`+`(k, `-`(1)), x, z, y); print(k, x, y, z); zug(`+`(k, `-`(1)), y, x, z) end if end proc;

Typesetting:-mprintslash([zug := proc (k, x, y, z) if `<`(0, k) then zug(`+`(k, `-`(1)), x, z, y); print(k, x, y, z); zug(`+`(k, `-`(1)), y, x, z) end if end proc], [proc (k, x, y, z) if `<`(0, k) the... (1)

Mit vier Scheiben und den Positionen a,b und c erhält man z.B. 

> zug(4, a, b, c); align=

 

Dabei ist 1..4 die Nummer der Scheibe (1 für die kleinste Scheibe), die von der ersten (Start) auf die letzte (Ziel) Position bewegt wird (die mittlere Position od. Parkposition ist nur zur Vollständigkeit aufgeführt). "1,a,c,b" bedeutet also: bewege Scheibe 1 von a nach b, und "2,a,b,c": bewege Scheibe 2 von a nach c. 

Man sieht an diesem Beispiel:
1. Scheiben mit ungerader Nummer bewegen sich zyklisch mit (a,b,c) und Scheiben mit gerader Nummer zyklisch mit (a,c,b).
 
2. Scheibe 1 wird in jedem zweiten Zug, Scheibe 2 wird in jedem vierten Zug, und Scheibe j wird in jedem 2j-ten Zug bewegt.
3. Anmerkung: Falls als Zielstapel für den vollständigen Turm b oder c vorgegeben wird, kann das je nach Anzahl der Scheiben (gerade oder ungerade) leicht berücksichtigt werden.

Nachdem die Bewegung der Scheiben zyklisch ist, kann es sich nicht um ein Problem handeln, das nur rekursiv (oder iterativ) zu lösen ist. Es muss also eine explizite Lösung geben. Um diese explizite Lösung zu finden, muss man nur die Frage beantworten wie oft die Scheibe j bewegt wurde, wenn insgesamt n Züge gemacht wurden. 

Mit einem einfachen Abzählverfahren findet man 

> kj := proc (n, j) options operator, arrow; floor(`+`(`/`(`*`(n), `*`(`^`(2, j))), `/`(1, 2))) end proc;
Typesetting:-mprintslash([kj := proc (n, j) options operator, arrow; floor(`+`(`/`(`*`(n), `*`(`^`(2, j))), `/`(1, 2))) end proc], [proc (n, j) options operator, arrow; floor(`+`(`/`(`*`(n), `*`(`^`(2... (3)
 

Veranschaulichung für fünf Scheiben 

> plot([seq(kj(n, j), j = 1 .. 5)], n = 0 .. 31);
 

Plot_2d
 

Womit die Rechenzeit von O(2n) auf O(1) reduziert ist. 

 

Bekanntermaßen lässt sich übrigens die Nummer der Scheibe, die bewegt werden muss, so berechnen (Rekursionsrelation): 

> L[1] := NULL; -1; for k to 5 do L[`+`(k, 1)] := L[k], k, L[k]; print(L[`+`(k, 1)]) end do; -1

oder so (explizit): 

> seq(`+`(padic[ordp](n, 2), 1), n = 1 .. 31);
 
1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1

Nur weiß man dann nicht, wo sich die Scheibe befindet. Für die Rekursionsrelation findet man auch Darstellungen der Art (Abszisse: Nummer des Zuges, Ordinate: Nummer der Scheibe, die bewegt wird):

oder als Baum

Insbesondere die Baumdarstellung wird mit ihren Ästen von oben nach unten gelesen (Informatikbäume und Stammbäume haben ihre Wurzel oben :), also nicht in der Reihenfolge der Züge.
Die explizite Lösung lässt sich leichter finden, wenn man von links nach rechts liest (Zweierlogarithmus - um 1 nach oben verschoben - als "Einhüllende" in schwarz):

 

Download Worksheet (Minimalversion).

Siehe auch:  Physikalische Plaudereien | Weihnachten 2020 | Venuszyklus | Analemma | schielender Mond | Uhrenparadoxon | Schwebungen | Quantensprung

Noch mehr Links: Die mathematische Beschreibung dynamischer Systeme verwendet Systeme von Differentialgleichungen, die eng verwandt sind mit der Beschreibung atomarer Übergänge (Systeme mit zwei Zuständen) , siehe z.B. Spontane Emission | Kaskade | Photogalerie | Photonenemission | Weisskopf-Wigner

Moderne Physik mit Maple

HOME | Fächer | Physik | Elektrizität | Optik | Atomphysik | Quantenphysik | Top