www.wikidata.de-de.nina.az
Dieser Artikel behandelt das Knobelspiel Fur die gleichnamige Datensicherungsart siehe Datensicherung Die Turme von Hanoi sind ein mathematisches Knobel und Geduldsspiel In der Informatik gilt es als Standardbeispiel fur rekursive Programmierung Inhaltsverzeichnis 1 Spielregeln 2 Geschichte 3 Zugfolgen 3 1 Turme bis vier Scheiben 3 2 Zugfolge fur grossere Turme 4 Rekursiver Algorithmus 5 Iterativer Algorithmus 5 1 Uhrzeigersinn 5 2 Gerade Ungerade Ziffern 6 Optimalitat der Algorithmen 7 Eigenschaften optimaler Zugfolgen 8 Der Spielbaum und das Sierpinski Dreieck 9 Literatur 10 Weblinks 11 EinzelnachweiseSpielregeln Bearbeiten nbsp Startanordnung fur die Turme von HanoiDas Spiel wird von einer Person gespielt Es besteht aus drei gleich grossen Staben auf die mehrere gelochte Scheiben gesteckt werden alle verschieden gross Zu Beginn liegen alle Scheiben auf dem linken Stab der Grosse nach geordnet mit der grossten Scheibe unten und der kleinsten oben siehe Bild Ziel des Spiels ist es den kompletten Scheiben Stapel vom linken Stab auf den rechten Stab zu versetzen Hierbei gelten zwei Regeln Es darf immer nur eine Scheibe gleichzeitig bewegt werden Die bewegte Scheibe darf nicht auf eine kleinere Scheibe gesteckt werden Folglich sind zu jedem Zeitpunkt des Spieles die Scheiben auf jedem Feld der Grosse nach geordnet Geschichte BearbeitenDas Spiel wurde 1883 vom franzosischen Mathematiker Edouard Lucas erfunden deshalb auch manchmal Lucas Turme engl Lucas Tower genannt Lucas brachte das Spiel 1883 auf den Markt als Tour d Hanoi von einem Prof Claus aus Siam von der Universitat Li Sou Stian ein Anagramm fur Lucas und die Universitat Saint Louis 1 2 Er dachte sich dazu die Geschichte aus dass dies eine vereinfachte Version des Turms von Brahma sei Indische Monche im grossen Tempel zu Benares im Mittelpunkt der Welt mussten einen Turm aus 64 goldenen Scheiben versetzen Bevor ihnen das gelungen sei ware aber der Tempel zu Staub zerfallen und mit einem Donnerschlag das Ende der Welt gekommen 3 1 Das ursprungliche Spiel hatte acht Scheiben Das Ratsel fand bald darauf Eingang in Sammlungen mathematischer Ratsel 4 5 Zugfolgen BearbeitenDas Spiel kann mit einer beliebigen Anzahl von Scheiben gespielt werden Zur Erlauterung wird die linke Stange Start mit A displaystyle A nbsp die mittlere mit B displaystyle B nbsp und die rechte Stange Ziel mit C displaystyle C nbsp bezeichnet Die Scheiben werden von der kleinsten bis zur grossten mit S 1 displaystyle S 1 nbsp S 2 displaystyle S 2 nbsp usw bis S n displaystyle S n nbsp bezeichnet wobei n displaystyle n nbsp die Anzahl der Scheiben ist Die hier verwendete Schreibweise fur Zuge ist Die Angabe S 1 A C displaystyle S 1 Rightarrow A to C nbsp bedeutet dass die Scheibe S 1 displaystyle S 1 nbsp vom Stab A displaystyle A nbsp auf den Stab C displaystyle C nbsp verschoben wird Turme bis vier Scheiben Bearbeiten Der triviale Fall mit n 1 also mit einer Scheibe ist in einem Zug losbar Es genugt der Zug S 1 A C displaystyle S 1 Rightarrow A to C nbsp Der Fall n 2 displaystyle n 2 nbsp also mit zwei Scheiben erfordert drei Zuge Zuerst wird die obere kleine Scheibe auf den Stab B displaystyle B nbsp gelegt anschliessend die untere grossere Scheibe auf den Stab C displaystyle C nbsp und abschliessend die kleine Scheibe vom Stab B displaystyle B nbsp auf den Stab C displaystyle C nbsp gelegt Die Aufgabe wird also durch die folgenden drei Zuge gelost S 1 A B displaystyle S 1 Rightarrow A to B nbsp S 2 A C displaystyle S 2 Rightarrow A to C nbsp S 1 B C displaystyle S 1 Rightarrow B to C nbsp nbsp Losung des Problems mit drei ScheibenFur den Fall n 3 displaystyle n 3 nbsp also mit drei Scheiben kann folgende Voruberlegung angestellt werden Um die grosste also unten liegende Scheibe nach C displaystyle C nbsp bewegen zu konnen muss der Zweierstapel 2 Stapel Stapel aus den Scheiben S 1 displaystyle S 1 nbsp und S 2 displaystyle S 2 nbsp daruber auf B displaystyle B nbsp bewegt werden Um diesen 2 Stapel nach B displaystyle B nbsp zu bewegen muss der 1 Stapel daruber also die oberste kleinste Scheibe S 1 displaystyle S 1 nbsp zunachst nach C displaystyle C nbsp bewegt werden Anschliessend kann die mittlere Scheibe nach B displaystyle B nbsp und die kleinste Scheibe von C displaystyle C nbsp nach B displaystyle B nbsp bewegt werden Es ergibt sich also die Zugfolge S 1 A C S 2 A B S 1 C B displaystyle S 1 Rightarrow A to C quad vert quad S 2 Rightarrow A to B quad vert quad S 1 Rightarrow C to B nbsp Diese Zugfolge entspricht also dem Fall mit zwei Scheiben wobei jedoch die Stabe B displaystyle B nbsp und C displaystyle C nbsp vertauschte Rollen spielen Jetzt kann die dritte unterste Scheibe nach rechts verschoben werden Dies entspricht dem Zug S 3 A C displaystyle S 3 Rightarrow A to C nbsp Zum Schluss muss der 2 Stapel von der Mitte nach rechts verschoben werden um die Aufgabe zu losen Dies funktioniert genauso wie die Zugfolge am Anfang nur dass Stab A displaystyle A nbsp mit Stab B displaystyle B nbsp Stab B displaystyle B nbsp mit Stab C displaystyle C nbsp und Stab C displaystyle C nbsp mit Stab A displaystyle A nbsp vertauschte Rollen spielen Es bleibt also die Zugfolge S 1 B A S 2 B C S 1 A C displaystyle S 1 Rightarrow B to A quad vert quad S 2 Rightarrow B to C quad vert quad S 1 Rightarrow A to C nbsp auszufuhren Insgesamt werden also sieben Spielzuge benotigt nbsp Losung des Problems mit vier ScheibenAllgemein kann fur jede zusatzliche Scheibe zuerst der Stapel mit einer Scheibe auf B displaystyle B nbsp dann die unterste Scheibe nach C displaystyle C nbsp und anschliessend der Stapel von B displaystyle B nbsp nach C displaystyle C nbsp weiterbewegt werden Fur den Fall n 4 displaystyle n 4 nbsp also mit vier Scheiben ergibt sich also die Zugfolge mit den 15 Losungsschritten S 1 A B S 2 A C S 1 B C displaystyle S 1 Rightarrow A to B quad vert quad S 2 Rightarrow A to C quad vert quad S 1 Rightarrow B to C nbsp S 3 A B displaystyle S 3 Rightarrow A to B nbsp dd S 1 C A S 2 C B S 1 A B displaystyle S 1 Rightarrow C to A quad vert quad S 2 Rightarrow C to B quad vert quad S 1 Rightarrow A to B nbsp S 4 A C displaystyle S 4 Rightarrow A to C nbsp dd dd S 1 B C S 2 B A S 1 C A displaystyle S 1 Rightarrow B to C quad vert quad S 2 Rightarrow B to A quad vert quad S 1 Rightarrow C to A nbsp S 3 B C displaystyle S 3 Rightarrow B to C nbsp dd S 1 A B S 2 A C S 1 B C displaystyle S 1 Rightarrow A to B quad vert quad S 2 Rightarrow A to C quad vert quad S 1 Rightarrow B to C nbsp Zugfolge fur grossere Turme Bearbeiten AnzahlScheiben Anzahl Zuge5 3110 102320 1 048 57530 1 073 741 82340 1 099 511 627 77550 1 125 899 906 842 62364 18 446 744 073 709 551 615Die Zahl der bei optimaler Losung notigen Zuge wachst exponentiell mit der Scheibenzahl Fur n displaystyle n nbsp Scheiben werden 2 n 1 displaystyle 2 n 1 nbsp Zuge benotigt 3 Die nebenstehende Tabelle zeigt die Anzahl der Zuge bei verschiedenen Turmgrossen Rekursiver Algorithmus BearbeitenDie Geschichte um die Monche und die Zugfolgen fur kleine Scheibenanzahlen fuhren mit einem rekursiven Algorithmus zur Losung des Spiels Da sich ein Computerprogramm zur Losung des Spiels mit wenigen Zeilen schreiben lasst ist Turme von Hanoi ein klassisches Beispiel fur diese Art der Problemlosung 6 Der Algorithmus besteht im Wesentlichen aus einer Funktion bewege die vier Parameter besitzt Mit i ist die Anzahl der zu verschiebenden Scheiben bezeichnet mit a der Stab von dem verschoben werden soll mit b der Stab der als Zwischenziel dient und mit c der Stab auf den die Scheiben verschoben werden sollen Zur Losung des eigentlichen Problems wird bewege mit i n a A b B und c C aufgerufen Die Funktion bewege lost ein Teilproblem dadurch dass es dieses in drei einfachere Probleme aufteilt sofern der zu verschiebende Turm mindestens die Hohe 1 besitzt Andernfalls ist die Funktion bewege untatig Die drei Teilprobleme werden sequentiell ausgefuhrt Zunachst wird der um eine Scheibe kleinere Turm von a auf das Zwischenziel b verschoben indem sich die Funktion bewege selbst mit den entsprechenden Parametern aufruft Die Stabe b und c tauschen dabei ihre Rollen Anschliessend wird die einzig verbliebene Scheibe von a nach c verschoben Zum Abschluss wird der zuvor auf b verschobene Turm auf seinen Bestimmungsort c verschoben wobei hier a und b die Rollen tauschen function bewege Zahl i Stab a Stab b Stab c falls i gt 0 bewege i 1 a c b verschiebe oberste Scheibe von a nach c bewege i 1 b a c So verhalt sich die Funktion bei drei Scheiben die Stabe wurden durchnummeriert links a mitte b rechts c der Bewegungsablauf ist exakt wie im Bild oben bewege 3 a b c bewege 2 a c b bewege 1 a b c bewege 0 a c b verschiebe oberste Scheibe von a nach c bewege 0 b a c verschiebe oberste Scheibe von a nach b bewege 1 c a b bewege 0 c b a verschiebe oberste Scheibe von c nach b bewege 0 a c b verschiebe oberste Scheibe von a nach c bewege 2 b a c bewege 1 b c a bewege 0 b a c verschiebe oberste Scheibe von b nach a bewege 0 c b a verschiebe oberste Scheibe von b nach c bewege 1 a b c bewege 0 a c b verschiebe oberste Scheibe von a nach c bewege 0 b a c Die Korrektheit des Algorithmus ist zwar intuitiv glaubhaft formal aber nicht trivial beweisbar Im Wesentlichen mussen zwei Dinge gezeigt werden Zum einen mussen die Teillosungen korrekt arbeiten Zum anderen ist zu zeigen dass diese uberhaupt durchgefuhrt werden konnen Schliesslich darf keine der Scheiben die bei Teillosungen nicht betrachtet werden den Transport verhindern Dass dem tatsachlich so ist folgt aus der Eigenschaft dass die Funktion bewege bei jeder Teillosung immer nur die kleinsten i Scheiben bewegt Sowohl diese Eigenschaft als auch die Korrektheit der Teillosungen lasst sich durch vollstandige Induktion zeigen Iterativer Algorithmus BearbeitenUhrzeigersinn Bearbeiten Peter Buneman und Leon Levy haben 1980 einen iterativen Algorithmus beschrieben der die gleiche Zugfolge generiert 7 Bei diesem ist die Korrektheit zwar nicht sofort erkennbar die Handlungsweise aber ohne das Konzept der Rekursion verstandlich Es sei vorausgesetzt dass die Stabe A B und C bei gerader Scheibenanzahl im Uhrzeigersinn auf einem Kreis angeordnet sind sonst entgegen dem Uhrzeigersinn Die Scheiben befinden sich zum Anfang alle auf Stab A am Ende auf Stab C Solange sich auf wenigstens einem der beiden Stabe A und B Scheiben befinden wird erst die kleinste Scheibe S 1 displaystyle S 1 nbsp im Uhrzeigersinn und anschliessend sofern dies moglich ist eine von S 1 displaystyle S 1 nbsp verschiedene Scheibe verschoben Als Pseudocode notiert ergibt sich also folgender Algorithmus solange Stab A oder B enthalten Scheiben Verschiebe S 1 displaystyle S 1 nbsp im Uhrzeigersinn um einen Platz falls eine von S 1 displaystyle S 1 nbsp verschiedene Scheibe ist verschiebbar Verschiebe eine von S 1 displaystyle S 1 nbsp verschiedene Scheibe So verhalt sich die Funktion bei drei Scheiben vergleiche Bild oben Um mit dem Bild zu synchronisieren wird S 1 displaystyle S 1 nbsp um zwei statt um ein Feld im Uhrzeigersinn verschoben Anfangsposition A 3 2 1 B 0 0 0 C 0 0 0 Erster Durchlauf A 3 2 0 B 0 0 0 C 1 0 0 S 1 displaystyle S 1 nbsp von A nach C A 3 0 0 B 2 0 0 C 1 0 0 S 2 displaystyle S 2 nbsp von A nach B Zweiter Durchlauf A 3 0 0 B 2 1 0 C 0 0 0 S 1 displaystyle S 1 nbsp von C nach B A 0 0 0 B 2 1 0 C 3 0 0 S 3 displaystyle S 3 nbsp von A nach C Dritter Durchlauf A 1 0 0 B 2 0 0 C 3 0 0 S 1 displaystyle S 1 nbsp von B nach A A 1 0 0 B 0 0 0 C 3 2 0 S 2 displaystyle S 2 nbsp von B nach C Letzter Durchlauf A 0 0 0 B 0 0 0 C 3 2 1 S 1 displaystyle S 1 nbsp von A nach C Endposition A 0 0 0 B 0 0 0 C 3 2 1 Der zweite Zug innerhalb der Schleife ist bis auf den letzten Schleifendurchgang immer moglich und auch eindeutig Um dies einzusehen sei der Stab auf dem S 1 displaystyle S 1 nbsp liegt mit a und von den beiden verbliebenen Staben denjenigen mit der kleineren obenaufliegenden Scheibe mit b der anderen mit c bezeichnet Offensichtlich kann die oberste Scheibe von b auf c verschoben werden Dies ist zugleich die einzige Moglichkeit eine Scheibe verschieden von S 1 displaystyle S 1 nbsp zu verschieben Denn weder die oberste Scheibe von b noch von c kann auf a verschoben werden da dort mit S 1 displaystyle S 1 nbsp die kleinste Scheibe liegt Auch ein Verschieben der obersten Scheibe von c nach b ist nach Wahl der Bezeichnungen der Stabe nicht moglich Der Fall dass keine andere Scheibe als S 1 displaystyle S 1 nbsp verschiebbar ist tritt nur dann ein wenn alle Scheiben wieder auf einem Stab liegen das Ziel also bereits erreicht ist Gerade Ungerade Ziffern Bearbeiten Ein weiterer Losungsweg beruht auf folgenden beiden Merkmalen des Anfangsturms Zum einen auf der geraden bzw ungeraden Anzahl der Scheiben und zum Zweiten auf der Nummerierung der Scheiben beim Abzahlen von unten nach oben 8 Es sind dann folgende Regeln zu beachten beim ersten Zug und bei ungerader Scheibenanzahl geht die kleinste Scheibe von A nach C bzw im geraden Fall von A nach B jeder zweite Zug erfolgt stets mit der kleinsten Scheibe falls ihre Endziffer gerade bzw ungerade ist geht der Zug auf eine Scheibe mit ungerader bzw gerader Nummerierung falls dies nicht moglich ist geht der Zug auf ein Leerfeld der Zug dazwischen betrifft die beiden oben liegenden nicht kleinsten Scheiben Er ist eindeutig die kleinere der beiden Scheiben geht auf die grossere Scheibe falls das nicht moglich ist auf ein Leerfeld Optimalitat der Algorithmen BearbeitenEs gibt fur jede Scheibenanzahl nur einen optimalen Losungsweg fur das Problem also nur eine kurzeste Zugfolge Diese wird von beiden Algorithmen durchlaufen In diesem Sinne sind die Algorithmen also optimal Fur den rekursiven Algorithmus lasst sich dies leicht einsehen 3 Bevor die unterste Scheibe eines Teil Turmes verschoben werden kann mussen alle daruberliegenden Scheiben auf das Zwischenziel verschoben werden dort mussen sie naturlich in geordneter Reihenfolge landen Erst dann kann die unterste Scheibe auf den Zielstab verschoben werden Denn nur dann liegt diese frei und nur wenn alle ursprunglich uber dieser Scheibe liegenden Scheiben auf dem Zwischenziel liegen kann keine dieser kleineren Scheiben das Verschieben der untersten Scheibe auf das Ziel blockieren Fur die Optimalitat des iterativen Algorithmus genugt es zu zeigen dass die durch den rekursiven Algorithmus bestimmte Zugfolge den Bedingungen des iterativen Algorithmus genugt Dies ergibt sich aus der folgenden Uberlegung Das Versetzen eines nichtleeren Teilturmes beginnt und endet jeweils mit einer Bewegung der kleinsten Scheibe In der rekursiven Funktion wird also unmittelbar vor und unmittelbar nach dem Verschieben der i ten Scheibe die kleinste Scheibe bewegt Da jede Bewegung einer Scheibe auf dieser Anweisung beruht und die kleinste Scheibe aufgrund der Optimalitat niemals zweimal direkt hintereinander bewegt wird wird sie in jedem zweiten Zug versetzt Die zyklische Richtung in der die beiden Teilturme in einem Aufruf der Funktion versetzt werden ist fur die beiden rekursiven Aufrufe a c b und b a c der Funktion dieselbe namlich der Richtung a b c entgegengesetzt Infolgedessen ist die zyklische Richtung fur alle Aufrufe mit i 1 dieselbe das heisst die kleinste Scheibe wird immer in derselben Richtung bewegt Somit erzeugt der rekursive Algorithmus dieselbe Zugfolge wie der iterative Der iterative Algorithmus fuhrt auch dann zur Losung wenn die Stabe falsch herum auf dem Kreis angeordnet werden Im Falle einer falschen Anordnung werden die Scheiben aber zuerst auf Stab B verschoben Da in dieser Situation die Abbruchbedingung nicht erfullt ist wird anschliessend weiter auf C verschoben Der Algorithmus benotigt in diesem Fall damit doppelt so viele Zuge ist dann also nicht optimal Fur eine optimale Zugfolge sind folgende Bedingungen offensichtlich notwendig Eine bestimmte Spielsituation darf nicht erneut erreicht werden Die zuletzt bewegte Scheibe darf nicht gleich noch einmal bewegt werden Sie sind aber nicht hinreichend dies zeigt das Beispiel fur drei Scheiben mit insgesamt 11 Zugen S 1 A B displaystyle S 1 Rightarrow A to B nbsp S 2 A C displaystyle S 2 Rightarrow A to C nbsp S 1 B C displaystyle S 1 Rightarrow B to C nbsp S 3 A B displaystyle S 3 Rightarrow A to B nbsp S 1 C B displaystyle S 1 Rightarrow C to B nbsp S 2 C A displaystyle S 2 Rightarrow C to A nbsp S 1 B A displaystyle S 1 Rightarrow B to A nbsp S 3 B C displaystyle S 3 Rightarrow B to C nbsp S 1 A B displaystyle S 1 Rightarrow A to B nbsp S 2 A C displaystyle S 2 Rightarrow A to C nbsp S 1 B C displaystyle S 1 Rightarrow B to C nbsp Die oben angegebenen Zugfolgen fur kleine Scheibenanzahlen sind optimal entsprechen also genau den Zugfolgen die von den Algorithmen erzeugt werden Eigenschaften optimaler Zugfolgen BearbeitenFur optimale Zugfolgen lassen sich eine ganze Reihe von Eigenschaften herleiten Wegen der Optimalitat des rekursiven Algorithmus ist dies besonders leicht anhand seiner Funktionsweise moglich Sei n displaystyle n nbsp wieder die Anzahl der Scheiben Die Anzahl der Zuge der optimalen Losung ist dann 2 n 1 displaystyle 2 n 1 nbsp Dies lasst sich leicht induktiv zeigen Fur eine einzelne Scheibe ist dies sicher richtig denn diese muss nur von A displaystyle A nbsp nach C displaystyle C nbsp verschoben werden Die optimale Zugfolge besteht also wie behauptet aus einem Zug Fur grossere Scheibenanzahlen wird die Anzahl der Zuge durch Summation der Zuge fur die Teilprobleme nachgewiesen Die Zuganzahl entspricht also dem Doppelten der minimalen Zuganzahl fur den um eine Scheibe kleineren Turm da dieser zweimal bewegt werden muss plus den einen Zug um die grosste Scheibe zu bewegen Wie behauptet folgt 2 n 1 1 1 2 n 1 1 2 n 1 displaystyle left 2 n 1 1 right 1 left 2 n 1 1 right 2 n 1 nbsp Es lasst sich leicht bestimmen wie oft und bei welchen Zugen eine Scheibe bei einer optimalen Zugfolge bewegt wird Allgemein gilt dass die Scheibe S k displaystyle S k nbsp genau 2 n k displaystyle 2 n k nbsp mal bewegt wird Dabei wird sie beim Zug 2 k 1 displaystyle 2 k 1 nbsp das erste Mal und dann nach jeweils 2 k displaystyle 2 k nbsp Zugen erneut bewegt Die kleinste Scheibe S 1 displaystyle S 1 nbsp wird bei jedem zweiten Zug bewegt beginnend mit dem ersten Zug Die zweitkleinste Scheibe S 2 displaystyle S 2 nbsp wird bei jedem vierten Zug bewegt beginnend mit dem zweiten Zug Die grosste Scheibe S n displaystyle S n nbsp wird einmal bewegt und zwar beim mittleren also dem 2 n 1 displaystyle 2 n 1 nbsp ten Zug Die zweitgrosste Scheibe S n 1 displaystyle S n 1 nbsp wird zweimal bewegt und zwar nach dem ersten und dritten Viertel der um 1 erhohten Zugfolge also bei den Zugen 2 n 2 displaystyle 2 n 2 nbsp und 3 2 n 2 displaystyle 3 cdot 2 n 2 nbsp Auf diese Weise ist es moglich an jedem Punkt der Zugfolge zu bestimmen welche Scheibe als Nachstes bewegt werden muss Der Spielbaum und das Sierpinski Dreieck Bearbeiten nbsp Spielbaum zum Turm der Hohe 3 nbsp Spielbaum zum Turm der Hohe 7 der sich dem Sierpinski Dreieck annahert Stellt man alle erlaubten Spielzuge in einem Graphen dar dann erhalt man den Spielbaum Dabei wird jede Spielstellung durch einen Knoten dargestellt und jeder Zug durch eine Kante Die Beschriftung der Knoten erfolgt anhand der Position der Scheiben beginnend mit der Position der grossten Scheibe S n displaystyle S n nbsp Die nebenstehende Grafik zeigt den Spielbaum eines Turms der Hohe drei Die Ecken des Dreiecks mit den Stellungen AAA und CCC entsprechen der Start bzw Endposition die Ecke BBB entspricht der Stellung mit allen Scheiben auf dem mittleren Stab B Die Kantenfarbe entspricht der der bewegten Scheibe in der Animation oben Rot fur die kleinste Gelb fur die mittlere und Blau fur die grosste Scheibe S 3 displaystyle S 3 nbsp Der erste Zug der optimalen Losung oben bezeichnet mit S 1 displaystyle S 1 nbsp AC entspricht also der roten Kante zwischen AAA und AAC und bewegt die kleine rote Scheibe S 1 displaystyle S 1 nbsp von A nach C Danach wird die gelbe Scheibe S 2 displaystyle S 2 nbsp von A nach B gezogen und die Stellung dadurch von AAC zu ABC verandert Die Anzahl der Knoten im Graph also die Anzahl moglicher Spielstellungen ist 3 n displaystyle 3 n nbsp denn jede Scheibe kann sich auf jedem Stab befinden und bei mehreren Scheiben auf demselben Stab ist deren Anordnung aufgrund ihrer Grosse eindeutig gegeben Von jeder Spielstellung aus lasst sich die kleinste Scheibe auf zwei andere Stabe bewegen Sind nicht alle Scheiben auf dem gleichen Stab darf man zudem noch die nachstkleinere obenliegende Scheibe bewegen Von allen Stellungen aus hat man also drei Zugmoglichkeiten ausser an den Ausgangspositionen AAA BBB und CCC in denen nur zwei Zuge moglich sind Die Anzahl der Kanten k n displaystyle k n nbsp im Graph ist also k n 3 2 3 n 3 3 2 3 2 3 n 1 displaystyle k n frac 3 cdot 2 3 n 3 cdot 3 2 frac 3 2 3 n 1 nbsp Die Division durch Zwei ruhrt daher dass jede Kante zu zwei Knoten gehort Die Gesamtheit aller Zuge ist 2 k n displaystyle 2k n nbsp da man Hin und Ruckzug unterscheiden muss Durch den rekursiven Aufbau des Spielgraphen lasst sich leicht nachweisen dass der Durchmesser des Graphen gleich 2 n 1 displaystyle 2 n 1 nbsp ist Das heisst von einer gegebenen Stellung aus ist jede andere Stellung mit hochstens 2 n 1 displaystyle 2 n 1 nbsp Zugen erreichbar und es gibt Stellungen deren kurzeste Verbindung 2 n 1 displaystyle 2 n 1 nbsp Zuge umfasst wie zum Beispiel die optimale Zugfolge von der Start zur Endstellung Erhoht man einen Turm um eine Scheibe dann wachsen sowohl die Anzahl der Knoten als auch die Anzahl der Kanten seines Spielbaumes in der Grossenordnung von 3 wahrend der geometrische Durchmesser in der gewahlten Veranschaulichung um den Faktor 2 wachst Normiert man die Spielbaume auf den Durchmesser Eins dann strebt die Folge der so normierten Graphen gegen das Sierpinski Dreieck Die Grenzstruktur ist also ein selbstahnliches Fraktal mit der Hausdorff Dimension H log 3 log 2 1 584 96 displaystyle H log 3 log 2 1 58496 nbsp Literatur BearbeitenAndreas M Hinz Sandi Klavzar Ciril Petr The Tower of Hanoi Myth and Math 2 Auflage Birkhauser 2018 Martin Gardner Das Ikosaeder Spiel und der Turm von Hanoi in Martin Gardner Mathematische Ratsel und Probleme Vieweg 1964 englisches Original The Icosian Game and the Tower of Hanoi in Martin Gardner The Scientific American Book of Puzzles and Diversions Simon and Schuster 1959 Neuauflage Hexaflexygons Probability Paradoxes and the Tower of Hanoi Cambridge UP 2008 mit Literaturverzeichnis Weblinks BearbeitenEinfuhrung in die wissenschaftliche Programmierung Seite 3 Stack Beispiel Turme von Hanoi Vorlesung an der Technischen Universitat Munchen Lernfunk de Demonstration des Algorithmus Ausschnitt aus der Vorlesung Algorithmen der Universitat Osnabruck Towers of Hanoi bei Wolfram Research Zusammenhang zu verschiedenen mathematischen Fachgebieten Turme von Hanoi ein mit Maple realisierter Algorithmus Turme von Hanoi eine graphische Realisierung des Algorithmus in Html5 Canvas Explizite LosungEinzelnachweise Bearbeiten a b Martin Gardner Das Ikosaeder Spiel und der Turm von Hanoi in Martin Gardner Mathematische Ratsel und Probleme Vieweg 1964 Andreas M Hinz Sandi Klavzar Ciril Petr The Tower of Hanoi Myth and Math 2 Auflage Birkhauser 2018 a b c Florian Freistetter Die Turme der Apokalypse In spektrum de Artikel vom 14 November 2021 aufgerufen am 11 Mai 2022 W W Rouse Ball H S M Coxeter Mathematical recreations and essays 11 Auflage Macmillan 1947 S 313 315 das Problem findet sich auch schon in den alteren Ausgaben von Ball z B in der Ausgabe von 1905 Henry Ernest Dudeney The Canterbury Puzzles New York Dutton 1908 S 1 2 als The Reve s Puzzle Ronald L Graham Donald E Knuth Oren Patashnik Concrete Mathematics Kap 1 1 S 1ff archive org Peter Buneman Leon Levy The towers of Hanoi problem In Information Processing Letters Band 10 Nr 4 5 1980 S 243 244 doi 10 1016 0020 0190 80 90150 7 englisch Herbert Mayer Don Perkins Towers of Hanoi revisited a nonrecursive surprise In ACM SIGPLAN Notices Band 19 Nr 2 1984 S 80 84 doi 10 1145 948566 948573 nbsp Dieser Artikel wurde am 30 September 2005 in dieser Version in die Liste der lesenswerten Artikel aufgenommen Abgerufen von https de wikipedia org w index php title Turme von Hanoi amp oldid 237618200