Türme von Hanoi

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Turm von Hanoi)
Datei:Tower of Hanoi.jpeg
Die Türme von Hanoi

Die Türme von Hanoi sind ein mathematisches Knobel- und Geduldsspiel. Es gilt als Standardbeispiel für das Teile-und-herrsche-Verfahren in der Programmierung.

Aufbau

Das Spiel besteht aus drei gleich großen Stäben , und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C} , auf die mehrere gelochte Scheiben gelegt werden, alle verschieden groß. Zu Beginn liegen alle Scheiben auf Stab Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} , der Größe nach geordnet, mit der größten Scheibe unten und der kleinsten oben. Ziel des Spiels ist es, den kompletten Scheiben-Stapel von nach zu versetzen.

Bei jedem Zug darf die oberste Scheibe eines beliebigen Stabes unter der Voraussetzung, dass sich dort nicht schon eine kleinere Scheibe befindet, auf einen der beiden anderen Stäbe gelegt werden. Folglich sind zu jedem Zeitpunkt des Spieles die Scheiben auf jedem Feld der Größe nach geordnet.

Geschichte

Das Spiel wurde 1883 vom französischen Mathematiker Édouard Lucas erfunden – deshalb auch manchmal Lucas-Türme (engl. Lucas Tower) genannt. Lucas brachte das Spiel 1883 auf den Markt als Tour d'Hanoi von einem Prof. Claus aus Siam (von der Universität Li-Sou-Stian), ein Anagramm für Lucas und die Universität Saint-Louis.[1][2] Er dachte sich dazu die Geschichte aus, dass dies eine vereinfachte Version des Turms von Brahma sei. Indische Mönche im großen Tempel zu Benares, im Mittelpunkt der Welt, müssten einen Turm aus 64 goldenen Scheiben versetzen. Bevor ihnen das gelungen sei, wäre aber der Tempel zu Staub zerfallen und mit einem Donnerschlag das Ende der Welt gekommen.[3][1] Das ursprüngliche Spiel hatte acht Scheiben. Das Rätsel fand bald darauf Eingang in Sammlungen mathematischer Rätsel.[4][5]

Zugfolgen

Das Spiel kann mit einer beliebigen Anzahl von Scheiben gespielt werden. Zur Erläuterung werden die Scheiben von der kleinsten bis zur größten mit bis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_n} bezeichnet, wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} die Anzahl der Scheiben ist. Die hier verwendete Schreibweise für Züge ist: Die Angabe bedeutet, dass die Scheibe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_1} vom Stab Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} auf den Stab Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C} verschoben wird.

Türme bis vier Scheiben

Der triviale Fall mit n = 1, also mit einer Scheibe, ist in einem Zug lösbar. Es genügt der Zug:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_1 \Rightarrow A \to C}

Der Fall Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n = 2} , also mit zwei Scheiben, ist erfordert drei Züge: Zuerst wird die obere kleine Scheibe auf den Stab gelegt, anschließend die untere größere Scheibe auf den Stab Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C} und abschließend die kleine Scheibe vom Stab auf den Stab gelegt. Die Aufgabe wird also durch die folgenden drei Züge gelöst:

| | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_1 \Rightarrow B \to C}
Datei:Tower of Hanoi.gif
Lösung des Problems mit drei Scheiben

Für den Fall Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n = 3} , also mit drei Scheiben, kann folgende Vorüberlegung angestellt werden: Um die größte, also unten liegende, Scheibe nach bewegen zu können, muss der Zweierstapel ("2-Stapel", Stapel aus den Scheiben und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_2} ) darüber auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle B} bewegt werden. Um diesen 2-Stapel nach Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle B} zu bewegen, muss der 1-Stapel darüber, also die oberste, kleinste Scheibe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_1} , zunächst nach Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C} bewegt werden. Anschließend kann die mittlere Scheibe nach Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle B} und die kleinste Scheibe von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C} nach Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle B} bewegt werden. Es ergibt sich also die Zugfolge:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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}

