Torres de Hanoi
Estrutura de Dados
Marco Antonio Montebello Júnior
[email protected]
Torres de Hanoi
“No século XIX, um jogo chamado Torres de Hanoi
apareceu na Europa, junto com um material
promocional explicando que o jogo representava
uma tarefa conduzida no Templo de Brahma
(montanhas de Hanoi – sacerdotes brâmanes).
Dizia, ainda, que na criação do mundo, aos
sacerdotes foi dada uma plataforma de metal na
qual existiam três hastes de diamante.
Estrutura de Dados
Torres de Hanoi
Na primeira haste existiam 64 discos de ouro, cada
um ligeiramente menor em relação ao que estava
por cima. (A versão mais exótica vendida na época
na Europa tinha 8 (oito) discos e 3 (três) hastes de
madeira).
Estrutura de Dados
Torres de Hanoi
Os sacerdotes foram incumbidos com a tarefa de
mover todos os discos de ouro do primeiro disco
para o terceiro, porém, com as seguintes
condições:
a. Mover apenas um disco por vez;
b. E nenhum disco poderia ficar sobre um
disco menor.
Estrutura de Dados
Torres de Hanoi
Entretanto, poderiam utilizar qualquer haste de
diamante como descanso para os discos.
Aos sacerdotes foi dito que quando eles
terminassem de movimentar os 64 discos de ouro,
significaria o fim do mundo!!!”
Estrutura de Dados
Torres de Hanoi
Estrutura de Dados
Desenvolvendo uma solução
para Torres de Hanoi






Concentrar nossa atenção não no primeiro passo
Mas sim, no passo mais difícil: mover o último
disco
Como acessar o disco número 64?
Lembre-se que somente um disco pode ser
movido por vez
E o último (o maior) não pode nunca estar sobre
os demais
Quando movemos o disco 1, não pode existir
nenhum outro disco nas torres 1 e 3
Estrutura de Dados
Resumindo os passos do
algoritmo de Torres de Hanoi

Move (63, 1, 2, 3)

Move 63 discos da torre 1 para 2 (torre 3 temporária)

Escreva: “Mova o disco número 64 da torre 1
para torre 3”

Move (63, 2, 3, 1)

Move 63 discos da torre 2 para torre 3 (torre 1
temporária)
Estrutura de Dados
Refinamento

Para escrever o algoritmo na sua forma final,
nós devemos saber em cada passo, qual torre
será utilizada como armazenamento
temporário, e assim, nós construímos a função
“move” com as seguintes especificações:

void move(int qtd, int inicio, int fim, int aux)
 Pré-condição: Existe no mínimo qtd discos na torre inicio. O disco
de topo (se existir) nas torres aux e fim, é maior do que qualquer
outros qtd discos presentes na torre inicio.
 Pós-Condições: Os qtd discos que estavam na torre inicio foram
movidos para a torre fim. A torre temp (usada como armazenamento
temporário) retornou para sua posição inicial.
Estrutura de Dados
Refinamento

Nossa tarefa deve terminar num número finito de
passos.

Uma regra óbvia é que, quando não existir mais
discos para ser movido, não há mais nada para
fazer...
Estrutura de Dados
Analisando um programa que
considera as regras anteriores
#define discos = 64; //faça essa constante ser menor para testar o programa
/*
Pré: Nenhum
Pós: A simulação das torres de Hanoi terminou
*/
void move(int qtd, int inicio, int fim, int aux);
main()
{
move (discos, 1, 3, 2);
}
void move(int qtd, int inicio, int fim, int aux)
{
if(qtd > 0)
{
move(qtd – 1, inicio, aux, fim);
printf(“Mova disco %i de %i para %i”, qtd, inicio, fim);
move(qtd - 1, aux, fim, inicio);
}
}
Estrutura de Dados
Acompanhamento / Análise

Acompanhamento e análise do programa
recursivo de Torres de Hanói com árvore de
recursão.

Demonstração:

move(3, 1, 3, 2);
Estrutura de Dados
Analisando a árvore de recursão

Uma instrução é exibida para cada vértice (ou
nó)

Exceto para as folhas que são chamadas com
count == 0

O número de vértices tipo não-folhas é:

1 + 2 + 4 +...+ 263 = 20 + 21 + 22+ . . . + 263 = 264 –1
Estrutura de Dados
Podemos concluir o seguinte


Número de movimentos para movimentar todos 64
discos é de: 264 -1
Este valor pode ser estimado por:


Número aproximado de movimentos é:






