Torre da Hanói, qual a solução vencedora tendo N discos?

Question

Quantos movimentos são precisos tendo N discos?

A Torre de Hanoi é um quebra-cabeça criado pelo matemático francês Edouard Lucas em 1883 que consiste em uma base contendo três pinos, onde em um deles, são dispostos sete discos uns sobre os outros, em ordem crescente de diâmetro, de cima para baixo. O problema consiste em passar todos os discos de um pino para outro qualquer, usando um dos pinos como auxiliar, de maneira que um disco maior nunca fique em cima de outro menor em nenhuma situação.

Answer 1

Resposta: 2^n -1 (2 elevado a n-ésima potência menos 1).

Explicação:

A melhor forma de pensar na solução é recursivamente:

Problema inicial:
Dadas 3 pilhas, A, B e C, mover N discos de A para B, usando C como auxiliar.

Solução recursiva:
1) Mover N-1 discos de A para C, usando B como auxiliar
2) Mover o disco maior de A para B
3) Mover N-1 discos de C para B, usando A como auxiliar

Os sub-problemas (1) e (3) podem não ser elementares, mas são idênticos ao problema inicial e também mais simples, uma vez que o número de discos a mover é menor. A mesma solução pode ser recursivamente aplicada aos sub-problemas até que os mesmos se tornem elementares, ou seja, quando o número de disco a mover for 1 (um).

Para chegar à fórmula, faça o caminho oposto:
• O problema mais simples, com 1 disco, requer 1 movimento.
• O problema mais complexo seguinte requer o dobro (há 2 sub-problemas) do anterior mais 1
• Segue tabela:
N N° de movimentos da solução
1     1 = 1 = 2^1 - 1
2     2x1 + 1 = 3 = 2^2 -1
3     2x(2x1 + 1) + 1 = 7 = 2^3 -1
...        ...
n-1  2^(n-1)-1
n     2x(2^(n-1)-1)+1 = 2^n-1

Answer 2

a resposta é a que a disseram acima (2^n)-1

Answer 3

Para 1 disco, é necessário 1 movimento
Para 2 discos, são necessários 3 movimentos
Para 3 discos, são necessários 7 movimentos
Para 4 discos, são necessários 15 movimentos
Para 5 discos, são necessários 31 movimentos

Observa-se q há uma regra, ou seja, sempre elevado ao numero de discos menos uma unidade. Então podemos dizer que para n discos, esse valor será de:

(2^n) - 1