Algoritmo para a resolução da Torre de Hanoy (L2)

A Torre de Hanói é um quebra-cabeça que consiste em uma base contendo três pinos, em um dos quais são dispostos alguns discos uns sobre os outros, em ordem crescente de diâmetro, de cima para baixo. O problema consiste em passar todos os discos de um pino para outro qualquer, usando um dos pinos como auxiliar, de maneira que um disco maior nunca fique em cima de outro menor em nenhuma situação. O número de discos pode variar sendo que o mais simples contém apenas três.

A solução :

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

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

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.

(L1) Os Missionários e Canibais

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.