Deprecated: Function eregi() is deprecated in /home/ckirner/public_html/realidadevirtual/cmsimple/cms.php on line 41
Realidade Virtual e Aumentada - Tempo de Execução
Realidade Virtual e Aumentada
ENTRADA >   APLICAÇÕES > Torre de Hanoi > Tempo de Execução

Tempo de Execução

Torre de Hanoi

(Hanoi Tower)

Tempo de Execução do Algoritmo da Torre de  Hanoi
Claudio Kirner - 2007

O tempo de execução do algoritmo da Torre de Hanoi, tanto para a execução manual, quanto para execução por computador, depende do número de movimentos necessários para a transferência da torre de um pino a outro.

Fig. 1 - Movimentação de um disco de um pino a outro.

Analisando o algoritmo, percebe-se que a solução, para uma torre com D discos, depende do movimento de D-1 discos (torre de cima) do pino origem para o auxiliar, da movimentação do disco de baixo para o pino destino e da movimentação de D-1 discos do pino auxiliar para o destino.

Considerando M o número de movimentos e D o número de Discos, tem-se: MD = 2*MD-1 +1.

Partindo-se de uma torre com 1 disco, cuja solução é 1 movimento, os movimentos para torres com mais discos resultam na Tabela 1.

Através de inspeção, percebe-se que o número de movimentos é:

(MD = 2**D – 1).



Os interessados poderão consultar os links disponíveis para ver a dedução formal da fórmula. A título de curiosidade, se alguém tentar transferir uma torre de 12 discos, gastando 3 segundos por movimento, levará 3 x 4096 = 12.288  segundos, que corresponde a aproximadamente 3 horas e meia, trabalhando sem parar.

(PRÓXIMO)