Java-Programmierung Herausforderung: recursing die Türme von Hanoi
Diese Herausforderung hilft Ihnen, Ihre Programmierung Talente verwenden, um ein Java-Programm zu schreiben, das die Schritte gedruckt werden benötigt, um eine Türme von Hanoi Puzzle die Anzahl der Platten gegeben zu lösen.
Die Türme von Hanoi ist eine klassische Logik-Puzzle, das aus drei vertikalen Zapfen und einer Anzahl von Platten unterschiedlicher Durchmesser besteht. Jede Scheibe hat ein Loch in der Mitte, so dass die Scheiben über die Zapfen gerutscht werden.
Das Puzzle beginnt mit allen der gestapelten Scheiben an einem der Stifte, wobei der größte Platte an der Unterseite und dem kleinsten an der Oberseite. Das Ziel des Puzzles ist es, den Stapel von Scheiben zu einem der anderen Stifte zu bewegen, gehorchen nur zwei einfache Regeln: (1) können Sie nur eine Scheibe zu einem Zeitpunkt zu verschieben, und (2) kann man nie auf eine größere Festplatte platzieren Spitze eines kleineren.
Die folgende Abbildung zeigt die Lösung für einen Stapel von drei Scheiben. Wie Sie sehen können, erfordert die Lösung sieben bewegt:
Bewegen Sie Datenträger 1 von Peg 1 bis Peg 3.
Bewegen Sie Disk 2 von Peg 1 bis Peg 2.
Bewegen Sie Datenträger 1 von Peg 3 bis Peg 2.
Bewegen Sie Datenträger 3 von Peg 1 bis Peg 3.
Bewegen Sie Datenträger 1 von Peg 2 bis Peg 1.
Bewegen Sie Disk 2 von Peg 2 bis Peg 3.
Bewegen Sie Datenträger 1 von Peg 1 bis Peg 3.
Nach diesen sieben Schritten wird der Stapel von Scheiben auf Peg 3 sein.
Das Puzzle wird interessant, wenn Sie Festplatten in die Ausgangsposition beginnen hinzuzufügen. Mit drei Scheiben erfordert das Puzzle nur 7 bewegt sich zu lösen. Mit vier Scheiben werden 15 bewegt erforderlich. Mit fünf Scheiben, werden Sie 31 bewegt benötigen. Sechs Scheiben erfordert 64 bewegt.
Wenn Sie die Mathematik verfolgt haben, die Anzahl der erforderlichen Schritte zur Lösung der Rätsel steigt exponentiell, wie die Anzahl der Platten erhöht. Insbesondere die Anzahl der erforderlichen Bewegungen zu bewegen, n Scheiben 2n- 1. Zum Beispiel kann ein Stapel von 20 Platten werden 2 erfordern20 - 1 moves-, die mehr als eine Million bewegt ist!
Eine interessante Legende ist mit dem Rätsel verbunden sind: in einem Tempel in Hanoi, Mönche wurden seit der Erschaffung der Erde mit 64 Festplatten auf einem Türme von Hanoi Puzzle arbeiten. Wenn sie fertig sind, wird die Welt zu einem Ende kommen. Zum Glück haben wir eine lange Zeit zu warten: Wenn die Mönche eine Scheibe pro Sekunde bewegen kann, wird es weitere 580.000.000.000 Jahre oder so sein, bevor sie das Rätsel zu beenden.
Ihre Herausforderung ist einfach: Schreiben Sie ein Java-Programm, das die Schritte gedruckt werden benötigt, um eine Türme von Hanoi Puzzle die Anzahl der Platten gegeben zu lösen. Das Programm sollte zunächst den Benutzer auffordern, für die Anzahl der Festplatten. Dann sollte es die Schritte angezeigt werden, eine pro Zeile. Jeder Schritt sollte angeben, welche von einer Platte zu bewegen, peg, und die Zapfen die Platte zu bewegen. Die Schritte sollten auch fortlaufend nummeriert werden.
Sobald Sie fertig sind, sollte das Programm wiederholen, wieder den Benutzer für die Anzahl der Platten zu fragen. Das Programm sollte beendet, wenn der Benutzer 0 eintritt.
Hier ist ein Beispiel der Ausgabe der Konsole sollte Ihr Programm erzeugen:
Wie viele Platten? (0 bis Ende) 31: 1 bis 32: 1 bis 23: 3 bis 24: 1 bis 35: 2 bis 16: 2 bis 37: 1 viele Platten zu 3Wie? (0 bis Ende)0
Die einzige andere Anforderung für diese Herausforderung zu lösen ist, dass Ihre Lösung rekursive Programmierung verwenden. Mit anderen Worten, müssen Sie Ihre Lösung umfassen ein Verfahren, das sich um das Rätsel zu lösen, nennt.
Rekursive Programmierung kann eine Herausforderung sein, so dass hier ein paar Hinweise zur Lösung dieses Rätsels sind:
Das Puzzle besteht aus drei Heringen. Einer von ihnen enthält den Startstack von disks- nennen diese peg die Quelle peg. Einer der verbleibenden beiden Zapfen ist der Zapfen Sie den Stapel von Scheiben zu bewegen wollen, dass diese die peg to- nennen Ziel peg. Der dritte Zapfen ist für Sie als Zwischen Zapfen zu verwenden Platten zu speichern, auf vorübergehend, wie Sie sie bewegen. Rufen Sie diese peg die Ersatz peg.
Ihre rekursive Methode sollte drei Parameter akzeptieren: die Anzahl der Platten zu bewegen, Quelle Pflock, und die Ziel peg. Verwenden Sie die ganzzahligen Werte 1, 2 und 3, um die Zapfen darstellen.
Die Grundidee, das Puzzle rekursiv zu lösen, ist dies: Um einen Stapel von Scheiben aus einer Quelle Bindung an ein Ziel peg erfordert drei Schritte zu bewegen:
Verschieben Sie alle Platten in dem Stapel mit Ausnahme der Bodenplatte auf den Ersatz peg.
Bewegen Sie die größte Festplatte im Originalstapel auf den Ziel peg.
Bewegen Sie den Stapel Sie 1 von der Ersatz Bindung an den Ziel Pflock in Schritt bewegt.
Natürlich lassen Puzzle Regeln, die Sie nur eine Platte zu einem Zeitpunkt zu verschieben, so dass Sie hier nicht einfach durch Abnehmen des Stapels und bewegen es gegeben Schritte 1 und 3 des Verfahrens zu erreichen. Das ist, wo die Rekursion kommt. Für die Schritte 1 und 3, rufen Sie die Methode rekursiv, jedes Mal die Angabe einer weniger Scheibe bewegt werden, und jedes Mal den bisherigen Ziel peg als Ersatz peg verwenden.
Sie fragen sich, warum der rekursiven Methode nicht das Reserverad peg als Argument akzeptieren müssen? Weil Sie leicht berechnen kann, die Quell- und Ziel Heringe gegeben. Da es nur drei Stifte sind, 1, Nummern 2 und 3, wobei die Summe der drei Stifte 6 (1 + 2 + 3). In Anbetracht der Quell- und Ziel Heringe, können Sie den Ersatz peg berechnen, indem die Quell- und Ziel-peg von 6. Zum Beispiel subtrahiert, wenn die Quelle peg 1 ist und der Ziel peg 3 ist, muss der Ersatz peg sein 2, weil
6 - 3 - 1 = 2.
Für die Lösung gehen, bis die Registerkarte Downloads des Java All-in-One For Dummies, 4th Edition Produktseite.
Viel Glück!