842. Torres de Hanói

Olá meus amigos nerds, vocês sabiam que há uma lenda que diz que quando alguém conseguir resolver o problema das torres de Hanói usando 64 discos o mundo acabará? Hoje, vamos descobrir se essa lenda é verdadeira ou não ao resolver o problema 842. Torres de Hanói.

O conhecido quebra-cabeça consiste em uma base contendo três pinos, em um dos quais são dispostos alguns discos uns sobre os outros, em ordem crescente de diâmetro, de cima para baixo. O problema consiste em passar todos os discos de um pino para outro qualquer, usando um dos pinos como auxiliar, de maneira que um disco maior nunca fique em cima de outro menor em nenhuma situação.

Na realidade esse problema não nos pede para resolver o desafio das torres de hanói, inclusive ele nos apresenta a solução do mesmo e nos pede para que computemos o número de operações necessárias para solucionar o quebra cabeça.

Hanoi(N, Orig, Dest, Temp)

   se N = 1 então

      mover o menor disco do pino Orig para o pino Dest;

   senão

      Hanoi(N-1, Orig, Temp, Dest);

      mover o N-ésimo menor disco do pino Orig para o pino Dest;

      Hanoi(N-1, Temp, Dest, Orig);

Solução

Do algorítimo acima tiramos a seguinte relação de recorrência:

Hanoi (N) = 2*Hanoi(N-1) + 1

Expandindo a recorrência mais um pouco temos:

Hanoi (N) = 2*(2*Hanoi(N-2) + 1) + 1 = 4*Hanoi(N-2) + 2+1 = 8*Hanoi(N-3) + 4 + 2 + 1

Observe que, após "resolvermos" a expressão acima i vezes ela poderia ser escrita da seguinte forma:

Hanoi(N) = 2^i * Hanoi (N - i) + [sum 2^(x - 1) para x de 1 a i]

quando i == N temos:

Hanoi(N) = 2^N * Hanoi (0) + [sum 2^(x - 1) para x de 1 a N]

Mas Hanoi(0) = 0 já que se não houver peças não precisamos mover nada. Por outro lado [sum 2^(x - 1) para x de 1 a N] = 2^(N-1) - 1. Logo:

Hanoi(N) = 2^(N-1)

É interessante notar, que há uma outra solução bem obvia para o problema: Implementar e instrumentar o algoritmo acima e contar o número de movimentos na força bruta. Como você pode ver, pela ordem de grandeza do número de operações, essa solução certamente seria muito ineficiente e receberia um TLE.

Só por curiosidade, a lenda é verdadeira, se alguém gastasse 1 segundo para mover um disco, 2^64  = 1.8446744e+19 segundos é muito mais tempo que a idade do universo.

Implementação