Os missionários e os canibais

Solução:

Achei esta solução num trabalho de informática da Puc - Rio, muito interessante por sinal.
Para vê-lo, clique aqui.
No entanto antes eu tentei através desse jogo, aqui é possível tentar todas as possibilidades para depois montar uma solução como a de cima.




Algorítmo


Transporte 2 canibais
Volte com 1 canibal , deixe do outro lado um canibal
Leve 2 canibais para o outro lado
Deixe 1 canibal do outro lado (que agora tem 2 canibais)
Volte com 1 canibal, leve 2 missionários
Deixe 1 missionário e 1 canibal do outro lado,
Volte com 1 canibal e 1 missionário
Troque o canibal pelo missionário, ficando do lado esquerdo 3 missionários.
Volte com 1 canibal e busque o outro canibal
Voltei com 1 canibal e busque o último, totalizando do lado esquerdo 3 canibais e 3 missionários. 

Torre de Hanoi

Algorítmo da Torre de  Hanoi
Por Claudio Kirner - 2007

A solução para o problema da Torre de Hanoi com recursividade é compacta e baseia-se no seguinte:

a) A única operação possível de ser executada é "move disco de um pino para outro";

b) Uma torre com (N) discos, em um pino, pode ser reduzido ao disco de baixo e a torre de cima com (N-1) discos;

c) A solução consiste em transferir a torre com (N-1) discos do pino origem para o pino auxiliar, mover o disco de baixo do pino origem para o pino destino e transferir a torre com (N-1) discos do pino auxiliar para o pino destino. Como a transferência da torre de cima não é uma operação possível de ser executada, ela deverá ser reduzida sucessivamente até transformar-se em um movimento de disco.

A Fig. 1 mostra os passos da solução com o disco de baixo e a torre de cima. Para mover a torre de cima, aplica-se novamente a solução com o disco de baixo dessa torre e a subtorre de cima, e assim por diante até sobrar só um disco, que poderá ser movido. Isto liberará a movimentação dos outros discos de baixo, que ficaram pendentes, constituindo uma solução recursiva.

Fig. 1 - Solução da Torre de hanoi com o disco de baixo e a torre de cima.

Fonte

Mensagem do dia