So lösen Sie das Problem des Turms von Hanoi - Ein illustrierter Algorithmus-Leitfaden

Bevor wir anfangen, lassen Sie uns über das Problem des Turms von Hanoi sprechen. Nun, dies ist ein lustiges Puzzlespiel, bei dem das Ziel darin besteht, einen ganzen Stapel Festplatten von der Quellposition an eine andere Position zu verschieben. Es werden drei einfache Regeln befolgt:

  1. Es kann jeweils nur eine Festplatte verschoben werden.
  2. Jeder Zug besteht darin, die obere Scheibe von einem der Stapel zu nehmen und auf einen anderen Stapel zu legen. Mit anderen Worten, eine Festplatte kann nur verschoben werden, wenn es sich um die oberste Festplatte auf einem Stapel handelt.
  3. Es darf keine größere Festplatte auf eine kleinere Festplatte gelegt werden.

Versuchen wir uns nun ein Szenario vorzustellen. Angenommen, wir haben einen Stapel von drei Festplatten. Unsere Aufgabe ist es, diesen Stapel von Quelle A zu Ziel C zu verschieben . Wie machen wir das?

Bevor wir dort ankommen können, stellen wir uns vor gibt es einen Zwischenpunkt B .

Wir können B als Helfer verwenden, um diesen Job zu beenden. Wir sind jetzt bereit weiterzumachen. Lassen Sie uns jeden der Schritte durchgehen:

  1. Verschieben Sie die erste Festplatte von A nach C.
  2. Verschieben Sie die erste Festplatte von A nach B.
  3. Verschieben Sie die erste Festplatte von C nach B.
  4. Verschieben Sie die erste Festplatte von A nach C.
  5. Verschieben Sie die erste Festplatte von B nach A.
  6. Verschieben Sie die erste Festplatte von B nach C.
  7. Verschieben Sie die erste Festplatte von A nach C.

Boom! Wir haben unser Problem gelöst.

Sie können das animierte Bild oben zum besseren Verständnis sehen.

Versuchen wir nun, den Algorithmus zu erstellen, um das Problem zu lösen. Warten Sie, wir haben hier ein neues Wort: " Algorithmus ". Was ist das? Irgendeine Idee? Kein Problem, mal sehen.

Was ist ein Algorithmus?

Ein Algorithmus ist eines der wichtigsten Konzepte für einen Softwareentwickler. Tatsächlich denke ich, dass es nicht nur für die Softwareentwicklung oder -programmierung wichtig ist, sondern für alle. Algorithmen beeinflussen uns in unserem täglichen Leben. Mal sehen wie.

Angenommen, Sie arbeiten in einem Büro. So erledigen Sie jeden Morgen eine Reihe von Aufgaben in einer Sequenz: Zuerst wachen Sie auf, dann gehen Sie in den Waschraum, frühstücken, bereiten sich auf das Büro vor, verlassen das Haus, dann können Sie ein Taxi oder einen Bus nehmen oder zu Fuß in Richtung gehen Büro und nach einer gewissen Zeit erreichen Sie Ihr Büro. Sie können sagen, dass alle diese Schritte einen Algorithmus bilden .

In einfachen Worten ist ein Algorithmus eine Reihe von Aufgaben. Ich hoffe, Sie haben die Schritte, die wir unternommen haben, um drei Plattenstapel von A nach C zu verschieben, nicht vergessen. Sie können auch sagen, dass diese Schritte der Algorithmus zur Lösung des Tower of Hanoi-Problems sind.

In der Mathematik und Informatik ist ein Algorithmus eine eindeutige Spezifikation zur Lösung einer Klasse von Problemen. Algorithmen können Berechnungs-, Datenverarbeitungs- und automatisierte Argumentationsaufgaben ausführen. - Wikipedia

Wenn Sie sich diese Schritte ansehen, sehen Sie, dass wir dieselbe Aufgabe mehrmals ausgeführt haben - das Verschieben von Festplatten von einem Stapel auf einen anderen. Wir können diese Schritte innerhalb der Schrittrekursion nennen .

Rekursion

Rekursionruft dieselbe Aktion von dieser Aktion auf. Genau wie auf dem obigen Bild.

Es gibt also eine Regel für rekursive Arbeiten: Es muss eine Bedingung vorhanden sein, um die Ausführung dieser Aktion zu stoppen. Ich hoffe, Sie verstehen die Grundlagen der Rekursion.

Versuchen wir nun, ein Verfahren zu entwickeln, mit dem wir das Problem des Turms von Hanoi lösen können. Wir versuchen, die Lösung mit Pseudocode zu erstellen . Pseudocode ist eine Methode zum Schreiben von Computercode in englischer Sprache.

tower(disk, source, intermediate, destination) { }

Dies ist das Grundgerüst unserer Lösung. Wir nehmen die Gesamtzahl der Festplatten als Argument. Dann müssen wir die Quelle, den Zwischenort und das Ziel übergeben, damit wir die Karte verstehen können, die wir zum Abschließen des Auftrags verwenden werden.

Jetzt müssen wir einen finden Zu . Der Terminalstatus ist der Status, in dem wir diese Funktion nicht mehr aufrufen werden.

IF disk is equal 1

