Problem
Quebra-cabeça “Torres de Hanói” consiste em três hastes, numeradas 1, 2, 3. Uma pirâmide de n discos de diferentes diâmetros é colocada na haste 1 em ordem crescente de diâmetro. Os discos podem ser transferidos de uma haste para outra de cada vez, enquanto o disco não pode ser colocado sobre um disco de diâmetro menor. É necessário transferir toda a pirâmide da haste 1 para a haste 3 no número mínimo de transferências.
Escreva um programa que resolva um quebra-cabeça; para um determinado número de discos n imprime uma sequência de permutações no formato a b c, onde a — número do disco deslocado, b — o número da haste da qual este disco é removido, c — o número da haste em que este disco é colocado.
Por exemplo, a linha 1 2 3 significa mover o disco número 1 do pino 2 para o pino 3. Um comando é impresso em uma linha. Os discos são numerados de 1 a n em ordem crescente de diâmetro.
Entrada
Digite um número natural n ( 0 < n < 11).
Saída
O programa deve exibir a maneira mínima (em termos do número de operações realizadas) de reorganizar a pirâmide a partir do número de discos fornecido.
Exemplos
| # |
Entrada |
Saída |
| 1 |
2 |
1 1 2
2 1 3
1 2 3
|
Запрещенные операторы: for; while; until