Aprendiz
Respostas dos
Exercícios Propostos
Jaime Evaristo
Instituto de Computação
Universidade Federal de Alagoas
Capítulo 1
1. Naturalmente, na primeira travessia, um índio levaria um branco até a outra margem e voltaria sozinho. A questão é a segunda: não poderia atravessar um índio e um branco, pois, ao chegar na outra margem, haveria dois brancos e um índio; não poderiam atravessar dois índio, pois o terceiro ficaria com dois brancos. A solução é atravessar dois brancos e um deles retornar. A terceira travessia só pode ser feita por dois índios, pois já existem dois brancos na outra margem. A questão é o retorno. A única possibilidade é retornar um índio e um branco! Temos então o seguinte algoritmo:
1. Atravessem um índio e um branco.
2. Retorne o índio.
3. Atravessem dois brancos.
4. Retorne um branco.
5. Atravessem dois índios.
6. Retornem um índio e um branco.
7. Atravessem dois índios.
8. Retorne um branco.
9. Atravessem dois brancos.
10. Retorne um branco.
11. Atravessem dois brancos.
2. Indicando por 1, 2, 3, 4, ... os discos na ordem crescente dos seus diâmetros, temos para o caso n = 2:
1. Disco 1 da origem para auxiliar.
2. Disco 2 da origem para o destino.
3. Disco 1 da auxiliar para o destino.
Para o caso n = 3, basta observar que é necessário apenas transportar os dois discos 1 e 2 da origem para auxiliar (que é o caso anterior), transportar o disco 3 da origem para o destino e os discos 1 e 2 da torre auxiliar para o destino (que é, novamente, o caso anterior). 1. Disco 1 da origem para destino.
2. Disco 2 da origem para auxiliar.
3. Disco 1 do destino para auxiliar.
4. Disco 3 da origem para destino.
5. Disco 1 da auxiliar para origem.
6. Disco 2 da auxiliar para o destino.
7. Disco 1 da origem para o destino.
3. Para facilitar a linguagem, indiquemos por P(m, n) = 0 se as esferas m e n têm o mesmo peso e por P(m, n) > 0 se a esfera m pesa mais que a esfera n. Temos então a seguinte