Torre de Hanoi

1. TORREDE
HANÓI
,
Juliana Marianna e Rafael
18/03/2011

2. ORIGEM
Criador: Edouard Lucas.
Motivo do nome: inspirado na torre símbolo da
cidade de Hanói, no Vietnã.
Lenda sobre a origem (mais conhecida): há
um templo Hindu no centro do universo. Nesse
Templo, Brahma criou uma torre com 64 discos
de ouro e mais duas estacas equilibradas sobre
uma plataforma. Se as ordens e instruções
dadas por Brahma para essa construção forem
cumpridas, o templo irá se desmoronar e o
mundo desaparecer.

3. SOLUÇÃO
É preciso diminuir a complexidade da torre para movê-la da
melhor maneira (mínimo de movimentos) possível.
EXEMPLO PRÁTICO, COM 4 DISCOS:
1º disco => 1 movimento.
Torre do 1º e 2º disco (sendo que o primeiro já foi movido) => 2 movimentos.
Torre do 1º, 2º e 3º (sempre leva em conta a formação anterior) => 4 movimentos.
E assim se sucede até o último disco, numa PG: (1,2,4,8...2n)
=>
=> =>
=> => => =>

4. NÚMERO DE MOVIMENTOS MÍNIMO
2
n
-1
4 discos => 15 movimentos
7 discos => 127 movimentos
15 discos => 32.767 movimentos
64 discos (de Brahma) => 18.446.744.073.709.551.615 movimentos.

5. RESOLUÇÃO ALGORÍTMICA RECURSIVA
Hanoi (n, origem, destino, auxiliar)
Inicio
Se n>0 então
Hanoi (n-1, origem, auxiliar, destino)
destino = origem
Hanoi (n-1, auxiliar, destino, origem)
Fim-se
Fim
11
1+T(n-1)1+T(n-1)
11
1+T(n-1)1+T(n-1)

6. ANÁLISE DE COMPLEXIDADE
Quando n>0
T(n) = 4+2T(n-1)
Quando n=0
T(n) = 1

7. ANÁLISE DE COMPLEXIDADE
Na 1ª iteração
T(n) = 4+2T(n-1)
Na 2ª iteração
T(n) = 4+2(4)+4T(n-2)
Na 3ª iteração
T(n) = 4+2(4)+4(4)+8T(n-3)
Na 4ª iteração
T(n) = 4+2(4)+4(4)+8(4)+16T(n-4)
E na k-ésima iteração?E na k-ésima iteração?

8. ANÁLISE DE COMPLEXIDADE
Na k-ésima iteração:Na k-ésima iteração:
Tn=42
1
42
2
42
3
42
4
Tn−k
442
1
2
2
2
3
2
4
...2
∞
Tn−k
PG: PG: 2
1
2
2
2
3
2
4
...2
∞
Soma da Soma da
PG:PG:
S
k=
a
1
∗q
n
−1
q−1
S
k=
2∗2
n
−1
2−1
S
k=2
n1
−2

9. ANÁLISE DE COMPLEXIDADE
Condição de parada: Condição de parada:
n-k = 0
n=k
Substituindo:Substituindo:
tn=44∗S
k
tn−k
tn=44∗2
n1
−21
tn=44∗2
n1
−81
tn=2
n3
−3ou2
n
∗8−3

10. ANÁLISE DE COMPLEXIDADE
A pergunta que não quer calar...
O algoritmo da Torre de Hanoi é:O algoritmo da Torre de Hanoi é:
O2
n


11. E este é o fim!
OBRIGADO.