Jump to content
thoga31

Os Missionários e os Canibais

Recommended Posts

thoga31

Os Missionários e os Canibais

Este é um desafio pertencente à categoria clássica dos problemas dos rios.

A história

Temos 3 missionários e 3 canibais numa margem do rio. O barco apenas aguenta com 2 pessoas de cada vez. Deve-se ter em atenção que, se os canibais estiverem em maior número, mas não igual, aos missionários, eles tornam-se refeição...

O objectivo, claro, é passar todos os 6 elementos da história sem que os missionários sejam transformados em refeição dos canibais.

Objectivo

Construir um programa/script na vossa linguagem de eleição que resolva este problema.

Restrições

O programa/script deve estar preparado para receber por input um número qualquer de canibais e missionários, ou seja, deve estar preparado para resolver este problema qualquer que seja a condição inicial.

Deve haver um controlo do input, ou seja, o nº de missionários nunca deve ser inferior ao de canibais.

Cada passo de resolução deve ter uma parte "Vão" e outra "Voltam" - ou seja, cada passo corresponde a uma ida e volta do barco margem-a-margem.

E lembrem-se: o barco não anda sozinho - pelo menos uma pessoa, missionário ou canibal, deverá ir a bordo para o barco andar.

Exemplo de input/output

Canibais? 3
Missionários? 4
ERRO: Missionários > Canibais
Missionários? 3

SOLUÇÃO:
01) Vão: 2 canibais + 0 missionários. Voltam: 1 canibais + 0 missionários.
02) Vão: 2 canibais + 0 missionários. Voltam: 1 canibais + 0 missionários.
03) Vão: 0 canibais + 2 missionários. Voltam: 1 canibais + 1 missionários.
04) Vão: 0 canibais + 2 missionários. Voltam: 1 canibais + 0 missionários.
05) Vão: 2 canibais + 0 missionários. Voltam: 1 canibais + 0 missionários.
06) Vão: 2 canibais + 0 missionários. Voltam: <FIM!>

Material de apoio

Jogo online para testar o problema

Edited by thoga31

Knowledge is free!

Share this post


Link to post
Share on other sites
HappyHippyHippo

acho que falta um restrição : uma viagem (ida ou volta) deverá sempre levar alguém "o barco não anda sozinho"


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
thoga31

acho que falta um restrição : uma viagem (ida ou volta) deverá sempre levar alguém "o barco não anda sozinho"

Pensei que isso era óbvio, mas eu coloco lá na mesma, não vá alguém ter na solução 3 passos com "Voltam: 0 + 0" :P


Knowledge is free!

Share this post


Link to post
Share on other sites
Flinger

Até porque se assim não for a solução é ainda mais simples :P

Levam-se 2 canibais,volta sozinho, levam-se 2 missionários, volta sozinho, leva os 2 que faltam.

Share this post


Link to post
Share on other sites
HappyHippyHippo

ora bem : aqui vai a minha solução em D com um algoritmo de breadth-first search

import tango.io.Console;
import tango.stdc.stdlib;
import Integer = tango.text.convert.Integer;

// Enumeracao que dita para que lado do rio o barco se movimentou na acao
enum Dir {
   Para_Direita,
   Para_Esquerda
}

// um estado/acao da solução
struct Estado {
   Dir  dir;      // Direcao do barco
   byte eCanibal; // Numero de canibais do lado esquerdo da margem
   byte eMission; // Numero de missionarios do lado esquerdo da margem
   byte dCanibal; // Numero de canibais do lado direito da margem
   byte dMission; // Numero de missionarios do lado direito da margem
   byte action;   // Numero identificativo da acao realizada no estado
}

// Lista de funcoes que actualizam um estado quando o barco se movimenta para a mergem direita do rio
//
// para a direita / acao 1 / 2 canibal e 0 missionarios
// para a direita / acao 2 / 1 canibal e 0 missionarios
// para a direita / acao 3 / 1 canibal e 1 missionarios
// para a direita / acao 4 / 0 canibal e 1 missionarios
// para a direita / acao 5 / 0 canibal e 2 missionarios
Estado c2m0_e_d(Estado e) { e.action = 1; e.dir = Dir.Para_Direita; e.eCanibal -= 2; e.dCanibal += 2; return e; }
Estado c1m0_e_d(Estado e) { e.action = 2; e.dir = Dir.Para_Direita; e.eCanibal -= 1; e.dCanibal += 1; return e; }
Estado c1m1_e_d(Estado e) { e.action = 3; e.dir = Dir.Para_Direita; e.eCanibal -= 1; e.dCanibal += 1; e.eMission -= 1; e.dMission += 1; return e; }
Estado c0m1_e_d(Estado e) { e.action = 4; e.dir = Dir.Para_Direita; e.eMission -= 1; e.dMission += 1; return e; }
Estado c0m2_e_d(Estado e) { e.action = 5; e.dir = Dir.Para_Direita; e.eMission -= 2; e.dMission += 2; return e; }

// Lista de funcoes que actualizam um estado quando o barco se movimenta para a mergem esquerda do rio
//
// para a esquerda / acao 1 / 2 canibal e 0 missionarios
// para a esquerda / acao 2 / 1 canibal e 0 missionarios
// para a esquerda / acao 3 / 1 canibal e 1 missionarios
// para a esquerda / acao 4 / 0 canibal e 1 missionarios
// para a esquerda / acao 5 / 0 canibal e 2 missionarios
Estado c2m0_d_e(Estado e) { e.action = 1; e.dir = Dir.Para_Esquerda; e.dCanibal -= 2; e.eCanibal += 2; return e; }
Estado c1m0_d_e(Estado e) { e.action = 2; e.dir = Dir.Para_Esquerda; e.dCanibal -= 1; e.eCanibal += 1; return e; }
Estado c1m1_d_e(Estado e) { e.action = 3; e.dir = Dir.Para_Esquerda; e.dCanibal -= 1; e.eCanibal += 1; e.dMission -= 1; e.eMission += 1; return e; }
Estado c0m1_d_e(Estado e) { e.action = 4; e.dir = Dir.Para_Esquerda; e.dMission -= 1; e.eMission += 1; return e; }
Estado c0m2_d_e(Estado e) { e.action = 5; e.dir = Dir.Para_Esquerda; e.dMission -= 2; e.eMission += 2; return e; }

// Funcao usada para validar a actualizacao do estado
bool validar(Estado[] solucao) {
   // elemento actualizado a ser verificado
   Estado e = solucao[$-1];

   bool ok = (e.eCanibal <= e.eMission || e.eMission == 0) && // verificar racio de canibais/missionarios do lado esquerdo
             (e.dCanibal <= e.dMission || e.dMission == 0) && // verificar racio de canibais/missionarios do lado direito
             (e.eCanibal >= 0) && (e.dCanibal >= 0) && (e.eMission >= 0) && (e.dMission >= 0) && // validar movimentos invalido que levem a numeros negativos
             (e.dCanibal + e.dMission > 0); // invalidar movimentos que levem ao estado inicial

   // verificar na solucao por um estado igual = ciclo
   for (int index = solucao.length - 2; index >= 0 && ok; index--) {
       if ((solucao[index].dCanibal == solucao[$-1].dCanibal) &&
           (solucao[index].eCanibal == solucao[$-1].eCanibal) &&
           (solucao[index].dMission == solucao[$-1].dMission) &&
           (solucao[index].eMission == solucao[$-1].eMission) &&
           (solucao[index].dir      == solucao[$-1].dir))
               ok = false;
   }

   return ok;
}

// funcao para verificar se a solucao chegou ao fim
bool solucao(Estado e) {
   return (e.eCanibal == 0) &&
          (e.eMission == 0);
}

// funcao recursiva de resolucao do problema
bool calcular(Estado[][] matrix, Dir dir, ref Estado[] res, int iteracao) {
   // matrix auxiliar
   Estado[][] aux;

   // limitar o numero de iteracoes, nao queremos que o programa fique para sempre a correr
   if (iteracao >= 50)
       return false;

   // calculo de novos valores para a matrix
   int n_solucoes = matrix.length * 5;
   int n_passos = matrix[0].length + 1;

   // alocacao de memoria para a matrix dinamica auxiliar
   aux.length = n_solucoes;
   for(int index = 0; index < aux.length; index++)
       aux[index].length = n_passos;

   // ciclo de copia da matrix original para a matrix auxiliar com a concatenacao do nova estado
   for(int index = 0; index < matrix.length; index++) {
       if (dir == Dir.Para_Direita) {
           // movimento do barco da direita para a esquerda
           aux[index*5    ][0 .. n_passos] = matrix[index] ~ c2m0_e_d(matrix[index][n_passos - 2]);
           aux[index*5 + 1][0 .. n_passos] = matrix[index] ~ c1m0_e_d(matrix[index][n_passos - 2]);
           aux[index*5 + 2][0 .. n_passos] = matrix[index] ~ c1m1_e_d(matrix[index][n_passos - 2]);
           aux[index*5 + 3][0 .. n_passos] = matrix[index] ~ c0m1_e_d(matrix[index][n_passos - 2]);
           aux[index*5 + 4][0 .. n_passos] = matrix[index] ~ c0m2_e_d(matrix[index][n_passos - 2]);
       } else {
           // movimento do barco da esquerda para a direita
           aux[index*5    ][0 .. n_passos] = matrix[index] ~ c2m0_d_e(matrix[index][n_passos - 2]);
           aux[index*5 + 1][0 .. n_passos] = matrix[index] ~ c1m0_d_e(matrix[index][n_passos - 2]);
           aux[index*5 + 2][0 .. n_passos] = matrix[index] ~ c1m1_d_e(matrix[index][n_passos - 2]);
           aux[index*5 + 3][0 .. n_passos] = matrix[index] ~ c0m1_d_e(matrix[index][n_passos - 2]);
           aux[index*5 + 4][0 .. n_passos] = matrix[index] ~ c0m2_d_e(matrix[index][n_passos - 2]);
       }
   }

   /* "limpar" a matrix original para ser recriada so com as novas solucoes viaveis */
   matrix.length = 0;
   for (int index = 0; index < n_solucoes; index++) {
       // verifica se o estado calculado e solucao
       if (solucao(aux[index][n_passos - 1])) {
           res = aux[index];
           return true;
       }

       // valida o estado calculado
       if (validar(aux[index])) {
           // adiciona a solucao a matrix de solucoes parciais
           matrix.length = matrix.length + 1;
           matrix[$-1] = aux[index];
       }
   }

   // chamada recursiva de pesquisa da solucao
   if (dir == Dir.Para_Direita)
       return calcular(matrix, Dir.Para_Esquerda, res, iteracao++);
   return calcular(matrix, Dir.Para_Direita, res, iteracao + 1);
}

void main() {
   // matrix inicial de pesquisa de solucao
   Estado[][] matrix;
   // array com a solucao encontrada
   Estado[] resultado;

   // inicializacao da matrix de pesqusia
   matrix.length = 1;
   matrix[0].length = 1;

   // perguntar pelo numero de canibais
   int quantidade = 0;
   while (quantidade < 3 || quantidade > 100) {
       try {
           Cout("Qual o número de canibais? (min = 3 | max = 100)")
               .newline();
           if ((quantidade = Integer.toInt(Cin.get())) < 3)
               Cout("O valor inserido não pode ser inferior a 3")
                   .newline();
       } catch (Object o) {
           Cout("O valor inserido não é um número válido").newline();
       }
   }
   matrix[0][0].eCanibal = quantidade;
   matrix[0][0].dCanibal = 0;

   // perguntar pelo numero de missionarios
   quantidade = 0;
   while (quantidade < matrix[0][0].eCanibal || quantidade > 100) {
       try {
           Cout("Qual o número de missionários? (min = ")
               .append(Integer.toString(matrix[0][0].eCanibal))
               .append(" | max = 100)")
               .newline();
           if ((quantidade = Integer.toInt(Cin.get())) < 3)
               Cout("O valor inserido não pode ser inferior a 3")
                   .newline();
       } catch (Object o) {
           Cout("O valor inserido não é um número válido").newline();
       }
   }
   matrix[0][0].eMission = quantidade;
   matrix[0][0].dMission = 0;

   // chamar a funcao recursiva de pesquisa da solucao
   if (calcular(matrix, Dir.Para_Direita, resultado, 0)) {
       Cout("Solução:").newline();

       // ciclo de apresentacao dos passos da solucao
       for(int index = 1; index < resultado.length; index++) {
           if (index % 2 == 1) {
               Cout(Integer.toString(index / 2));
               Cout(") Vão : ");
               switch (resultado[index].action) {
                   case 1: Cout("2 canibais + 0 missionários. "); break;
                   case 2: Cout("1 canibais + 0 missionários. "); break;
                   case 3: Cout("1 canibais + 1 missionários. "); break;
                   case 4: Cout("0 canibais + 1 missionários. "); break;
                   case 5: Cout("0 canibais + 2 missionários. "); break;
               }
           } else {
               Cout("Voltam : ");
               switch (resultado[index].action) {
                   case 1: Cout("2 canibais + 0 missionários. "); break;
                   case 2: Cout("1 canibais + 0 missionários. "); break;
                   case 3: Cout("1 canibais + 1 missionários. "); break;
                   case 4: Cout("0 canibais + 1 missionários. "); break;
                   case 5: Cout("0 canibais + 2 missionários. "); break;
               }
               Cout.newline();
           }
       }
   } else
       Cout("Não foi possível encontrar nenhuma solução").newline();

   Cout().newline();
   system("PAUSE"); // infelizmente fiz isto no Windows 
}

espero com este post ter apresentado uma "nova" linguagem de programação a muita gente :D

Edited by HappyHippyHippo

IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.