Problem
Puzzle “Torres de Hanoi” consta de tres varillas, numeradas 1, 2, 3. Una pirámide de n discos de diferentes diámetros se coloca sobre la varilla 1 en orden ascendente de diámetro. Los discos se pueden transferir de una varilla a otra a la vez, mientras que el disco no se puede colocar en un disco de menor diámetro. Es necesario trasladar toda la pirámide de la varilla 1 a la varilla 3 en el mínimo número de transferencias.
Escriba un programa que resuelva un rompecabezas; para un número dado de discos n imprime una secuencia de permutaciones en el formato a b c, donde a — número del disco desplazado, b — el número de la varilla de la que se extrae este disco, c — el número de la varilla en la que se coloca este disco.
Por ejemplo, la línea 1 2 3 significa mover el disco número 1 del pin 2 al pin 3. Un comando está impreso en una línea. Los discos están numerados del 1 al n en orden creciente de diámetro.
Entrada
Ingrese un número natural n (0 < n < 11).
Salida
El programa debe mostrar la forma mínima (en términos de la cantidad de operaciones realizadas) de reorganizar la pirámide a partir de la cantidad dada de discos.
Ejemplos
| # |
Entrada |
Salida |
| 1 |
2 |
1 1 2
2 1 3
1 2 3
|
Запрещенные операторы: for; while; until