Diese Zugfolge entspricht also dem Fall mit zwei Scheiben, wobei jedoch die Stäbe und vertauschte Rollen spielen.

Jetzt kann die dritte, unterste Scheibe nach rechts verschoben werden. Dies entspricht dem Zug:

Zum Schluss muss der 2-Stapel von der Mitte nach rechts verschoben werden, um die Aufgabe zu lösen. Dies funktioniert genauso wie die Zugfolge am Anfang, nur dass Stab Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} mit Stab Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle B} , Stab mit Stab Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C} und Stab mit Stab Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} vertauschte Rollen spielen. Es bleibt also die Zugfolge:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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}

auszuführen. Insgesamt werden also sieben Spielzüge benötigt.

Datei:Tower of Hanoi 4.gif
Lösung des Problems mit vier Scheiben

Allgemein kann für jede zusätzliche Scheibe zuerst der Stapel mit einer Scheibe auf , dann die unterste Scheibe nach Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C} und anschließend der Stapel von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle B} nach Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C} weiterbewegt werden. Für den Fall Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n = 4} , also mit vier Scheiben, ergibt sich also die Zugfolge mit den 15 Lösungsschritten:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_3 \Rightarrow A \to B}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_4 \Rightarrow A \to C}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_3 \Rightarrow B \to C}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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}

Zugfolge für größere Türme

Anzahl
Scheiben 		Anzahl Züge
5 31
10 1023
20 1 048 575
30 1 073 741 823
40 1 099 511 627 775
50 1 125 899 906 842 623
64 18 446 744 073 709 551 615

Die Zahl der bei optimaler Lösung nötigen Züge wächst exponentiell mit der Scheibenzahl. Für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Scheiben werden Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^n-1} Züge benötigt.[3] Die nebenstehende Tabelle zeigt die Anzahl der Züge bei verschiedenen Turmgrößen.

Rekursiver Algorithmus

Die Geschichte um die Mönche und die Zugfolgen für kleine Scheibenanzahlen führen mit einem rekursiven Algorithmus zur Lösung des Spiels. Da sich ein Computerprogramm zur Lösung des Spiels mit wenigen Zeilen schreiben lässt, ist Türme von Hanoi ein klassisches Beispiel für diese Art der Problemlösung.[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 Lösung des eigentlichen Problems wird bewege mit i = n, a = A, b = B und c = C aufgerufen.

Die Funktion bewege löst ein Teilproblem dadurch, dass es dieses in drei einfachere Probleme aufteilt, sofern der zu verschiebende Turm mindestens die Höhe 1 besitzt. Andernfalls ist die Funktion bewege untätig. Die drei Teilprobleme werden sequentiell ausgeführt. Zunächst 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 Stäbe b und c tauschen dabei ihre Rollen. Anschließend 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 > 0) {
       bewege(i-1, a, c, b);
       verschiebe oberste Scheibe von a nach c;
       bewege(i-1, b, a, c);
    }
}

So verhält sich die Funktion bei drei Scheiben (die Stäbe 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 müssen zwei Dinge gezeigt werden. Zum einen müssen die Teillösungen korrekt arbeiten. Zum anderen ist zu zeigen, dass diese überhaupt durchgeführt werden können. Schließlich darf keine der Scheiben, die bei Teillösungen nicht betrachtet werden, den Transport verhindern. Dass dem tatsächlich so ist, folgt aus der Eigenschaft, dass die Funktion bewege bei jeder Teillösung immer nur die kleinsten i Scheiben bewegt. Sowohl diese Eigenschaft als auch die Korrektheit der Teillösungen lässt sich durch vollständige Induktion zeigen.

Iterativer Algorithmus

Uhrzeigersinn

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 verständlich. Es sei vorausgesetzt, dass die Stäbe 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 Stäbe A und B Scheiben befinden, wird erst die kleinste Scheibe (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_1} ) im Uhrzeigersinn und anschließend, sofern dies möglich ist, eine von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_1} verschiedene Scheibe verschoben. Als Pseudocode notiert ergibt sich also folgender Algorithmus: 

