Jump to content

Mother's Milk


polska
 Share

Recommended Posts

Boas pessoal, estou a resolver o problema da USACO Mother's Milk, e pensei numa DFS, penso que seja um problema que enquadre muito bem nesta resolução, então implementei o programa, e uma função void dfs, o problema, é que não estou a perceber que condições devo colocar... o problema é o seguinte:

Farmer John has three milking buckets of capacity A, B, and C liters. Each of the numbers A, B, and C is an integer from 1 through 20, inclusive. Initially, buckets A and B are empty while bucket C is full of milk. Sometimes, FJ pours milk from one bucket to another until the second bucket is filled or the first bucket is empty. Once begun, a pour must be completed, of course. Being thrifty, no milk may be tossed out.

Write a program to help FJ determine what amounts of milk he can leave in bucket C when he begins with three buckets as above, pours milk among the buckets for a while, and then notes that bucket A is empty.

PROGRAM NAME: milk3

INPUT FORMAT

A single line with the three integers A, B, and C.

SAMPLE INPUT (file milk3.in)

8 9 10

OUTPUT FORMAT

A single line with a sorted list of all the possible amounts of milk that can be in bucket C when bucket A is empty.

SAMPLE OUTPUT (file milk3.out)

1 2 8 9 10

Eu percebo o que pede pede o problema, devo imprimir todos os valores que o balde C por conter quando o balde A esta vazio.. Porém, não estou a entender que condições devo colocar na minha função dfs, eu já coloquei o mapa dos baldes que já verifiquei e um array com os valores possiveis, mas as condições não estou a consseguir..

este e o meu code, quem me puder ajudar:

#include <stdio.h>
#include <assert.h>

bool verificado[21][21][21], can[21]; //inteiros entre 1 e 20, inclusive
int a, b, c;

/* DFS - Depth first search */
void dfs( int bA, int bB, int bC )
{
//verifica se a possibilidade (bA,bB) ja foi testada, se foi não repete o teste
if( verificado[bA][bB][bC] )
 return;

//marca a possibilidade (bA,bB,bC) como testada, para a próxima vez não passar na condição acima
verificado[bA][bB][bC] = true;

//se bA esta vazia então bC é um dos resultados
if( bA == 0 )
 can[bC] = true;

//condicoes...



}

int main()
{
FILE *in, *out;
in = fopen( "milk3.in", "r" );
out = fopen( "milk3.out", "w" );
assert( in != NULL && out != NULL );

//recebe a, b, c
fscanf( in, "%d %d %d", &a, &b, &c );

dfs( 0, 0, c );

for( int i=0; i<c; i++ )
{
 if( can[i] )
  printf( "%d ", i );
}
printf( "\n" );

return 0;
}

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Link to comment
Share on other sites

Repara que numa determinada situação (por exemplo: 2 litros no balde A, 3 no B e 5 no C) só podes evoluir para seis situações (não obrigatoriamente distintas): podes passar do balde A para o balde B ou C (0-5-5 ou 0-3-7), do balde B para A ou C (5-0-5 ou 2-0-8), e do balde C para o balde A ou B (7-3-0 ou 2-8-0). Cada passagem é completa, isto é, ou enches o balde destino ou esvazias o balde origem.

/* calcular tAB, tAC, tBA, tBC, tCA, tCB: as transferencias de um balde para outro */
dfs(bA-tAB, bB+tAB, bC); /* Balde A para B */
dfs(bA-tAC, bB, bC+tAC); /* Balde A para C */
dfs(bA+tBA, bB-tBA, bC); /* Balde B para A */
dfs(bA, bB-tBC, bC+tBC); /* Balde B para C */
dfs(bA+tCA, bB, bC-tCA); /* Balde C para A */
dfs(bA, bB+tCB, bC-tCB); /* Balde C para B */
Edited by pmg

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Link to comment
Share on other sites

Repara que numa determinada situação (por exemplo: 2 litros no balde A, 3 no B e 5 no C) só podes evoluir para seis situações (não obrigatoriamente distintas): podes passar do balde A para o balde B ou C (0-5-5 ou 0-3-7), do balde B para A ou C (5-0-5 ou 2-0-8), e do balde C para o balde A ou B (7-3-0 ou 2-8-0). Cada passagem é completa, isto é, ou enches o balde destino ou esvazias o balde origem.

