Algoritmos

• 1-Qual é a quantidade min de cada caso?

• 2-Quais as pecas que mais se movimenta

• 3-existe alguma formula matemática que expressa o numero de movimentos ?

• 4-algoritmo matemático para a resolução

• 5-mudando o destino do C para B muda alguma coisa?

• 6-o que você achou da atividade feita com a torre de Hanói?

Respostas

1. 3 discos - 7  Movimentos

      4 discos - 15 Movimentos

      5 discos - 31 Movimentos

      6 discos - 63 Movimentos

      7 discos - 127 movimentos

      15 discos - 32.767 movimentos

      64 discos - 18.446.744.073.709.551.615 movimentos

   

2.   A peça que mais se movimenta é o disco menor (numero 1) seguido pelo numero 2.

3.   [pic 1] sendo n o número de discos.

4.     Aqui usaremos a notação (i, j) para representar a transferência do disco di para o pino j e Tn para uma Torre com n discos. Podemos considerar os pinos 1, 2 e 3 da esquerda para a direita. Abaixo temos a sequência de jogadas para um jogo com três discos, onde a Torre é transferida para o pino 2.

(1,2) → (2,3) → (1,3) → (3,2) → (1,1) → (2,2) → (1,2). 7

Note que para transferir a Torre com 3 discos para o pino j devemos começar movimentando o disco d1 para o pino j.

Considere agora uma Torre com n discos. Ao transferir T3 estará lib- erado um pino para a transferência de d4. Transfira d4 e translade T3 para onde está d4, resultando aí T4. Estará liberado um pino para a transferência de d5. Transfira d5 e transfira T4 para onde está d5 observando o processo anterior. Continuando, sempre estará liberado um pino para a transferência de di. Transfira di e em seguida Ti−1 para onde está di. O jogo estará terminado quando i = n.