Bem Vindo(a) !
Nós temos 1 estudante onlineCursos e Treinamentos
Instituições de Ensino
Login
A torre de hanoi 
A torre de Hanoi é um interessante jogo cujo objetivo é: transportar todos os discos de um extremo a outro do conjunto de hastes verticais, obedecendo as seguintes regras: #1 - Mover um disco por vez e sempre o que estiver no topo da "pilha" #2 - Jamais "empilhar" um disco maior sobre um menor Antes de escrevermos mais sobre esse interessante jogo e a interessante lenda, que o envolve, proponho o seguinte desafio: Quantas são as possíveis configurações (de acordo com as regras) de uma torre de Hanoi composta por 4(quatro) discos e 3(três) hastes verticais? Antes da solução, a lenda! Diz a lenda que, em algum lugar nas selvas da Índia há um mosteiro que guarda uma torre de hanoi com 64 discos de ouro. Desde a sua montagem inicial (todos os discos em uma das hastes laterais) os monges seguem o ritual sagrado de transpor todos os discos de um extremo ao outro da torre, seguindo as regras de movimentação. Por que sagrado? Porque ao terminar acontecerá um ruidoso trovão anunciando o fim do mundo! Quanto tempo isso significa? Vamos admitir que os monges sejam rápidos e demoram apenas 1 segundo para transpor cada disco de uma posição à outra. Em acordo com a conhecida expressão que dá o número mínimo (N) de movimentos para transpora quantidade todal de discos(d) a torre de um extremo à outro: N = 2^d -1 Essa expressão pode ser obtida por indução. Verifique os casos para 1, 2, 3 discos e verifique o padrão! temos: t = 1.8446744 x 10^19 segundos o que corresponde a, aproximadamente, t =585 bilhões de anos! Um intervalo de tempo muito maior que o tempo de vida de nosso Sol! Ou seja, um intervalo de tempo maior que o de vida de nosso sistema solar tal qual o conhecemos, logo, não será o trabalho dos monges a causa do fim do mundo.Ufa! Finalmente, respondendo a pergunta inicial do desafio, o número de posições distintas em uma torre de hanoi com 3 hastes e 4 discos é: 45 A contagem, considerando que todos os discos iniciam em uma das hastes localizadas nas extremidades (haste A), é ilustrada na figura abaixo. Na contagem, numeramos os discos de 1 a 4, sendo 4 o maior deles. Assim, quanto maior o número, maior o disco. O ordenamento dos discos é realizado de baixo para cima, dessa forma o primeiro número da sequência indica o disco que inicia a pilha de baixo para cima. Já a hastes recebem as letras "A", "B" e "C" como nome, estando A e C nas extremidades. 
Como são três hastes, basta multiplicar esse resultado parcial por 3. Note que é justamente o triplo do número mínimo de movimentos para se chegar a solução! (com todos os discos inicialmente em uma das hastes laterais). Novamente, esse resultado pode ser obtido por indução ;-) Enquanto o fim do mundo não vem, que tal exercitar a mente (se divertir!) com a torre de hanoi? Bom divertimento! |