• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

wavee

[Ajuda] Estrutura do programa: 3 Missionários e 3 Canibais

21 mensagens neste tópico

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á

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros 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  :ipool:

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

...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros 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  :ipool:

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 :cheesygrin:

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 

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros 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?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros 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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros 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!

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros 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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ok, obrigado pelo esclarecimento, o DFS cheira-me a algoritmo para IA... ainda n fiz a cadeiramas tb so tenho essa este semestre :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Já joguei um jogo com essa mesma mecânica. O jogo foi desenvolvido em flash!;)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros 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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros 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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros 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#

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros 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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros 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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros 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...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora