Exercícios Resolvidos de Algoritmos

Ver Teoria

Enunciado

A “Torre de Hanói” é um quebra-cabeça que a gente movimenta discos por hastes. A imagem abaixo mostra 3 hastes, A, B e C, com 4 discos iniciados na haste A.

O objetivo é mover os 4 discos pra haste C.

Porém, existem algumas regras:

  • Você só pode mover um disco por vez;
  • Você não pode colocar um disco maior em cima de um menor.

Obs: lembre-se que o melhor algoritmo é aquele com menor custo, ou seja, menor quantidade de movimentos que você puder!

Passo 1

Cara, esse é um problema clássico no meio da computação. Você pode ver como um joguinho, que a gente pode resolver como um quebra cabeça. Um quebra cabeça difícil pacas!

Vamos a uma das possíveis resoluções. Mas antes, queria te lembrar que não tem só uma solução, beleza? Problemas de algoritmo podem ter vááárias possíveis soluções, você pode encontrar a sua. Mas sem esquecer que o ideal é usar o mínimo de movimentos possíveis, beleza?

Olha esse algoritmo:

  1. Disco 1 de A pra B
  2. Disco 2 de A pra C
  3. Disco 1 de B pra C
  4. Disco 3 de A pra B
  5. Disco 1 de C pra A
  6. Disco 2 de C pra B
  7. Disco 1 de A pra B
  8. Disco 4 de A pra C
  9. Disco 1 de B pra C
  10. Disco 2 de B pra A
  11. Disco 1 de C pra A
  12. Disco 3 de B pra C
  13. Disco 1 de A pra B
  14. Disco 2 de A pra C
  15. Disco 1 de B pra C

Viu? Depois desses passos, todos os discos vão estar na estaca C.

Valeu!! Até a próxima!

Resposta

  1. Disco 1 de A pra B
  2. Disco 2 de A pra C
  3. Disco 1 de B pra C
  4. Disco 3 de A pra B
  5. Disco 1 de C pra A
  6. Disco 2 de C pra B
  7. Disco 1 de A pra B
  8. Disco 4 de A pra C
  9. Disco 1 de B pra C
  10. Disco 2 de B pra A
  11. Disco 1 de C pra A
  12. Disco 3 de B pra C
  13. Disco 1 de A pra B
  14. Disco 2 de A pra C
  15. Disco 1 de B pra C