In unserem Fall wäre dies unser Endzustand. Denn wenn sich eine Festplatte in unserem Stapel befindet, ist es einfach, diesen letzten Schritt auszuführen, und danach ist unsere Aufgabe erledigt. Mach dir keine Sorgen, wenn es dir nicht klar ist. Wenn wir das Ende erreichen, wird dieses Konzept klarer.

Okay, wir haben unseren Endpunkt gefunden, an dem wir unsere Festplatte wie folgt an das Ziel verschieben:

move disk from source to destination

Jetzt rufen wir unsere Funktion erneut auf, indem wir diese Argumente übergeben. In diesem Fall teilen wir den Plattenstapel in zwei Teile. Die größte Festplatte ( n-te Festplatte) befindet sich in einem Teil und alle anderen ( n-1 ) Festplatten befinden sich im zweiten Teil. Dort rufen wir die Methode zweimal für - (n-1) auf.

tower(disk - 1, source, destination, intermediate)

Wie gesagt, wir übergeben total_disks_on_stack - 1 als Argument. Und dann bewegen wir unsere Festplatte wie folgt:

move disk from source to destination

Danach rufen wir unsere Methode wieder so auf:

tower(disk - 1, intermediate, source, destination)

Sehen wir uns unseren vollständigen Pseudocode an:

tower(disk, source, inter, dest) IF disk is equal 1, THEN move disk from source to destination ELSE tower(disk - 1, source, destination, intermediate) // Step 1 move disk from source to destination // Step 2 tower(disk - 1, intermediate, source, destination) // Step 3 END IF END

Dies ist der Baum für drei Festplatten:

Dies ist der vollständige Code in Ruby:

def tower(disk_numbers, source, auxilary, destination) if disk_numbers == 1 puts "#{source} -> #{destination}" return end tower(disk_numbers - 1, source, destination, auxilary) puts "#{source} -> #{destination}" tower(disk_numbers - 1, auxilary, source, destination) nil end

Anruf tower(3, 'source','aux','dest')

Ausgabe:

source -> dest source -> aux dest -> aux source -> dest aux -> source aux -> dest source -> dest

Es dauerte sieben Schritte, bis drei Festplatten das Ziel erreichten. Wir nennen dies eine rekursive Methode .

Berechnungen der Zeitkomplexität und der Raumkomplexität

Zeitliche Komplexität

Wenn wir Code oder eine Anwendung auf unserem Computer ausführen, dauert es einige Zeit - CPU-Zyklen. Aber es ist nicht für jeden Computer gleich. Beispielsweise ist die Verarbeitungszeit für einen Core i7 und einen Dual Core nicht gleich. Um dieses Problem zu lösen, gibt es in der Informatik ein Konzept namens Zeitkomplexität .

Zeitkomplexität ist ein Konzept in der Informatik, das sich mit der Quantifizierung der Zeit befasst, die ein Satz von Code oder Algorithmus benötigt, um in Abhängigkeit von der Menge der Eingabe zu verarbeiten oder auszuführen.

In other words, time complexity is essentially efficiency, or how long a program function takes to process a given input. — techopedia

The time complexity of algorithms is most commonly expressed using big O notation. It’s an asymptotic notation to represent the time complexity.

Now, the time required to move n disks is T(n). There are two recursive calls for (n-1). There is one constant time operation to move a disk from source to the destination, let this be m1. Therefore:

T(n) = 2T(n-1) + m1 ..... eq(1)

And

T(0) = m2, a constant ...... eq(2) From eq (1) T(1) = 2T(1-1) + m1 = 2T(0)+m1 = 2m2 + m1 ..... eq(3) [From eq 2] T(2) = 2T(2-1) + m1 = 2T(1) + m1 = 4m2 + 2m1 + m1 .... eq(4) [From eq(3)] T(3) = 2T(3-1) + m1 = 2T(2) + m1 = 8m2 + 4m1 + 2m1 + m1 [From eq(4)]

From these patterns — eq(2) to the last one — we can say that the time complexity of this algorithm is O(2^n) or O(a^n) where a is a constant greater than 1. So it has exponential time complexity. For the single increase in problem size, the time required is double the previous one. This is computationally very expensive. Most of the recursive programs take exponential time, and that is why it is very hard to write them iteratively.

Space complexity

After the explanation of time complexity analysis, I think you can guess now what this is…This is the calculation of space required in ram for running a code or application.

In our case, the space for the parameter for each call is independent of n,meaning it is constant. Let it be J. When we do the second recursive call, the first one is over. That means that we can reuse the space after finishing the first one. Hence:

T(n) = T(n-1) + k .... eq(1) T(0) = k, [constant] .... eq(2) T(1) = T(1-1) + k = T(0) + k = 2K T(2) = 3k T(3) = 4k

So the space complexity is O(n).

After these analyses, we can see that time complexity of this algorithm is exponential but space complexity is linear.

Conclusion

From this article, I hope you can now understand the Tower of Hanoi puzzle and how to solve it. Also, I tried to give you some basic understanding about algorithms, their importance, recursion, pseudocode, time complexity, and space complexity. If you want to learn these topics in detail, here are some well-known online courses links:

  1. Algorithms, Part I
  2. Algorithms, Part II
  3. The Google course on Udacity
  4. Javascript Algorithms And Data Structures Certification (300 hours)

You can visit my data structures and algorithms repoto see my other problems solutions.

I am on GitHub | Twitter | LinkedIn