Turm von Hanoi 4 Stäbe

Question

bin jetzt schon länger wegen der folgender Aufgabe am Überlegen:

Turm von Hanoi mit vier Stäben

Es seien n Scheiben auf einen von vier Stäben, so dass jede Scheibe auf einer gröÿeren Scheibe liegt. Das Ziel ist, alle n Scheiben auf eine der leeren Stäben zu bringen, wobei dieselben Regeln wie im Fall mit drei Stäben
zu beachten sind.
Man beschreibe eine Rekursion, die das Problem so löst, dass alle Stäbe benutzt werden
und man zeige mit Induktion eine Formel für die benötigte Anzahl von Schritten.

Ich habe mir jetzt überlegt, wie das ganze mit verschiedenen Anzahlen von Scheiben funktionieren soll.

Dabei habe ich folgende Schritte notiert:

n -> B

n-1 -> C

n-2 -> D

n -> C

n-3 -> B

n -> A

n-2 -> B

n-1 -> B

n -> B

Allerdings habe ich keine Ahnung wie ich das formal aufschreiben soll für n Scheiben. Wie beschreibe ich eine solche Rekursion? Ich weiß nicht, wie ich die Schritte allgemein beschreiben soll.

Answer 1

Hallo jni97,

Es gibt keine feste Syntax um einen Algorithmus zu beschreiben. Wenn es keine konkrete Programmiersprache oder ähnliches ist, macht man es in einem Pseudo-Code.

In diesem Fall wäre eine Funktion zu beschreiben, die sich selbst aufruft - ich nenne sie mal move.

Funktion: move( n, quelle, x, y, ziel )

Bedeutet: bringe n Scheiben von der Position quelle über x und y zum ziel. Und könnte so aussehen:

Funktion: move( n, quelle, x, y, ziel )

    if( n <= 3 )    // die Anzahl der Scheiben  ist kleiner oder gleich 3

        move1( quelle, x )    // move1 ist die Bewegung einer Scheibe

        move1( quelle, y )

        move1( quelle, ziel )

        move1( y, ziel )

        move1( x, ziel )

   else    // das heißt wenn n größer als 3 ist

        move( n-2, quelle, x, ziel, y )

        move1( quelle, x )

        move1( quelle, ziel )

        move1( x, ziel )

        move( n-2, y, x, ziel )

und der Aufruf beim Start würde dann lauten:

move( n, A, B, C, D )

Wenn Du Schwierigkeiten hast, die Anzahl der Schritte zu berechnen, so frage noch mal nach.

Gruß Werner

Comments

Hallo Werner,

danke für deine Antwort! Ich wusste nicht, dass man in Mathe Pseudocode benutzen darf, aber das erleichtert die Erklärung natürlich erheblich.

Für die Anzahl der Schritte hätte ich jetzt gesagt:

Anzahl = n * 5, für n <= 3

Anzahl = 2*(n + 3), für n > 3, weil für jedes n zwei Mal move aufgerufen wird und drei Mal der einfache Schritt(move1).

Stimmt das oder liege ich da falsch?

---

Hallo jni97,

Man darf in Mathe alles, was logisch ist. Pseudecode ist nicht unbedingt klar auf Axiomen definiert, aber wer sagt, dass wir hier Mathe machen ...

ich habe den Algorithmus noch mal etwas optimiert. Insbesondere im Bereich kleiner \(n\) kann man es noch mit weniger Schritten machen. Das ist draus geworden:

        if( n <= 1 )
            move1( quelle, ziel );
        else if( n == 2 )
            move1( quelle, y );
            move1( quelle, ziel );
            move1( y, ziel );
        else // n >= 3
            move( n-2, quelle, x, ziel, y );
            move1( quelle, x );
            move1( quelle, ziel );
            move1( x, ziel );
            move( n-2, y, quelle, x, ziel );

Und das sind die Anzahl der Schritte \(s(n)\) in Abhängigkeit der zu verschiebenden Scheiben.

s(1)=1
s(2)=3
s(3)=5
s(4)=9
s(5)=13
s(6)=21
s(7)=29
s(8)=45
s(9)=61
s(10)=93
s(11)=125
s(12)=189
s(13)=253
s(14)=381
s(15)=509
s(16)=765
s(17)=1021
s(18)=1533
s(19)=2045

Du schriebst: "Für die Anzahl der Schritte hätte ich jetzt gesagt: Anzahl = n * 5, für n <= 3

Anzahl = 2*(n + 3), für n > 3"
Das ist definitiv zu wenig. Die Folge wächst exponentiell.  Für die obige Folge habe ich
$$s(n) = 2 s(n-2) + 3$$heraus bekommen.

Gruß Werner

---

Alles klar, danke Dir für die gute Hilfe!

Answer 2

Die Anzahl der Züge beträgt 2^n - 1 bei n Scheiben. 

Ich persönlich würde jetzt den Java Code runter rattert, aber man kann das auch sprachlich ausdrücken bzw. im mathematischen Pseudo Code. Dazu muss man jedoch verstanden haben, wie man das Problem löst. 

Das einfachste ist der rekursive Weg, d.h. eine Funktion, die sich selbst immer wieder aufruft. Die Idee ist dann die Blöcke zu verteilen und auf einem anderen Stab wieder aufzubauen, das schafft man, indem man den großen Turm sinnvoll auf die verbleibenden Stäbe verteilt, und von dieser Verteilung Stückweise wieder eine Zusammensetzung baut. Ich würde das einfach mal mit einem praktischen Selbst versuch machen, da sieht man schnell um was es letztlich geht. 

Comments

\(s(n)=2^n-1\) ist aber deutlich schlechter als es mein Vorschlag mit \(s(n)=2\cdot s(n-2)+3\) mit \(s(1)=1\) und \(s(2)=3\) ist.

Inzwischen habe ich auch die Formel für \(s(n)\) gefunden. Getrennt für gerade und ungerade Werte von \(n\):

$$\begin{aligned}s(n) &= 2^{\frac{n+3}{2}}-3 \quad &n = 2k-1, \space &k \in \mathbb{N} \\s(n)&= 3( 2^{\frac{n}{2}} -1) &n = 2k, \space &k \in \mathbb{N}\end{aligned}$$

---

Ok, das irritiert mich leicht im Studium hab ich auch mal eine Aufgabenstellung gehabt, wo es um die Türme von Hanoi gibt, und wenn mich nicht alles täuscht war, die Laufzeit, die ich vorgeschlagen habe schon optimiert. Aber das finde ich gerade selber recht interessant, ich werde mir das morgen mal ausführlicher ansehen. 

Danke Werner, das gibt mir auch nochmal die Möglichkeit etwas dazu zu lernen!

---

Hallo Fragensteller001,

Bei den klassischen Türmen von Hanoi benötigt man tatsächlich \(2^n-1\) Züge zum Verschieben der Scheiben. Hier haben wird aber vier statt wie üblich drei Plätze (s.o. Aufgabenstellung)

Gruß Werner