Lembra do jogo das torres de Hanoi que mencionei na primeira aula? Espero que você tenha jogado um pouco pois agora vamos ver como juntar todos os fundamentos do pensamento computacional para resolver esse problema.
O tabuleiro do jogo é composto por três postes e um conjunto de discos de tamanhos diferentes. Os discos começam empilhados do maior para o menor no primeiro poste e o objetivo é mover a pilha para o terceiro poste. As regras são simples:
Posição inicial.
Posição final.
Vamos analisar o problema mais simples, quando a pilha tem somente um disco. A solução é trivial, basta mover o disco da coluna da esquerda para a coluna da direita.
Passamos para o problema com dois discos.
Primeiro é preciso liberar o disco maior para ele poder se movimentar usando o poste intermediário para guardar o disco menor.
Então, movemos o disco maior para a posição final.
Por fim, movemos o disco menor para terminar a solução. Fácil, mas ainda não ajuda muito a resolver os problemas com muitos discos.
No problema com três discos a coisa começa a ficar realmente interessante, acompanhe.
Podemos pensar nos dois discos menores como um disco "composto". Dessa forma o problema se reduz para o caso com 2 discos.
O que queremos é mover a pilha superior para o poste intermediário para liberar o disco maior. Perceba que nós já sabemos como mover uma pilha de dois discos.
Movemos o disco maior para a sua posição final.
Por fim, terminar de mover a pilha.
Como fica o problema com 4 discos? Seguimos a mesma estratégia.
Movemos a subpilha para o poste intermediário para liberar o disco maior.
Movemos o disco maior para a posição final.
Finalizamos movendo a subpilha para a posição final. Perceba que sabemos mover uma pilha de três discos para uma determinada posição.
Vamos construir uma representação simplificada do problema para tentar reconhecer algum padrão que nos permita construir um algoritmo para resolver o problema. Vou nomear os postes com as letras A, B e C e vou numerar os discos na sequência do menor para o maior.
Assim, para resolver o problema com três discos, precisamos seguir a seguinte sequência de movimentos: 0 → 1 → 0 → 2 → 0 → 1 → 0. Podemos observar um determinado padrão emergindo: sempre movimentamos o disco 0 seguido de outro disco. Vamos observar isso melhor.
Posição inicial →
0 →
1 →
0 →
2 →
0 →
1 →
0 → Fim
Pare um pouco e veja como aparentemente surge uma estrutura do tipo: 0 → 1 → 0 → 2 → 0 → 1 → 0. Sem demonstração vou afirmar que a solução do problema de 4 discos deve ser algo do tipo:
0 → 1 → 0 → 2 → 0 → 1 → 0 → 3 → 0 → 1 → 0 → 2 → 0 → 1 → 0. Pare e teste no jogo.