O jogo torre de Hanoi

Prévia do material em texto

Nome do/a aluno/a: Débora Oliveira Ramos 
Curso: Ciência da Computação 
Disciplina: Matemática Fundamental 
Professor: Vanessa da Luz Vieira 
 
 
O jogo torre de Hanói, também conhecida como torre de bramanismo foi 
 inventada em 1883 pelo matemático Edouard Lucas. 
A principal proposta do jogo é de transferir os discos de uma haste A para haste 
C, sendo eles empilhados de forma decrescente de tamanho com a menor quantidade 
de movimentos possível, contando com o auxílio de uma haste B para realização dos 
movimentos. 
O jogo possui apenas duas regras, onde a primeira é que somente um disco 
pode ser movido por vez e a segunda é que um disco maior nunca pode sobrepor um 
disco menor. 
Para sabermos quantos movimentos mínimos são necessários para realizar o 
jogo utilizamos o seguinte raciocínio: uma torre pode conter no mínimo 1 disco e o 
máximo de N discos (1,2,3,4,5...N), sabemos que para finalizar um jogo contendo 1 
disco apenas, precisamos de 1 único movimento, então para movermos N discos 
precisaremos remover os demais discos anteriores a N, ou seja , se tivermos 7 discos, 
precisamos remover 6 para mover então o 7º para a haste C e concluir o jogo, 
conforme a regra. Sabendo disso podemos utilizar a equação exponencial para 
calcularmos o número de movimentos mínimos para determinados números de 
discos. 
Vamos imaginar que temos N discos para mover, logo teremos que remover o 
disco anterior a N, ou seja N-1, após movermos todos os discos anteriores a N, 
movemos N para haste C e em seguida precisamos mover novamente para N os 
discos que o antecediam, ou seja (N-1)(N+1), sendo assim para termos a formulo para 
encontrar o número de movimentos exatos utilizaremos T como o número de 
movimentos, sendo T(2n-1) , veja a figura abaixo: 
 
 
 
 
 
 
 
 
 
 
 
Conforme a figura, temos 2 discos, podemos calcular o número mínimo de 
movimentos já ao observarmos as figuras, mas vamos aplicar a formula T(2n-1), 
substituiremos N pelo número de discos, portanto ficará T(22-1), T=3, ou seja, para 2 
discos temos 3 movimentos mínimos, fazendo o cálculo com 3, 4, 5, 6 e 7 discos 
temos os respectivos resultados: 
 
3 discos: T(23 - 1) → T(8-1) → T=7 
4 discos: T(24 - 1) → T(16-1) → T=15 
5 discos: T(25 - 1) → T(32-1) → T=31 
6 discos: T(26 - 1) → T(64-1) → T=63 
7 discos: T(27 - 1) → T(128-1) → T=127 
Assim, podemos descobrir a quantidade mínima necessária de movimentos de 
qualquer quantidade de discos desejáveis. 
 
 
 
Referências Bibliográficas 
https://www.aedi.ufpa.br/bom/images/pdf/hanoi.pdf