Imagine o seguinte problema:
Três canibais e três missionários se encontram à margem direita de um rio. Todos precisam cruzar esse rio, e para isso dispõem de um barco onde cabem somente duas pessoas de cada vez.
Os missionários precisam tomar cuidado ao fazer a travessia porque, se em qualquer instante houver mais canibais do que missionários em alguma das margens (havendo missionários naquela margem), os canibais "degustarão" alegremente os missionários.
Considerando estas restrições, como fazer com que todas as pessoas cruzem o rio e cheguem ao outro lado sãs e salvas?
Algumas estratégias possíveis podem ser descartadas (por exemplo, fazer com que um ou dois missionários cruzem inicialmente o rio sem nenhum canibal, já que os missionários que restassem teriam que "enfrentar" um número maior de canibais). Porém, mesmo assim o conjunto total de possibilidades pode ser testado e as soluções encontradas, desde que se possua uma forma rápida o suficiente para testar cada possibilidade, já que o conjunto de possibilidades é relativamente grande. Partindo desse princípio, um programa de computador adequado, rodando em um micro suficientemente rápido, poderia resolver o problema dos missionários e dos canibais em segundos, mostrando todas as soluções possíveis.
Questão: elaborar um programa, em linguagem C, para resolver o problema dos missionários e dos canibais. O programa deve:
- receber do usuário
o número total de missionários e canibais, permitindo que o mesmo
problema seja processado (e eventualmente resolvido) com outros valores além
dos fornecidos no texto.
- processar cada uma das possibilidades de travessia e encontrar as soluções
do problema. Para cada uma das soluções possíveis, exibir
cada um dos passos da travessia, mostrando qual foi ou quais foram as
pessoas que atravessaram em cada um dos passos.
Não é necessário representar graficamente a travessia, apenas em forma de texto. Por exemplo:
Ida 1: 1 missionário,
1 canibal
Volta 1: 1 canibal
Ida 2: 2 canibais
Volta 2: 1 missionário
...
Se o problema não tiver solução, para o conjunto de valores fornecidos, informar ao usuário (observação: existem pelo menos 1 solução para três missionários e três canibais)
Para entender melhor
o problema dos missionários e dos canibais e tentar resolvê-lo
de forma interativa, clique aqui