Turm von Hanoi Problem Erklärt - Java Rekursive Lösung

Der Turm von Hanoi ist ein klassisches Problem in der Welt der Programmierung. Die Problemstellung besteht aus drei Stangen/Pfählen und n Scheiben.

Die Scheiben können von einem Pfahl zum anderen bewegt werden. Die n Scheiben sind unterschiedlich groß.

Zunächst sind alle Scheiben auf dem ersten Turm gestapelt. Die Scheiben sind so gestapelt, dass eine Scheibe immer über einer größeren Scheibe liegt.

Standardaufstellung des Turms von Hanoi

Turm von Hanoi Aufstellung

Historischer Hintergrund

Interessante Tatsache: Dieses Spiel wurde im 19. Jahrhundert von dem französischen Mathematiker Édouard Lucas erfunden. Es wird mit einer Legende eines Hindu-Tempels in Verbindung gebracht, in dem das Rätsel angeblich genutzt wurde, um die geistige Disziplin junger Priester zu erhöhen.

Problemstellung

Verschieben Sie alle auf dem ersten Turm gestapelten Scheiben auf den letzten Turm mit Hilfe eines Hilfsturms in der Mitte. Beim Bewegen der Scheiben müssen bestimmte Regeln befolgt werden. Diese lauten:

1. Es kann nur eine Scheibe bewegt werden.
2. Eine größere Scheibe darf nicht auf eine kleinere Scheibe gelegt werden.

Sie müssen also alle Scheiben vom ersten Turm auf den letzten bewegen. Sie können jeweils nur eine Scheibe bewegen und niemals eine kleinere Scheibe über eine größere legen.

Dafür haben Sie einen zusätzlichen Turm, er wird als Hilfs-/Zwischenturm bezeichnet.

Da Sie jeweils nur eine Scheibe bewegen können, muss die zu bewegende Scheibe immer oben auf ihrem Turm liegen.

Theoretische Lösung des Turm von Hanoi Problems

Nennen wir die Türme A, B, C und die Scheiben 1, 2, 3.

Turm von Hanoi

Wir lösen diese Frage mit einfacher Rekursion. Um die drei Scheiben auf den letzten Turm zu bekommen, müssen Sie:

1. Die Scheibe Nummer 1 und 2 auf Turm B bringen.
2. Die Scheibe Nummer 3 auf Turm C bewegen.
3. Die Scheibe Nummer 1 und 2 von B nach C bringen.

Natürlich können Sie es nicht genau so machen wegen der Einschränkungen. Aber wir können dies nutzen, um eine Funktion zu erstellen, die es rekursiv macht.

TOH 1 Anfangszustand

In der Funktion, die wir schreiben, werden wir die Bewegung der Scheiben ausdrucken.

Implementierung der Lösung des Turms von Hanoi in Java

Lassen Sie uns mit dem Verständnis der beiden Hauptteile des Codes beginnen, um das Turm von Hanoi-Problem zu lösen.

1. Basisfall: Der Basisfall in unserem Code ist, wenn wir nur eine Scheibe haben. Das ist n=1.

if (n == 1)
{
    System.out.println("Nimm Scheibe 1 von Stange " +  from_rod + " nach Stange " + to_rod);
    return;
}

2. Rekursive Aufrufe: Die rekursiven Aufrufe zur Lösung des Turms von Hanoi sind wie folgt:

towerOfHanoi(n-1, from_rod, helper_rod, to_rod);
System.out.println("Nimm Scheibe " + n + " von Stange " +  from_rod + " nach Stange " + to_rod);
towerOfHanoi(n-1, helper_rod, to_rod, from_rod);

Diese entsprechen:

1. Die oberen n-1 Scheiben auf den Hilfsturm bewegen.
2. 1 Scheibe von der Quellstange zur Zielstange bewegen.
3. Die n-1 Scheiben vom Hilfsturm zur Zielstange nehmen.

Vollständige Java-Implementierung des Turms von Hanoi

package com.JournalDev;
public class Main {
    static void towerOfHanoi(int n, char from_rod, char to_rod, char helper_rod)
    {
        if (n == 1)
        {
            System.out.println("Nimm Scheibe 1 von Stange " +  from_rod + " nach Stange " + to_rod);
            return;
        }
        towerOfHanoi(n-1, from_rod, helper_rod, to_rod);
        System.out.println("Nimm Scheibe " + n + " von Stange " +  from_rod + " nach Stange " + to_rod);
        towerOfHanoi(n-1, helper_rod, to_rod, from_rod);
    }

    public static void main(String args[])
    {
        int n = 5;
        towerOfHanoi(n,'A','C', 'B');
    }

}

Ausgabe des Turms von Hanoi

Die Ausgabe des Codes ist:

Nimm Scheibe 1 von Stange A nach Stange C
Nimm Scheibe 2 von Stange A nach Stange B
Nimm Scheibe 1 von Stange C nach Stange B
Nimm Scheibe 3 von Stange A nach Stange C
Nimm Scheibe 1 von Stange B nach Stange A
Nimm Scheibe 2 von Stange B nach Stange C
Nimm Scheibe 1 von Stange A nach Stange C
...

Wir können den Prozess anhand der folgenden Illustration verstehen. Sie können den Code für eine beliebige Anzahl von Scheiben ausführen.

TOH für n=5

n=5

Die Formel zur Berechnung der Anzahl der Schritte für n Scheiben lautet:

(2^n)-1

Fazit

Der Turm von Hanoi ist ein faszinierendes Beispiel für rekursive Algorithmen und logisches Denken in der Programmierung. Es verdeutlicht, wie man komplexe Probleme durch strukturiertes Vorgehen effizient lösen kann. Wer sich mit Algorithmen und Datenstrukturen beschäftigt, kommt an diesem Klassiker kaum vorbei.

Wenn Sie Ihr Wissen über effiziente Algorithmen vertiefen oder maßgeschneiderte IT-Lösungen für Ihr Unternehmen entdecken möchten, registrieren Sie sich jetzt im ccenter oder kontaktieren Sie unser Sales-Team für eine individuelle Beratung.