Problem
Puzzle “Towers of Hanoi” consists of three rods, numbered 1, 2, 3. A pyramid of n disks of different diameters is put on rod 1 in ascending order of diameter. The disks can be transferred from one rod to another one at a time, while the disk cannot be placed on a disk of a smaller diameter. It is necessary to transfer the entire pyramid from rod 1 to rod 3 in the minimum number of transfers.
Write a program that solves a puzzle; for a given number of disks n prints a sequence of permutations in the format a b c, where a — number of the shifted disk, b — the number of the rod from which this disk is removed, c — the number of the rod on which this disc is put.
For example, line 1 2 3 means moving disc number 1 from pin 2 to pin 3. One command is printed on one line. The disks are numbered from 1 to n in order of increasing diameter.
Input
Enter a natural number n ( 0 < n < 11).
Output
The program should display the minimum (in terms of the number of operations performed) way of rearranging the pyramid from the given number of disks.
Examples
| # |
Input |
Output |
| 1 |
2 |
1 1 2
2 1 3
1 2 3
|
Запрещенные операторы: for; while; until