/* calcular tAB, tAC, tBA, tBC, tCA, tCB: as transferencias de um balde para outro */
dfs(bA-tAB, bB+tAB, bC); /* Balde A para B */
dfs(bA-tAC, bB, bC+tAC); /* Balde A para C */
dfs(bA+tBA, bB-tBA, bC); /* Balde B para A */
dfs(bA, bB-tBC, bC+tBC); /* Balde B para C */
dfs(bA+tCA, bB, bC-tCA); /* Balde C para A */
dfs(bA, bB+tCB, bC-tCB); /* Balde C para B */

hum, assim já começo a pensar nas condições 🙂

Thanks

Faltam aí uns mínimos/máximos para garantir que não se ultrapassam as capacidades dos baldes.

Como assim? Passar o mínimo de algo e o máximo de algo para a função?

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Link to comment
Share on other sites

hum, assim já começo a pensar nas condições 🙂

Nao te preocupes com as condicoes ... vais ver que chega aquela que ja escreveste (if (verificado...) return;)

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Link to comment
Share on other sites

Nao te preocupes com as condicoes ... vais ver que chega aquela que ja escreveste (if (verificado...) return;)

sim, mas estou a falar daquelas que tenho que fazer para usar :

dfs(bA-tAB, bB+tAB, bC); /* Balde A para B */

dfs(bA-tAC, bB, bC+tAC); /* Balde A para C */

dfs(bA+tBA, bB-tBA, bC); /* Balde B para A */

dfs(bA, bB-tBC, bC+tBC); /* Balde B para C */

dfs(bA+tCA, bB, bC-tCA); /* Balde C para A */

dfs(bA, bB+tCB, bC-tCB); /* Balde C para B */

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Link to comment
Share on other sites

Por exemplo, a transferencia de A para B é uma de duas hipoteses:

1) ou é tudo o que esta no A

2) ou é o suficiente para encher B

destas duas tens de escolher a mais pequena, mesmo que seja zero

nao precisas de mais condicoes.

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Link to comment
Share on other sites

Por exemplo, a transferencia de A para B é uma de duas hipoteses:

1) ou é tudo o que esta no A

2) ou é o suficiente para encher B

destas duas tens de escolher a mais pequena, mesmo que seja zero

nao precisas de mais condicoes.

então vou ter 6 condições, duas para cada balde.

por exemplo para o A verifico se esta vazio ou nao e se da para encher o B ou C , para o B e C a mesma coisa, certo?

Edited by polska

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Link to comment
Share on other sites

Podes fazer assim, como dizes ... mas repara:

se o balde A esta vazio, quando passas 0 litros para o balde B e chamas a funcao recursivamente (com os mesmos valores), a primeira coisa que a funcao faz 'e verificar que o DFS ja passou por essa combinacao e retorna imediatamente.

Como dizes, podes fazer uma condicao e nao chamar a funcao recursivamente ... mas, isso, acho eu, so vai complicar o codigo sem ganhar nada significativo em performance

/* versao com condicoes */
if (bA) {
   tAB = min(bA, <MAXB> - bB); /* min devolve o valor mais pequeno; <MAXB> tem a capacidade do balde B */
   dfs(bA - tAB, bB + tAB, bC);
   tAC = min(bA, <MAXC> - bC); /* tAC nao pode ser zero */
   dfs(bA - tAC, bB, bC + tAC);
}
if (bB) {
   /* ... */
}
/* ... */

/* versao sem condicoes (alem da primeira condicao "recursiva") */
tAB = min(bA, <MAXB> - bB); /* min e o que espera; <MAXB> e a capacidade do balde B */
dfs(bA - tAB, bB + tAB, bC);
tAC = min(bA, <MAXC> - bC); /* pode ser zero */
dfs(bA - tAC, bB, bC + tAC);
/* ... */

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Link to comment
Share on other sites

Podes fazer assim, como dizes ... mas repara:

se o balde A esta vazio, quando passas 0 litros para o balde B e chamas a funcao recursivamente (com os mesmos valores), a primeira coisa que a funcao faz 'e verificar que o DFS ja passou por essa combinacao e retorna imediatamente.

Como dizes, podes fazer uma condicao e nao chamar a funcao recursivamente ... mas, isso, acho eu, so vai complicar o codigo sem ganhar nada significativo em performance

