Problem
Das Puzzle "Türme von Hanoi" besteht aus drei Stäben, die mit den Zahlen 1, 2, 3 nummeriert sind. An der Stange 1 ist eine Pyramide von n Scheiben mit unterschiedlichem Durchmesser in aufsteigender Reihenfolge des Durchmessers angebracht. Die Scheiben können nacheinander von einem Stab zum anderen verschoben werden, wobei die Scheibe nicht auf eine Scheibe mit kleinerem Durchmesser gelegt werden kann. Es ist notwendig, die gesamte Pyramide für eine minimale Anzahl von Verschiebungen von Stange 1 auf Stange 3 zu verschieben.
Schreiben Sie ein Programm, das das Rätsel löst; Für eine bestimmte Anzahl von Discs druckt n die Verschiebungssequenz im Format a b c, wobei a die Nummer der zu verschiebenden Disc ist, b die Nummer des Stabes, von dem die Disc entfernt wird, c die Nummer des Stabes, auf den die Disc gelegt wird.
Zum Beispiel bedeutet Zeile 1 2 3, dass die Disk Nummer 1 von Stange 2 auf Stange 3 verschoben wird. Ein Befehl wird in einer Zeile gedruckt. Die Scheiben sind mit Zahlen von 1 bis n in aufsteigender Reihenfolge der Durchmesser nummeriert.
Eingabe
Die natürliche Zahl n wird eingegeben ( 0 < n < 11).
Ausgabe
Das Programm sollte die minimale (nach der Anzahl der durchgeführten Operationen) Methode zum Verschieben der Pyramide von der angegebenen Anzahl von Festplatten ausgeben.
Beispiele
| № |
Eingabe |
Ausgabe |
| 1 |
2 |
1 1 2
2 1 3
1 2 3
|
Запрещенные операторы: for; while; until