solange (Stab A oder B enthalten Scheiben) {
    Verschiebe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_1}
 im Uhrzeigersinn um einen Platz;
    falls (eine von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_1}
 verschiedene Scheibe ist verschiebbar)
        Verschiebe eine von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_1}
 verschiedene Scheibe;
}

So verhält sich die Funktion bei drei Scheiben (vergleiche Bild oben).

Um mit dem Bild zu synchronisieren, wird Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_1} 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 // Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_1}
 von A nach C
A = 3,0,0 | B = 2,0,0 | C = 1,0,0 // Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_2}
 von A nach B

Zweiter Durchlauf:
A = 3,0,0 | B = 2,1,0 | C = 0,0,0 // Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_1}
 von C nach B
A = 0,0,0 | B = 2,1,0 | C = 3,0,0 // Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_3}
 von A nach C

Dritter Durchlauf:
A = 1,0,0 | B = 2,0,0 | C = 3,0,0 // Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_1}
 von B nach A
A = 1,0,0 | B = 0,0,0 | C = 3,2,0 // Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_2}
 von B nach C

Letzter Durchlauf
A = 0,0,0 | B = 0,0,0 | C = 3,2,1 // Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_1}
 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 möglich und auch eindeutig. Um dies einzusehen, sei der Stab, auf dem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_1} liegt mit a und von den beiden verbliebenen Stäben 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 Möglichkeit, eine Scheibe verschieden von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_1} zu verschieben. Denn weder die oberste Scheibe von b noch von c kann auf a verschoben werden, da dort mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_1} die kleinste Scheibe liegt. Auch ein Verschieben der obersten Scheibe von c nach b ist nach Wahl der Bezeichnungen der Stäbe nicht möglich. Der Fall, dass keine andere Scheibe als Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_1} verschiebbar ist, tritt nur dann ein, wenn alle Scheiben wieder auf einem Stab liegen, das Ziel also bereits erreicht ist.

Gerade / Ungerade Ziffern

Ein weiterer Lösungsweg 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 Abzählen 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 möglich 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 größere Scheibe, falls das nicht möglich ist, auf ein Leerfeld.

Optimalität der Algorithmen

Es gibt für jede Scheibenanzahl nur einen optimalen Lösungsweg für das Problem, also nur eine kürzeste Zugfolge. Diese wird von beiden Algorithmen durchlaufen. In diesem Sinne sind die Algorithmen also optimal.

Für den rekursiven Algorithmus lässt sich dies leicht einsehen.[3] Bevor die unterste Scheibe eines (Teil-)Turmes verschoben werden kann, müssen alle darüberliegenden Scheiben auf das Zwischenziel verschoben werden (dort müssen sie natürlich 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 ursprünglich über dieser Scheibe liegenden Scheiben auf dem Zwischenziel liegen, kann keine dieser kleineren Scheiben das Verschieben der untersten Scheibe auf das Ziel blockieren.

Für die Optimalität des iterativen Algorithmus genügt es zu zeigen, dass die durch den rekursiven Algorithmus bestimmte Zugfolge den Bedingungen des iterativen Algorithmus genügt. Dies ergibt sich aus der folgenden Überlegung: 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 Optimalität niemals zweimal direkt hintereinander bewegt wird, wird sie in jedem zweiten Zug versetzt. Die zyklische Richtung, in der die beiden Teiltürme in einem Aufruf der Funktion versetzt werden, ist für die beiden rekursiven Aufrufe a–c–b und b–a–c der Funktion dieselbe, nämlich der Richtung a–b–c entgegengesetzt. Infolgedessen ist die zyklische Richtung für alle Aufrufe mit i = 1 dieselbe, das heißt, die kleinste Scheibe wird immer in derselben Richtung bewegt. Somit erzeugt der rekursive Algorithmus dieselbe Zugfolge wie der iterative.

Der iterative Algorithmus führt auch dann zur Lösung, wenn die Stäbe 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 erfüllt ist, wird anschließend weiter auf C verschoben. Der Algorithmus benötigt in diesem Fall damit doppelt so viele Züge, ist dann also nicht optimal.

Für eine optimale Zugfolge sind folgende Bedingungen offensichtlich notwendig:

  1. Eine bestimmte Spielsituation darf nicht erneut erreicht werden.
  2. Die zuletzt bewegte Scheibe darf nicht gleich noch einmal bewegt werden.

Sie sind aber nicht hinreichend, dies zeigt das Beispiel für drei Scheiben mit insgesamt 11 Zügen:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_1 \Rightarrow A \to B} | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_2 \Rightarrow A \to C} | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_1 \Rightarrow B \to C} | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_3 \Rightarrow A \to B} |Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_1 \Rightarrow C \to B} | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_2 \Rightarrow C \to A} | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_1 \Rightarrow B \to A} | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_3 \Rightarrow B \to C} | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_1 \Rightarrow A \to B} | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_2 \Rightarrow A \to C} | Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_1 \Rightarrow B \to C}