/* versao com condicoes */
if (bA) {
tAB = min(bA, <MAXB> - bB); /* min devolve o valor mais pequeno; <MAXB> tem a capacidade do balde B */
dfs(bA - tAB, bB + tAB, bC);
tAC = min(bA, <MAXC> - bC); /* tAC nao pode ser zero */
dfs(bA - tAC, bB, bC + tAC);
}
if (bB) {
/* ... */
}
/* ... */

/* versao sem condicoes (alem da primeira condicao "recursiva") */
tAB = min(bA, <MAXB> - bB); /* min e o que espera; <MAXB> e a capacidade do balde B */
dfs(bA - tAB, bB + tAB, bC);
tAC = min(bA, <MAXC> - bC); /* pode ser zero */
dfs(bA - tAC, bB, bC + tAC);
/* ... */

Ouve aqui uma confusão pmg 😄 , fiz-me entender mal, eu tou a pensar em fazer recursivamente claro, não faz muito sentido que seja de outra mamenira, mas repara, eu não vou simplesmente chegar ao meu codigo e colar isto:

dfs(bA-tAB, bB+tAB, bC); /* Balde A para B */

dfs(bA-tAC, bB, bC+tAC); /* Balde A para C */

dfs(bA+tBA, bB-tBA, bC); /* Balde B para A */

dfs(bA, bB-tBC, bC+tBC); /* Balde B para C */

dfs(bA+tCA, bB, bC-tCA); /* Balde C para A */

dfs(bA, bB+tCB, bC-tCB); /* Balde C para B */

Tenho de ter uma condição para saber cada chamada recursiva, se isto e isto acontece chamo a função com seguintes parâmetros, se acontecer isto e isto já chamo com outros parâmetros..

Edited by polska

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Link to comment
Share on other sites

... mas repara, eu não vou simplesmente chegar ao meu codigo e colar isto:

dfs(bA-tAB, bB+tAB, bC); /* Balde A para B */
dfs(bA-tAC, bB, bC+tAC); /* Balde A para C */
dfs(bA+tBA, bB-tBA, bC); /* Balde B para A */
dfs(bA, bB-tBC, bC+tBC); /* Balde B para C */
dfs(bA+tCA, bB, bC-tCA); /* Balde C para A */
dfs(bA, bB+tCB, bC-tCB); /* Balde C para B */

Porque? 🙂

Se os tAB, tAC, tBA, tBC, tCA, e tCB forem bem calculados (como exemplificado no meu post anterior) vai funconar 😛

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Link to comment
Share on other sites

Conssegui, obrigado pmg 🙂

/* A para B && A para C */
tAB = min(bA, b - bB);
dfs(bA - tAB, bB + tAB, bC);
tAC = min(bA, c - bC);
dfs(bA - tAC, bB, bC + tAC);
/* B para A && B para C */
tBA = min(bB, a - bA);
dfs(bA + tBA, bB - tBA, bC);
tBC = min(bB, c - bC);
dfs(bA, bB-tBC, bC + tBC);
/* C para A && C para B */
tCA = min(bC, a-bA);
dfs(bA + tCA, bB, bC - tCA);
tCB = min(bC, b-bB);
dfs(bA, bB + tCB, bC - tCB);
Edited by polska

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Link to comment
Share on other sites

Já agora, eu implementei uma dfs, ela percorre todos os caminhos e volta atrás quando um já foi verificado. Agora, se eu quisesse implementar uma bfs, como tinha que fazer, é que esta-me a fazer confusão, eu sei que numa bfs primeiro verifica todos os caminhos possíveis de um nó, e depois quando já foram todos verificados, passa para outro, e volta a verificar todos os possiveis..

Mas como implementar? Eu não sei se neste problema era possível, mas só mesmo para servir de exemplo..

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Link to comment
Share on other sites

A BFS vai pesquisando aos bocadinhos: primeiro todos os bocadinhos de comprimento 1, depois os bocadinhos de comprimento 2, depois os de 3, ...

Normalmente implementa-se com recurso a uma estrutura FIFO (uma queue). Basicamente:

1) mete o primeiro nó na queue

2) se a queue estiver vazia: terminar

3) retira um elemento da queue (o primeiro), marca-o visitado

4) mete todos os "filhos" não visitados desse elemento na queue

5) ir para 2

Edited by pmg

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Link to comment
Share on other sites

