Türme von Hanoi
Es gibt 3 Stäbe (links – 1, Mitte – 2 und rechts – 3). Auf dem ersten Stab liegen
n unterschiedlich große, runde Scheiben. Die Scheiben sind in aufsteigender Größenfolge von oben nach unten angeordnet. Man darf die oberste Scheibe von einem Stab auf einen anderen bewegen und dabei nur auf eine größere Scheibe legen. Das Ablegen einer größeren Scheibe auf einer kleineren ist nicht erlaubt.Ihre Aufgabe ist es, alle Schritte auszugeben, die dazu führen, alle Scheiben vom ersten Stab auf den dritten zu bringen. Dabei soll die Anzahl der Züge minimal sein.
Eingabe
Die Eingabe enthält eine ganze Zahl
n (1 ≤ n ≤ 16), die angibt, wie viele Scheiben sich auf dem ersten Stab befinden.Ausgabe
Das Programm soll alle erforderlichen Züge ausgeben, mit denen die Scheiben vom ersten Stab auf den dritten transportiert werden können, ohne dass eine größere Scheibe auf einer kleineren liegt. Die Ausgabe darf nicht mehr als Zeilen umfassen.
Beispiele
Input | Output |
2 | 1 -> 2
1 -> 3
2 -> 3 |
3 | 1 -> 3
1 -> 2
3 -> 2
1 -> 3
2 -> 1
2 -> 3
1 -> 3 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB