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: M_D = 2*M_D-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 é:

(M_D = 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.