Die oben angegebenen Zugfolgen für kleine Scheibenanzahlen sind optimal, entsprechen also genau den Zugfolgen, die von den Algorithmen erzeugt werden.

Eigenschaften optimaler Zugfolgen

Für optimale Zugfolgen lassen sich eine ganze Reihe von Eigenschaften herleiten. Wegen der Optimalität des rekursiven Algorithmus ist dies besonders leicht anhand seiner Funktionsweise möglich.

Sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} wieder die Anzahl der Scheiben. Die Anzahl der Züge der optimalen Lösung ist dann Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^n-1} . Dies lässt sich leicht induktiv zeigen. Für eine einzelne Scheibe ist dies sicher richtig, denn diese muss nur von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} nach Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C} verschoben werden. Die optimale Zugfolge besteht also, wie behauptet, aus einem Zug. Für größere Scheibenanzahlen wird die Anzahl der Züge durch Summation der Züge für die Teilprobleme nachgewiesen. Die Zuganzahl entspricht also dem Doppelten der minimalen Zuganzahl für den um eine Scheibe kleineren Turm, da dieser zweimal bewegt werden muss, plus den einen Zug, um die größte Scheibe zu bewegen. Wie behauptet folgt:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left(2^{n-1}-1\right) + 1 + \left(2^{n-1}-1\right) = 2^n-1.}

Es lässt sich leicht bestimmen, wie oft und bei welchen Zügen eine Scheibe bei einer optimalen Zugfolge bewegt wird. Allgemein gilt, dass die Scheibe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_k} genau Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^{n-k}} mal bewegt wird. Dabei wird sie beim Zug Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^{k-1}} das erste Mal und dann nach jeweils Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^{k}} Zügen erneut bewegt. Die kleinste Scheibe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_1} wird bei jedem zweiten Zug bewegt, beginnend mit dem ersten Zug. Die zweitkleinste Scheibe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_2} wird bei jedem vierten Zug bewegt, beginnend mit dem zweiten Zug. Die größte Scheibe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_n} wird einmal bewegt, und zwar beim mittleren, also dem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^{n-1}} -ten Zug. Die zweitgrößte Scheibe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_{n-1}} wird zweimal bewegt, und zwar nach dem ersten und dritten Viertel der um 1 erhöhten Zugfolge, also bei den Zügen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^{n-2}} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 3 \cdot 2^{n-2}} . Auf diese Weise ist es möglich, an jedem Punkt der Zugfolge zu bestimmen, welche Scheibe als Nächstes bewegt werden muss.

Der Spielbaum und das Sierpiński-Dreieck

Datei:Hanoi-Graph-3-text.png
Spielbaum zum Turm der Höhe 3
Spielbaum zum Turm der Höhe 7, der sich dem Sierpinski-Dreieck annähert.

Stellt man alle erlaubten Spielzüge in einem Graphen dar, dann erhält 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 größten Scheibe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_n} .

Die nebenstehende Grafik zeigt den Spielbaum eines Turms der Höhe 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 für die kleinste, Gelb für die mittlere und Blau für die größte Scheibe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_3} .

