Torre de Hanói, entenda a lógica e aprenda a solução

Solução de uma Torre de Hanói de 4 Discos

É interessante observar que o número mínimo de “movimentos” para conseguir transferir todos os discos da primeira estaca à terceira é 2n-1, sendo n o número de discos. Logo: Para solucionar um Hanói de 3 discos, são necessários 2³ -1 movimentos = 7 movimentos

Para solucionar um Hanói de 7 discos, são necessários 127 movimentos

Para solucionar um Hanói de 15 discos, são necessários 32.767 movimentos

Para solucionar um Hanói de 64 discos, como diz a lenda, são necessários 18.446.744.073.709.551.615 movimentos.

Para entender a lógica da Torre de Hanói é necessário analisar a construção de diferentes níveis da torre com o número mínimo de movimentos, tendo o nível anterior já formado, sendo que esses níveis são o número de peças desintegradas da torre original que irão formar outra torre com os menores discos.

Para mover o primeiro disco da torre original, 1 movimento é gasto. Para mover o segundo da torre original, sendo que o primeiro já foi movido e será construída uma torre com os 2 menores discos, são gastos 2 movimentos. Para deslocar o terceiro disco formando nova torre com os três menores discos, tendo a torre com os dois menores já formada, são gastos 4 movimentos.

Assim se sucede com os próximos discos até que o enésimo disco (o último) seja deslocado compondo uma torre com os outros discos tendo uma torre com o penúltimo disco e os demais juntos já formada. A sucessão formada pela soma dos movimentos é uma sucessão (1,2,4,8…2n)

A fórmula 2n – 1 é provinda da soma de uma progressão geométrica.

Sabe-se que em uma progressão geométrica a soma de seus termos equivale a [a * (qn – 1)] / q – 1, onde “a” é o primeiro termo e “q” é a razão.

Já que a razão é 2 e o primeiro termo é 1 temos que [a * (qn – 1)] / q – 1 = [1 * (2n – 1)] / 2 – 1 = 2n – 1

Visite nosso site e adquira já o seu!

Torre de Hanói nas Lojas Wessel, clique aqui.