TORRE DEHANÓI

, Juliana Marianna e Rafael18/03/2011

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 sobreuma 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.

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)

=>

=> =>

=> => => =>

NÚMERO DE MOVIMENTOS MÍNIMO

2n-14 discos => 15 movimentos

7 discos => 127 movimentos

15 discos => 32.767 movimentos

64 discos (de Brahma) => 18.446.744.073.709.551.615 movimentos.

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)

ANÁLISE DE COMPLEXIDADE

Quando n>0

T(n) = 4+2T(n-1)

Quando n=0

T(n) = 1

ANÁLISE DE COMPLEXIDADE

Na 1ª iteraçãoT(n) = 4+2T(n-1)

Na 2ª iteraçãoT(n) = 4+2(4)+4T(n-2)

Na 3ª iteraçãoT(n) = 4+2(4)+4(4)+8T(n-3)

Na 4ª iteraçãoT(n) = 4+2(4)+4(4)+8(4)+16T(n-4)

E na k-ésima iteração?E na k-ésima iteração?

ANÁLISE DE COMPLEXIDADE

Na k-ésima iteração:Na k-ésima iteração:

T n=4214 22423424T n−k

44 21222324...2∞T n−k

PG: PG: 21222324 ...2∞

Soma da Soma da PG:PG: S k=

a1∗qn−1

q−1

S k=2∗2n−12−1

S k=2n1−2

ANÁLISE DE COMPLEXIDADE

Condição de parada: Condição de parada:

n-k = 0

n=k

Substituindo:Substituindo:

t n =44∗S kt n−k t n =44∗2n1−21t n =44∗2n1−81t n =2n3−3 ou 2n∗8−3

ANÁLISE DE COMPLEXIDADE

A pergunta que não quer calar...

O algoritmo da Torre de Hanoi é:O algoritmo da Torre de Hanoi é:

O2n

E este é o fim!

OBRIGADO.