Algoritmos e Estruturas de Dados

Torres de Hanói

Um vídeo de Reducible – Towers of Hanoi: A Complete Recursive Visualization

Dadas 3 hastes (esquerda – 1, do meio – 2 e direita – 3), há n discos redondos de tamanhos diferentes na primeira haste. Os discos estão dispostos em ordem crescente de tamanho, de cima para baixo. É permitido mover o disco que está no topo de uma haste para o topo de outra haste, desde que seja colocado sobre um disco maior. Ou seja, não é permitido colocar um disco maior em cima de um disco menor.

O objetivo é listar todas as operações que levam à transferência de todos os discos da primeira haste para a terceira, usando o menor número possível de movimentos.

Entrada

A entrada contém um único inteiro n (1 ≤ n ≤ 16), que representa o número de discos na primeira haste.

Saída

O programa deve imprimir todas as operações necessárias para mover todos os discos da primeira haste para a terceira, garantindo que em cada haste os discos menores fiquem sempre por cima dos maiores. A saída não deve ultrapassar operações.

Exemplos

Entrada

Saída

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

To check your solution you need to sign in
Sign in to continue