Canibais e Missionários - Algoritmo e Solução

Três canibais e três missionários estão viajando juntos e chegam à margem de um rio. Eles desejam atravessar para a outra margem para, desta forma, continuar a viagem. O único meio de transporte disponível é um barco que comporta no máximo duas pessoas. Há uma outra dificuldade: em nenhum momento o número de canibais pode ser superior ao número de missionários pois desta forma os missionários estariam em grande perigo de vida. Como administrar a travessia?


Solução:

Imagem a parte, resolvi o problema pelos passos abaixo, e ficou assim:


1- Missionário e Canibal no Barco
2- Deixar Canibal
3- Dois Canibais no Barco
4- Deixar Canibal
5- Dois Missionários no Barco
6- Deixar um Missionário
7- Volta um Missionário e um Canibal no Barco
8-Deixar Canibal
9- Dois Missionários no Barco
10- Deixar ambos
11- Canibal volta sozinho no Barco
12- Agora, dois Canibais no Barco
13- Deixa um na margem oposta e volta para pegar o ultimo...


É isso, fica bem dificil imaginar o problema e ir fazendo pelos passos acima né? Então sugiro que cliquem no link abaixo e resolvam o problema num game ^^

http://rachacuca.com.br/jogos/missionarios-e-canibais/



Algoritmo:

Se o barco esta na posição direita
     Se o missionario1 estiver na posição inicial                                          // isto serve para mover o padre para o barco
          Se o lugar esquerdo do barco nao estiver ocupado
               Move o missionario1 para o lugar esquerdo do barco
               Definie o lugar esquerdo do barco como ocupado
          Senao
               Se o lugar direito do barco nao estiver ocupado
                    Move o missionario1 para o lugar direito do barco
                    Da o lugar direito do barco como ocupado
     Senao                                                                                                // aqui move do barco para terra
          Se o missionario1 estiver na posicao esquerda do barco
               Move o missionario1 para a posicao inicial
               Da o lugar esquerdo como livre
          Se o missionario1 estiver na posicao direita do barco
               Move o missionario1 para a posicao inicial
               Da o lugar direito como ocupado
Senao                                                                                                  // o barco esta no lado esquerdo
     Se o missionario1 esta na terra (no lado esquerdo)                                // tamos a tentar colocar 1º o missionario no barco
          Se o lugar esquerdo do barco n tiver ocupado
               Move o missionario1 para o lugar esquerdo do barco
               Da o lugar esquerdo do barco como ocupado
          Senao
              Se o lugar direito do barco n tiver ocupado
                   Move o missionario1 para o lugar direito
                   Da o lugar direito do barco como ocupado
     Senao                                                                                             // salta do barco para a terra
          Se o missionario1 esta na posicao esquerda do barco
               Move o missionario1 para a sua posicao em terra
               Da o lugar esquerdo do barco como ocupado
         Se o missionario1 esta na posicao direita do barco
               Move o missionario1 para a sua posicao em terra
               Da o lugar direito do barco como ocupado






A base do algortimo é essa, claro que não esta completo para todos os passos............