Wann wird das Ende der Welt sein?

Vor ein paar Tagen sagte mir ein Freund von mir:

Das Ende der Welt und der Menschheit wird kommen, wenn das Problem der Türme von Hanoi für 64 Disketten gelöst werden konnte.

Das ist ein interessanter Ansatz und ein wunderbarer Witz, um dieses Thema zu beschreiben. Aber wirklich, was ist das? was ist die Bedeutung dieses Satzes?

Nun, um etwas Licht ins Dunkel zu bringen, muss zunächst Hanois Problem selbst beschrieben werden.

Towers of Hanoi ist ein mathematisches Puzzle, bei dem wir drei Stäbe ( A , B und C ) und N Scheiben haben. Zunächst werden alle Scheiben mit abnehmendem Durchmesser gestapelt, dh die kleinste Scheibe wird oben platziert und sie befinden sich aufStange A. Das Ziel des Puzzles ist es, den gesamten Stapel auf eine andere Stange (hier als C bezeichnet ) zu verschieben, wobei die folgenden einfachen Regeln zu befolgen sind:

• Es kann immer nur eine Festplatte verschoben werden.
• Jede Bewegung besteht darin, die oberste Scheibe von einem der Stapel zu nehmen und sie auf einen anderen Stapel zu legen, dh eine Scheibe kann nur bewegt werden, wenn sie die oberste Scheibe auf einem Stapel ist.
• Keine Scheibe darf auf eine kleinere Scheibe gelegt werden.

Im Bild oben sind drei Stangen dargestellt (A, B, C) und werden benötigt, um vier Scheiben zu bewegen. Wir könnten also sagen, dass An das Problem ist, alle Festplatten von A nach C zu verschieben, wobei n die Gesamtzahl der Festplatten ist (in diesem Fall vier). Die Hauptidee ist:

• Nimm n – 1 Scheiben von A (n – 1 erste Scheiben) und bewege sie zu B (unter Verwendung der Hilfsstangen).
• Nehmen Sie die verbleibende Scheibe in A und verschieben Sie sie nach C.
• Lösen Sie das Problem, n — 1 Scheiben in B (Punkt 1) nach C zu bewegen (unter Verwendung der Hilfsstangen).

Diese Formel drückt also aus, dass wir, wenn Sie wissen wollten, wie viele Schritte zum Lösen von Hanoi mit n Scheiben erforderlich sind, nur von einem Basisfall und der letzten Iteration abhängen.

Am Ende lautet der eigentliche Ausdruck für die Lösung, wie viele Schritte erforderlich sind (es könnte eine gute Übung sein):

Und das ist der Beweis:

Nun, zurück zum Ausgangspunkt dieses Papiers und unter Verwendung dieser Formel:

Nur um eine Vorstellung zu machen, wenn wir in der Lage wären, Scheiben mit einer Geschwindigkeit von 1 pro Sekunde zu bewegen, würde es etwa 584 Milliarden Jahre dauern, bis sie fertig sind, was etwa dem 44-fachen des gegenwärtigen Alters des Universums entspricht; Wenn wir also der Idee meines Freundes folgen, brauchen wir uns keine Sorgen zu machen. :)

#hanoi #rekursion #mathe #witz