Torre
de Hanói
História
• A torre de Hanói, também conhecida por
torre do bramanismo ou quebra-cabeças do
fim do mundo, foi publicada em 1883 pelo
matemático Frances Edouard Lucas, com o
pseudônimo Prof. N. Claus (de Siam), um
anagrama de seu nome.
• A publicação dizia que o jogo vinha do Vietnã,
sendo popular também na China e no Japão, e
acompanhava a caixa do quebra-cabeças.
Edouard Lucas teve inspiração de uma lenda
para construir o jogo das Torres de Hanói. Já
seu nome foi inspirado na torre símbolo da
cidade de Hanói,
O que é Torre de Hanói?
• é um quebra-cabeça que consiste em uma base
contendo três pinos, em um dos quais são
dispostos alguns 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. O número de discos pode
variar sendo que o mais simples contém apenas
três.
Soluções
• É 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
• Para solucionar um Hanói de 7 discos, são
necessários 127 movimentos.
• A solução para o problema da Torre de Hanói com
recursividade é compacta e baseia-se no seguinte:
•
a) A única operação possível de ser executada é "move
disco de um pino para outro";
•
b) Uma torre com (N) discos, em um pino, pode ser
reduzido ao disco de baixo e a torre de cima com (N-1) discos;
•
c) A solução consiste em transferir a torre com (N-1) discos
do pino origem para o pino auxiliar, mover o disco de baixo do
pino origem para o pino destino e transferir a torre com (N-1)
discos do pino auxiliar para o pino destino. Como a
transferência da torre de cima não é uma operação possível
de ser executada, ela deverá ser reduzida sucessivamente até
transformar-se em um movimento de disco.
Aplicação Prática
• A Torre de Hanói pode ser trabalhada em níveis de
desenvolvimento com crianças. Na pré-escola, com regras
simples de separação de cores e tamanhos, a torre de
Hanoi ajuda em questões de coordenação motora,
identificação de formas, ordem crescente e decrescente,
entre outras formas de aprendizado.
• De uma maneira mais ampla, o jogo pode ser usado para o
estabelecimento de estratégias de transferência das peças,
como a contagem dos movimentos e raciocínio.
• Iniciando com um número menor de peças, ou seja,
resolvendo problemas mais simples, teremos oportunidade
de experimentar uma das mais importantes formas de
raciocínio matemático.
• Vantagens
• Algoritmos recursivos são mais compactos para
esse tipo de algoritmo, mais legíveis e mais fáceis
de serem compreendidos. Além da facilidade de
serem implementados em linguagens de
programação.
• Desvantagens
• Por usarem intensivamente a pilha, os algoritmos
recursivos tendem a ser mais lentos que os
iterativos, porém pode valer a pena sacrificar a
eficiência em benefício da clareza.
Conclusão
• A Torre de Hanoi consiste em passar todos os discos de uma extremidade
a outra sem que um disco maior fique em cima de um menor.
• As suas aplicações são basicamente usadas em escolas para que os
professores possam melhorar e desenvolver o cognitivo das crianças, além
do trabalho em grupo. Sendo este aplicado em pequenos grupos ou
individualmente.
• A Torre de Hanói possui várias formas de resolução. Uma delas é a
resolução recursiva a qual podemos dizer que é a mais limitada quanto ao
tempo de realização, já que sua execução dependerá de alguns fatores
para tornar-se mais eficaz.
• A resolução Iterativa utiliza alguns ciclos (estruturas) de repetição que
podem ser chamados de laços, existe ainda a possibilidade de algumas
estruturas adicionais (mais complexas) as quais tornam o algoritmo mais
rápido.
• É fato que todo algoritmo recursivo possuí um algoritmo iterativo
equivalente; Dependendo apenas da sua complexidade de construção.
•
•
•
•
Alunas : Isabella , Jaine, Mariângela
Números: 09, 13 e 27
1 ano “ B “
Professor: Cleber