Der erste Zug der optimalen Lösung – oben bezeichnet mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_1} -AC – entspricht also der roten Kante zwischen AAA und AAC und bewegt die kleine rote Scheibe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_1} von A nach C. Danach wird die gelbe Scheibe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_2} von A nach B gezogen und die Stellung dadurch von AAC zu ABC verändert.

Die Anzahl der Knoten im Graph – also die Anzahl möglicher Spielstellungen – ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 3^n} , denn jede Scheibe kann sich auf jedem Stab befinden und bei mehreren Scheiben auf demselben Stab ist deren Anordnung aufgrund ihrer Größe eindeutig gegeben.

Von jeder Spielstellung aus lässt sich die kleinste Scheibe auf zwei andere Stäbe bewegen. Sind nicht alle Scheiben auf dem gleichen Stab, darf man zudem noch die nächstkleinere, obenliegende Scheibe bewegen. Von allen Stellungen aus hat man also drei Zugmöglichkeiten, außer an den Ausgangspositionen AAA, BBB und CCC, in denen nur zwei Züge möglich sind.

Die Anzahl der Kanten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k_n} im Graph ist also

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k_n \;=\; \frac{3\cdot2 \,+\, (3^n-3)\cdot3}{2} \;=\; \frac{3}{2}\,(3^n-1) }

Die Division durch Zwei rührt daher, dass jede Kante zu zwei Knoten gehört. Die Gesamtheit aller Züge ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2k_n} , da man Hin- und Rückzug unterscheiden muss.

Durch den rekursiven Aufbau des Spielgraphen lässt sich leicht nachweisen, dass der Durchmesser des Graphen gleich Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^n-1} ist. Das heißt, von einer gegebenen Stellung aus ist jede andere Stellung mit höchstens Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^n-1} Zügen erreichbar, und es gibt Stellungen, deren kürzeste Verbindung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^n-1} Züge umfasst, wie zum Beispiel die optimale Zugfolge von der Start- zur Endstellung.

Erhöht man einen Turm um eine Scheibe, dann wachsen sowohl die Anzahl der Knoten als auch die Anzahl der Kanten seines Spielbaumes in der Größenordnung von 3, während der geometrische Durchmesser in der gewählten Veranschaulichung um den Faktor 2 wächst. Normiert man die Spielbäume auf den Durchmesser Eins, dann strebt die Folge der so normierten Graphen gegen das Sierpinski-Dreieck.

Die Grenzstruktur ist also ein selbstähnliches Fraktal mit der Hausdorff-Dimension Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle H = \log3 / \log2 = 1{,}58496...}

Literatur

  • Andreas M. Hinz, Sandi Klavžar, Ciril Petr: The Tower of Hanoi. Myth and Math, 2. Auflage, Birkhäuser 2018
  • Martin Gardner: Das Ikosaeder Spiel und der Turm von Hanoi, in: Martin Gardner, Mathematische Rätsel 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

Einzelnachweise

  1. ↑ a b Martin Gardner: Das Ikosaeder Spiel und der Turm von Hanoi, in: Martin Gardner, Mathematische Rätsel und Probleme, Vieweg 1964
  2. ↑ Andreas M. Hinz, Sandi Klavžar, Ciril Petr: The Tower of Hanoi. Myth and Math, 2. Auflage, Birkhäuser 2018
  3. ↑ a b c Florian Freistetter: Die Türme der Apokalypse. In: spektrum.de, Artikel vom 14. November 2021, aufgerufen am 11. Mai 2022.
  4. ↑ 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 älteren Ausgaben von Ball, z. B. in der Ausgabe von 1905)
  5. ↑ Henry Ernest Dudeney: The Canterbury Puzzles, New York, Dutton 1908, S. 1–2, als The Reve's Puzzle.
  6. ↑ Ronald L. Graham, Donald E. Knuth, Oren Patashnik: Concrete Mathematics. Kap. 1.1, S. 1ff (archive.org).
  7. ↑ 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).
  8. ↑ 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.
Abgerufen von „https://de.wikiup.org/index.php?title=Türme_von_Hanoi&oldid=225294191“