A BFS vai pesquisando aos bocadinhos: primeiro todos os bocadinhos de comprimento 1, depois os bocadinhos de comprimento 2, depois os de 3, ...

Normalmente implementa-se com recurso a uma estrutura FIFO (uma queue). Basicamente:

1) mete o primeiro nó na queue

2) se a queue estiver vazia: terminar

3) retira um elemento da queue (o primeiro), marca-o visitado

4) mete todos os "filhos" não visitados desse elemento na queue

5) ir para 2

O primeiro nó então seria o, 0 0 c , e guardava na queue . Mas depois como é que eu sabia que ja tinha todos os bocados deste nó?

Já agora, as chamadas da função mantinham-se certo?

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Link to comment
Share on other sites

Exemplo para capacidades 8 9 10

queue: (0 0 10)

removes o (0 0 10) e marcas visitado;

queue: --

metes na queue os "filhos nao visitados de (0 0 10)": (0 0 10) (0 0 10) (0 0 10) (0 0 10) (8 0 2) (0 9 1)

queue: (8 0 2) (0 9 1)

removes o (8 0 2) e marcas visitado;

queue: (0 9 1)

metes na queue os "filhos nao visitados de (8 0 2)": (0 8 2) (0 0 10) (8 0 2) (8 0 2) (8 0 2) e (8 2 0)

queue: (0 9 1) (0 8 2) (8 2 0)

removes o (0 9 1) e marcas visitado;

queue: (0 8 2) (8 2 0)

metes na queue os "filhos nao visitados de (0 9 1)": (0 9 1) (0 9 1) (8 1 1) (0 0 10) (1 9 0) (0 9 1)

queue: (0 8 2) (8 2 0) (8 1 1) (1 9 0)

...

Edited by pmg

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Link to comment
Share on other sites

eu estou a fazer a class da queue, mas não sei de que tipo deve ser a queue, um array? uma matriz?? Falta-me isso para completar as funções push e pop

#include <iostream>
#include <algorithm>

using namespace std;

#define MAX 21

class queu
{
private:
bool visisted[MAX][MAX][MAX];
bool can[MAX];
int queue[MAX][3]; // ?
int add;
int del;

public:
queu()
{
 add = -1;
 del = -1;
}

void push()
{
 if( add == -1 )
  add = del = 0;
 else
 {
  add++;
  if( add == MAX )
  {
   add--;
   return;
  }
 }
}

void pop()
{
 int tmp;
 if( del != -1 )
 {
  for( int i=0; i<=add; i++ )
  {
   if( (i+1) <= add )
   {

   }
  }
 }
}
};

int main()
{
   return 0;
}

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Link to comment
Share on other sites

Uma fila de pessoas é basicamente uma linha. Um array pode ser visto como uma linha de uma matriz, logo uma matriz não é adequada para implementar uma fila. Um array é uma das hipoteses, outra seria uma lista ligada.

Neste tipo de pesquisa tens de definir qual é o teu estado da pesquisa. Neste caso, o estado é a quantidade em cada um dos 3 baldes. A fila contém uma sequência de estados, por isso a classe fila não terá coisas como visisted[MAX][MAX][MAX] mas sim algo como

struct Estado {
  int a,b,c;
};
struct Queue {
  Estado fila[MAX];
  int inicio, fim;
// ...
};

PS: porque é que na última versão do forum, ao copiar um bocado de código de um post é copiada a formatação também? :/

"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

#include <iostream>
#include <algorithm>

Ah! Estás a usar uma linguagem que já tem uma implementação duma queue na biblioteca standard.

A minha sugestão é que uses as facilidades da linguagem que escolheste, em vez de estares a reinventar a roda.

Não usares a queue da Standard Library é o mesmo que teres um carro mas andares a pé porque não queres usar a chave.

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Link to comment
Share on other sites

Ah! Estás a usar uma linguagem que já tem uma implementação duma queue na biblioteca standard.

A minha sugestão é que uses as facilidades da linguagem que escolheste, em vez de estares a reinventar a roda.

Não usares a queue da Standard Library é o mesmo que teres um carro mas andares a pé porque não queres usar a chave.

Não concordo totalmente. Andar a pé faz muito bem.

Implementa uma queue pelo menos uma vez; a partir daí usa o que a tua linguagem te oferece.

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.