Exercícios Resolvidos de Algoritmos estruturados

Ver Teoria

Enunciado

Três jesuítas e três canibais precisam atravessar um rio; para tal, dispõem de um barco com capacidade para duas pessoas. Por medida de segurança, não se deve permitir que em alguma margem a quantidade de jesuítas seja inferior à de canibais. Qual a solução para efetuar a travessia com segurança? Elabore um algoritmo mostrando a resposta, indicando as ações que concretizam a solução deste problema.

Passo 1

A primeira coisa que devemos fazer é reunir algumas das características do enunciado.

Informações:

  • Um barco com 2 lugares;
  • Três jesuítas;
  • Três canibais.

Regra de segurança:

  • Uma margem sempre deve possuir um número de jesuítas maior ou igual ao de canibais.

Também é interessante definirmos algumas referências para as margens, nesse exemplo utilizaremos A para a margem inicial e B para a margem oposta do rio.

Passo 2

Estando todos na margem A, a primeira travessia do barco será feita com um jesuíta levando um canibal para a margem B desse mesmo rio:

Com o canibal na margem B, o próximo passo do algoritmo é:

Passo 3

Já na margem A, com três jesuítas e dois canibais presentes, existem as seguinte possibilidades:

  1. A travessia de A para B ser feita por um canibal e um jesuíta, nesse caso a margem B se torna insegura para o jesuíta;
  2. A travessia de A para B ser feita por dois jesuítas, nesse caso a margem A se torna insegura para o jesuíta remanescente.

Dessa forma, a travessia do barco da margem A para a margem B deve ser feita por dois canibais:

Com o canibal na margem B, o próximo passo do algoritmo é:

Passo 4

Já na margem A, com três jesuítas e apenas um canibal presentes, existe a seguintes possibilidade de travessia:

  1. A travessia de A para B ser feita por um canibal e um jesuíta, nesse caso a margem B se torna insegura para o jesuíta.

Sendo assim, a travessia do barco da margem A para a margem B deve ser feita por dois jesuítas:

Com um dos jesuítas na margem B, o seu amigo jesuíta não pode voltar sozinho para a margem A, pois a margem B se tornaria insegura para o jesuíta deixado. Com isso, o próximo passo do algoritmo é:

Passo 5

Na margem A, com dois jesuítas e dois canibais presentes, existem as seguintes possibilidades de travessia:

  1. A travessia de A para B ser feita por um canibal e um jesuíta, nenhuma das margens se torna instantaneamente um insegura (mas confia em mim, os retornos se tornam extremamente complicados devido ao espalhamento entre canibais e jesuítas);
  2. A travessia de A para B ser feita por dois canibais, nesse caso a margem B se tornaria um perigo para o jesuíta presente lá.

Dessa forma, a travessia do barco da margem A para a margem B deve ser feita por dois jesuítas:

Na margem B, com os três jesuítas e um canibal presentes, o algoritmo se torna praticamente solucionado.

Uma vez que os três jesuítas já se encontram na margem B, o canibal presente nessa mesma margem pode ser o realizador das travessias que irão buscar os dois canibais remanescentes na margem A, dessa forma os próximos passos do algoritmo serão:

Pronto, agora todos estão em segurança na margem B do rio!

Resposta

O algoritmo completo para a travessia dos três jesuítas e dos três canibais em segurança é: