Jump to content

Estrutura do programa: 3 Missionários e 3 Canibais


wavee
 Share

Recommended Posts

Olá a todos

Bem não percebo muito de programação e precisava da vossa ajuda é um problema já conhecido por muitos que é este.

3 Missionários e 3 Canibais pretendem atravessar um rio só existe um barco de 2 lugares para fazer a travessia. Em circunstância nenhuma os canibais podem ficar em maioria, como executar a travessia?

O que eu prentendia era só a estrutura disto num algoritmo tou com duvidas em como defenir a estrutura do barco e verificar se ele está cheio ou não se me pudessem ajudar agradecia.

Obrigado desde já

Link to comment
Share on other sites

Olá a todos

Bem não percebo muito de programação e precisava da vossa ajuda é um problema já conhecido por muitos que é este.

3 Missionários e 3 Canibais pretendem atravessar um rio só existe um barco de 2 lugares para fazer a travessia. Em circunstância nenhuma os canibais podem ficar em maioria, como executar a travessia?

O que eu prentendia era só a estrutura disto num algoritmo tou com duvidas em como defenir a estrutura do barco e verificar se ele está cheio ou não se me pudessem ajudar agradecia.

Obrigado desde já

Antes de mais, benvindo ao fórum

Por acaso não és do IST? Esse problema é referido na cadeira de IA.

Bem na cadeira refere um espaço de estados que é do tipo (X,Y, Z, W)

Onde X e Y é respectivamente o n.º de missionários e canibais numa margem, e Z e W é respectivamente o n.º de missionários e canibais noutra margem.

Consideras a acção {A, B, C}, onde A e B é respectivamente o número de missionários e canibais no barco e C refere se o barco vai da margem 1 -> 2 ou 2 -> 1.

Quando efectuas uma acção, há uma mudança de estado e em cada novo estado, verificas se é válido/não válido ou um estado repetido (que consideras como inválido, se não estás sempre às voltas).

Agora o tipo de procura, tu é que escolhes (se calhar o melhor é a procura em largura ou profundidade limitada, apesar de gastar muita memória).

Espero ter acendido umas luzes...

Bem isto é um dúvida de algoritmia, por isso, tópico movido!

Cumpr. bk@ero  ?

EDIT:

Uma demostraçãozinha:

O estado inicial -> (3,3,0,0)

acções possíveis -> estado seguinte

{2,0,1} -> (1,3,2,0) -> inválido

{1,1,1} -> (2,2,1,1) -> próxima acção -> .... -> ....

{0,2,1} -> (3,1,0,2) -> inválido

...

Link to comment
Share on other sites

Antes de mais, benvindo ao fórum

Por acaso não és do IST? Esse problema é referido na cadeira de IA.

Bem na cadeira refere um espaço de estados que é do tipo (X,Y, Z, W)

Onde X e Y é respectivamente o n.º de missionários e canibais numa margem, e Z e W é respectivamente o n.º de missionários e canibais noutra margem.

Consideras a acção {A, B, C}, onde A e B é respectivamente o número de missionários e canibais no barco e C refere se o barco vai da margem 1 -> 2 ou 2 -> 1.

Quando efectuas uma acção, há uma mudança de estado e em cada novo estado, verificas se é válido/não válido ou um estado repetido (que consideras como inválido, se não estás sempre às voltas).

Agora o tipo de procura, tu é que escolhes (se calhar o melhor é a procura em largura ou profundidade limitada, apesar de gastar muita memória).

Espero ter acendido umas luzes...

Bem isto é um dúvida de algoritmia, por isso, tópico movido!

Cumpr. bk@ero  ?

EDIT:

Uma demostraçãozinha:

O estado inicial -> (3,3,0,0)

acções possíveis -> estado seguinte

{2,0,1} -> (1,3,2,0) -> inválido

{1,1,1} -> (2,2,1,1) -> próxima acção -> .... -> ....

{0,2,1} -> (3,1,0,2) -> inválido

...

Obrigado pela resposta 😁

Não não sou do Ist estudo no Porto. Eu tava a pensar resolver por vectores mas vou tentar ir pelo caminho que me deste obrigado 

Link to comment
Share on other sites

Em q linguagem e q vais fazer o jogo?

Do modo como tou a imaginar o jogo, vou usar posições fixas para cada 1 dos componentes (Missionários , Canibais e barco)

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

Como n sei a linguagem q vais usar, nem como n sei se vais fazer em modo texto ou grafico.... fica so +  esta pequena ajuda... isto move os padres e demonios (1 codigo destes para cada 1) para as 4 posicoes possiveis do jogo.

Para mover o barco de um lado para outro:

Se o lugar esquerdo do barco estiver ocupado OU o lugar direito

    Se o barco estiver na posicao direita

          Mover o barco para a posicao esquerda

          Dizer q o barco esta no lado esquerdo

          Se o missionario1 estiver no lado esquerdo do barco

              Mover o missionario1 para o lado esquerdo do barco qdo este esta na posicao esquerda (o barco)

              Decrementar a quantidade de missionarios no lado esquerdo

              Incrementar a quantidade de missionarios no lado direito

          Se o missionario2.....

        // Isto e igual para cada 1 dos bonecos, inclusive o lado direito do barco

   

    Senao

          Se o barco estiver na posicao esquerda

              // fazer exctamente ao contrario do if acima

//condicao de vitoria

Se a quantidade de canibais no lado esquerdo for maior que a quantidade de missionarios do lado esquerdo

    Se a quantidade de missionarios for maior que 0

          PERDEU

Se a quantidade canibais no lado direito for maior que a quantidade de missionarios do lado direito

    Se a quantidade de padres  no lado direito for maior que 0

          PERDEU

Eficaz? N sei...

Simples? Axo q sim... isto da para implementar somente com variaveis

O caminho do brinkaero tambem usa vectores. Eu resolveria usando um DFS, visto serem poucas as combinações.

O q são DFS?

Link to comment
Share on other sites

Eficaz? N sei...

Simples? Axo q sim... isto da para implementar somente com variaveis

Bem muito obrigado era mesmo isto que eu queria, isto vai ser para implementar em C# com a ajuda que me deste já fiquei com a 1ªa fase do trabalho resolvido. Obrigado desde já a todos.

Link to comment
Share on other sites

Já fiz um trabalho identico e posso te ajudar com mais umas ideias!

-Criei uma variavel do tipo string com 3 caracteres, ou seja com 3 posições desde o 0 ao 2.

-Inicializei a variavel a d00 ( "d" = que equivale a ter o barco na margem esquerda e , "00" que são as posições em cima do barco.

-Sempre que uma figura sobe para o barco incremento um 1 na primeira posição ou na segunda se esta já estiver preenchida!

Exemplos:

Se  o barco estiver da margem direita e tem o 1º lugar cheio com uma figura vou ter a seguinte string "d10"

Se  o barco estiver da margem direita e tem o 2º lugar cheio com uma figura vou ter a seguinte string "d01"

Se o barco estiver da margem direita e tem os  2º lugar cheio s com duas  figuras vou ter a seguinte string "d11"

Assim sendo, temos o mesmo para o lado esquerdo da margem:

Se  o barco estiver da margem esquerda e tem o 1º lugar cheio com uma figura vou ter a seguinte string "e10"

Se  o barco estiver da margem esquerda e tem o 2º lugar cheio com uma figura vou ter a seguinte string "e01"

Se o barco estiver da margem esquerda e tem os  2º lugar cheio s com duas  figuras vou ter a seguinte string "e11"

Com esta pequena string podes gerir o resto do codigo com um simples case que verifica a posição do barco na posição 0 da string ou seja a primeira!

Se quiseres mais alguma ajuda envia mensagem privada que eu facilito o email do msn para ajudar, na boa!

Link to comment
Share on other sites

O q são DFS?

DFS = depth first search, busca em profundidade.

Basicamente, vais testas todos os movimentos possíveis recursivamente, e escolhes o "correcto".

Começas com 3 padres e 3 canibais, tentas mover 2 padres, ele dá erro (margem esquerda com mais canibais do que padres), volta um passo atras, tenta mover 2 canibais. Na margem direita, tenta mover um padre para a esquerda, dá erro, porque não há padres na margem direita, volta atras. Move um canibal. E volta ao inicio, desta vez com 3 padres e 2 canibais. Se implementado correctamente eu diria que nao iria além das 10 linhas (claro que posso estar enganado)..

Atenção: A solução que apontaram é muitíssimos mais eficiente, porque limita-se a arranjar a resposta correcta, e não a testar todas as respostas possíveis para verificar se são correctas ou não.

Link to comment
Share on other sites

Olá Pessoal.

Alguem sabe de alguma implementação do algoritmo A* para o problema dos três canibais e três missionários que pretendem atravessar um rio. Eles dispõem de um barco que só pode levar duas pessoas. Os missionários têm de ter cuidado para que o número de canibais nunca exceda o número de missionários numa margem, senão os canibais comem os missionários.

Se por acaso, for em C#, melhor.

Espero que alguem me ajude. O meu email é avelnunes@hotmail.com.

Xau, pessoal.

Link to comment
Share on other sites

boas ! eu tenho um bastante parecido.

"Um grupo de 3 missionários e de 3 canibais pretende atravessar um rio. Para esse efeito existe um barco com 2 lugares. Como efectuar a travessia do grupo de 6 pessoas de forma a garantir (por uma questão de segurança para os missionários) que o número de canibais, em qualquer das margens, nunca é superior ao número de missionários? Apresentar a solução com um algoritmo escrito em linguagem corrente."

Se alguem se quiser aventurar ! :)

força

Link to comment
Share on other sites

Eu vou dar o algoritmo A* em Inteligencia Artificial no próximo semestre... desconheço o algoritmo... mas pensava que era vocacionado para linguagens como o prolog e não C#

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Link to comment
Share on other sites

Eu vou dar o algoritmo A* em Inteligencia Artificial no próximo semestre... desconheço o algoritmo... mas pensava que era vocacionado para linguagens como o prolog e não C#

O algoritmo A* é usado em todas as linguagens mesmo, normalmente para path finding em jogos.

<3 life

Link to comment
Share on other sites

antónioramos

Alguém tem a resolução em C deste jogo precisava mesmo para fazer um trabalho de programação mas nem sei como vou começar alguém pode ajudar-me, por favor, agradecia mesmo muito.

Link to comment
Share on other sites

Alguém tem a resolução em C deste jogo precisava mesmo para fazer um trabalho de programação mas nem sei como vou começar alguém pode ajudar-me, por favor, agradecia mesmo muito.

O trabalho é sobre este jogo? Já tens muitas ajudas nos posts anteriores sobre o algoritmo a usar para resolver o problema, leste-os bem ?

Analisar soluções já feitas não ajuda muito a aprender a sério, eventualmente, só alguns truques...

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Link to comment
Share on other sites

É como já foi dito. Lê o tópico. Vais ter que usar um algoritmo de procura. Se tiveres dúvidas, pergunta.

Não respondo a dúvidas por mensagem.

Link to comment
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
 Share

×
×
  • 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.