103 = 1000  1024 = 210
264 = 24 x 260  24 x 1018 = 1,6x1019
Existem aproximadamente 3,2x107 segundos num ano
Suponha instruções num ritmo de um movimento por
segundo
A tarefa total levará quase 5x1011 anos
Estimativa de vida do universo: mínimo 20 bilhões
(2x1010) anos
Duração do mundo: 25 vezes mais do que já tem!!!
Estrutura de Dados
Consideração de tempo (execução) e espaço
(memória) do algoritmo recursivo de Torres de
Hanoi





Não existiria um computador que rodaria o
programa de Torres de Hanoi
Ele falharia por falta de tempo
Mas certamente não por falta de espaço
O espaço necessário é somente para fazer o
controle das 64 chamadas recursivas
Mas o tempo necessário requerido, é aquele
para fazer 264 cálculos
Estrutura de Dados
Desenvolvendo algoritmos
recursivos

Ache o passo chave



Ache uma regra de parada



Como este problema pode ser dividido?
Como posso desenvolver o passo chave da solução?
Uma regra de parada indica que o problema ou uma parte
razoável do mesmo foi feito
Ela é geralmente pequena e dá a solução trivial, sem a
necessidade da recursão
Monte seu algoritmo

Combine a regra de parada e o “passo chave” usando uma
instrução if
Estrutura de Dados
Desenvolvendo algoritmos
recursivos

Verifique o término




Certificar que a recursão sempre terminará
Comece com uma situação geral
Verifique se num número finito de passos, a regra de
parada será satisfeita e a recursão termina
Desenhe uma árvore de recursão

É a ferramenta chave para analisar algoritmos
recursivos
Estrutura de Dados
Tipos de recursividade
Recursão de Cauda



Essa situação na qual a chamada recursiva é o
último comando da função, é denominada
recursão de cauda
Isso forma um “looping” que será repetido até
que uma condição de parada seja satisfeita
A recursão de cauda pode sofrer transformações
até ser obtida uma estrutura de interação,
quando observaremos ganhos em tempo e
espaço
Estrutura de Dados
Exemplo
Fatorial
/*
Fatorial : versão recursiva
Pós
: n é um inteiro não negativo
Pré
: retorna o valor do fatorial de n
*/
int fatorial(int n)
{
if (n == 0)
return 1;
else
return n*fatorial(n-1);
}
/*
fatorial : versão interativa
Pós
: n é um inteiro não negativo
Pré
: retorna o valor do fatorial de n
*/
int fatorial(int n)
{
int count, product = 1;
for(count = 1; count < = n; count ++)
product*= count;
return product;
}
Estrutura de Dados
Considerando os exemplos
anteriores


Qual dos programas usa menos espaço de memória?
Acompanhe a execução recursiva para n = 5
fatorial(5)
= 5*fatorial(4)
= 5*(4*fatorial(3))
= 5*(4*(3*fatoriall(2)))
= 5*(4*(3*(2*fatorial(1))))
= 5*(4*(3*(2*(1*(fatorial(0))))))
= 5*(4*(3*(2*(1*))))
= 5*(4*(3*(2*1)))
= 5*(4*(3*2))
= 5*(4*6)
= 5*24
= 120
Estrutura de Dados
Diretrizes e conclusões gerais




A árvore de recursão é uma boa possibilidade para
ajudar a decisão entre utilizar um algoritmo recursivo e
não recursivo
Se ela tiver uma forma simples, a versão interativa pode
ser melhor
Se ela envolver tarefas de duplicação, outras estruturas
que não sejam pilhas poderão ser mais apropriadas,
então a necessidade de recursão pode desaparecer
Se a árvore de recursão parece ser consistente, com
poucas tarefas de duplicação, então a recursão pode
ser o método mais natural
Estrutura de Dados
Ainda mais...




A recursão é considerada uma abordagem topdown para resolver um problema
A interação está mais para um abordagem
bottom-up
É sempre verdadeiro que a recursão pode ser
substituída pela interação e pilhas
É verdade também, por outro lado, que qualquer
programa interativo que manipula uma pilha
pode ser substituído por um programa recursivo
sem nenhuma pilha
Estrutura de Dados
Mensagem sobre a utilização da
recursão

“Um programador cuidadoso deve não somente
perguntar, se a recursão deve ser removida, mas
também perguntar, quando um programa usa
pilhas, se a introdução da recursão poderia
produzir um programa mais natural e de melhor
entendimento, agregando melhorias na
abordagem e nos resultados do problema”
Estrutura de Dados