Algoritmos Recursivos - Torre de Hanoi

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
*
*
Algoritmos Recursivos 
(Segunda Aula) 
Prof. Dr. Marco Antônio Piteri
Kátia Martins Gonçalves
Rosemeire Bonfim de Almeida
*
*
*
Torre de Hanoi
Pino 1
Pino 2
Pino 3
Um pouco de história, ...
*
*
*
Torre de Hanoi
Pino 1
Pino 2
Pino 3
*
*
*
Torre de Hanoi
PROBLEMA ORIGINAL: Mover os 64 discos de diferentes diâmetros colocados inicialmente no Pino 1 para o Pino 3, obedecendo as seguintes regras:
Regra 1: Somente um disco pode ser movido por vez para um outro pino;
Regra 2: Nenhum disco de diâmetro maior pode ser colocado sobre um outro disco de diâmetro menor;
*
*
*
Torre de Hanoi
NOSSO OBJETIVO: Elaborar um algoritmo que seja capaz de enumerar (listar) a seqüência correta de movimentos para resolver o problema:
ESSE É UM EXEMPLO CLÁSSICO DE COMO PODEMOS ENCONTRAR UMA SOLUÇÃO RECURSIVA PARA UM PROBLEMA APARENTEMENTE COMPLEXO DE FORMA ELEGANTE E COMPACTA.
*
*
*
Torre de Hanoi
SOLUÇÃO: Vamos imaginar que desejamos mover n discos do Pino 1 para o Pino 3, usando o Pino 2 como temporário e vamos admitir que esta tarefa seja realizada pela função Mova_Discos(.) e seus respectivos parâmetros, ou seja. 
		Mova_Discos(N, P1, P2, P3), onde:
N : denota o número de discos a serem movidos;
P1 : denota o pino onde estão os discos inicialmente;
P2 : denota o pino de destino dos discos;
P3 : denota o pino auxiliar/temporário;
*
*
*
Torre de Hanoi
Logo, qual o significado da instrução Mova_Discos(3,1,3,2) ?
Desejamos mover 3 discos inicialmente colocados no Pino 1 para o Pino 3, usando o Pino 2 como auxiliar. 
Pensando recursivamente, podemos observar que a tarefa de mover n discos inicialmente colocados no Pino 1 para o Pino 3, usando o Pino 2 dado pela instrução 
Mova_Discos(n,1,3,2) é eqüivalente as seguintes subtarefas:
*
*
*
Torre de Hanoi
Mova_Discos(n,1,3,2) =
Mova_Discos(n-1,1,2,3) 
Mova_Discos(n-1,2,3,1) 
Mover o disco da base do Pino 1 para o Pino 3
Por sua vez, a idéia acima de decompor o problema original em instâncias menores do mesmo problema (recursão) pode ser repetida assim:
*
*
*
Torre de Hanoi
Mova_Discos(n-1,1,2,3) =
Mova_Discos(n-2,1,3,2) 
Mova_Discos(n-2,3,2,1) 
Mover o disco da base do Pino 1 para o Pino 2
..., o processo continua enquanto o número de disco n ≥ 1. Quando restar um único disco em um Pino (ele será o de menor diâmetro) e assim, poderá ser movido para o Pino de destino.
*
*
*
Torre de Hanoi
Assim, a solução do problema da Torre de Hanoi que consiste em mover n discos do Pino 1 para Pino 3, pode ser colocada recursivamente em termos algorítmicos da seguinte forma: 
printf(“\n %d ---> %d”, P1, P2);
void Hanoi(int N, int P1, int P2, int P3){
} //Hanoi
if(N > 0){
}
Hanoi(N-1, P1, P3, P2);
Hanoi(N-1, P3, P2, P1);
*
*
*
MD(3,1,3,2)
Estrutura da árvore representando a ordem das chamadas recursivas, os respectivos parâmetros e a ordem do movimentos para o problema da Torre de Hanoi.
MD(2,1,2,3)
MD(1,1,3,2)
MD(1,3,2,1)
MD(2,2,3,1)
1
2
3
4
1 → 3
1 → 2
3 → 2
1 → 3
MD(1,2,1,3)
MD(1,1,3,2)
5
6
7
2 → 1
2 → 3
1 → 3
Seqüência
1 → 3
1 → 2
3 → 2
1 → 3
2 → 1
2 → 3
1 → 3
*
*
*
Torre de Hanoi: O número de movimentos para n discos é dado por 2n - 1.
Pino 1
Pino 2
Pino 3
Discos
Movimento 1
Movimento 2
Movimento 3
Movimento 4
Movimento 5
Movimento 6
Movimento 7
1 → 3
1 → 2
3 → 2
1 → 3
2 → 1
2 → 3
1 → 3
*
*
*
Torre de Hanoi: O número de movimentos para n discos é dado por 2n - 1. Pode ser mostrado que esse número é mínimo.
Vamos admitir que C(n) seja o número de movimentos para resolver o problema para n discos e que desejamos movimentar os n discos do Pino 1 para o Pino 3.
Logo, devemos movimentar (n-1) discos do Pino 1 para o Pino 2, em seguida mover o último disco do Pino 1 para o Pino 3 (diâmetro maior), e na seqüência movimentar os (n-1) discos do Pino 2 para o Pino 3.
A partir da descrição acima, podemos deduzir a relação de recorrência 
C(n) = 
1 se n = 1 (condição inicial)
2C(n-1) +1 se n > 1 
*
*
*
Vamos encontrar uma fórmula explícita para a relação C(n) = 2C(n-1) +1 de modo a quantificar de forma mais clara o número de movimentos.
C(n) = 2C(n-1) + 1
= 2(2(C(n-2) + 1) + 1
...
= 23 ·C(n-3) + 22 + 2 + 1 
= 2n-1.C(1) + 2n-2 + 2n-3 + …+ 22 + 2 + 1
= 22C(n-2) + 2 + 1
= 23 ·(2C(n-4) + 1) +22 + 2+ 1 
= 22 ·(2C(n-3)+1) + 2 + 1 
= 24 ·C(n-4) + 23 +22 + 2+ 1 
= 2n-1 + 2n-2 + 2n-3 + …+ 22 + 2 + 1
*
*
*
Levando em consideração que a =1 e r = 2, concluímos que:
Sabemos que Soma Geométrica ar0 + ar1 + ar2 + ar3 +…+ arn, (0 < r ≠ 1) é dada por
Onde r é razão entre dois termos consecutivos quaisquer, ou seja, 
2n-1 + 2n-2 + 2n-3 + …+ 22 + 2 + 1 = 2n - 1
C(n) = 2n - 1
*
*
*
CURIOSIDADES
Como os monges sabiam que o mundo iria acabar? Nas condições do enunciado.
C(n) = 264 -1 = 18.446.774,073.709.551.615
Vamos assumir que um computador possa realizar 1 bilhão (109) de movimentos por segundo e que o ano tenha 365 dias. Nestas condições o computador levaria 584,94241735507203... anos para realizar todos os movimentos. 
Agora vamos assumir que os monges com toda aquela serenidade conseguissem realizar um movimento em cada microsegundo (10-6). Nestas condições, quantos anos eles levariam para realizar todos os movimentos. Façam as contas!!! (Resposta: mais de 5.000 anos)
*
*
*
CONCLUSÃO
Podemos dormir tranqüilos por um bom tempo!!! 
FIM!!!