Der Turm von Hanoi

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

Verschiebe 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.

Du musst also alle Scheiben vom ersten Turm auf den letzten bewegen. Du kannst jeweils nur eine Scheibe bewegen und niemals eine kleinere Scheibe über eine größere legen.

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

Da du jeweils nur eine Scheibe bewegen kannst, 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, musst du:

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 kannst du 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

Lass 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. Du kannst 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

So löst du den Turm von Hanoi mit Rekursion. Wir hoffen, dass wir es gut erklärt haben und du Spaß beim Lernen mit uns hattest!