Torre de Hanoi
A Torre de Hanói (também conhecida como O Problema do Templo de Benares, Torre de Brahma, Torre de Lucas, ou simplesmente quebra-cabeças de pirâmide) é um jogo matemático composto por três hastes e discos de vários tamanhos que podem deslizar sobre qualquer haste.
Um determinado número de discos (feitos de madeira) é colocado numa das hastes, o que determina a complexidade da solução.
Os discos são colocados numa haste em ordem decrescente de tamanho, com o menor no topo, para se aproximar de uma forma cónica. O objetivo do quebra-cabeças é levar a pilha completa para outra haste, seguindo as instruções abaixo:
- Num movimento, apenas um disco pode ser transferido.
- Cada movimento envolve remover o disco superior de uma das pilhas e colocá-lo em cima de outra pilha ou de uma haste vazia.
- Um disco maior não pode ser colocado em cima de um menor.
Componentes:
- Três hastes
- Conjunto de discos com tamanhos diferentes
Princípio de funcionamento:
A Torre de Hanói é um excelente exemplo de um problema recursivo.
Vamos ver como resolver.
n = 1
Se tivermos apenas 1 disco, é muito fácil, basta movê-lo uma vez e acabou.
n = 2
Se tiver 2 discos, então precisa de mover o de cima para a haste 2, depois o de baixo para a haste 3 e só então mover o menor da haste 2 para a haste 3. Isso leva 3 movimentos no total.
n = 3
Se aplicar a mesma lógica de antes, notará que para mover o disco inferior para a haste 2, primeiro precisa de mover os outros dois para a haste 3, mover o 3o disco para a haste 2 e só depois mover os dois discos da haste 3 para a haste 2, repetindo o processo para n= 2, o que significa que você teve que mover 2 peças duas vezes repetindo exatamente o mesmo procedimento.
O quebra-cabeça pode ser resolvido em 7 passos com 3 discos.
n = 4
Novamente, repetindo a lógica, para 4 peças, deve repetir todas as etapas necessárias para a etapa 3 duas vezes. Isso significa que para cada disco que se adiciona, tem que dobrar todas as etapas necessárias.
O quebra-cabeça pode ser resolvido em 15 etapas com 4 discos.
Para n discos:
2n-1 é o menor número de movimentos necessários para resolver um quebra-cabeça da Torre de Hanói, sendo n o número total de discos.
Instruções:
- Comece com 5 discos na haste 1 colocados corretamente do maior para o menor, de modo que o maior fique na parte inferior e o menor no topo.
- Mova uma peça de cada vez para outra haste, certificando-se de nunca colocar um disco maior em cima de um menor.
- Mova todos os discos da haste 1 para a haste 2.
- Quantos movimentos fez?
- Qual é o número mínimo de movimentos necessários para resolver o quebra-cabeça com 5 discos?
Links:
Towers of Hanoi (article) | Algorithms | Khan Academy