Jump to content

Função Recursiva , ajuda


polska

Recommended Posts

Boas pessoal, resolvi recentemente um problema onde me era dado um preço pretendido e um conjunto de N moedas, eu tinha de encontrar o menor preço maior ou igual ao preço pretendido com 4 moedas do conjunto N..

Então eu, para gerar todas as possibilidades do conjunto N com 4 moedas fiz assim:

//gera possibilidades com as 4 moedas
for(i1=0; i1<num_moedas; i1++)
  for(i2=i1; i2<num_moedas; i2++)
for(i3=i2; i3<num_moedas; i3++)
 for(i4=i3; i4<num_moedas; i4++)
  possibilidades[last++] = moedas[i1]+moedas[i2]+moedas[i3]+moedas[i4];

Mas o que eu queria agora, era fazer uma função recursiva que me gerasse essas possibilidades, mas não a consegui fazer, alguém me pode dar uma ajuda?

Aqui deixo o programa todo, pode servir de alguma ajuda:

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int possibilidades[10000];

int compara(const void *a, const void *b)
{
 return (*(int*)a-*(int*)b);
}

bool pesquisa_binaria(int fim, int num)
{
 int meio, inf, sup;
 sup = fim-1;
 inf = 0;

 while(inf <= sup)
 {
   meio = inf+(sup-inf)/2;
   if(num == possibilidades[meio])
 return true;
   if(num > possibilidades[meio])
    inf = meio+1;
   else
 sup = meio-1;
 }
 return false;
}

int main()
{
int preco, num_moedas, moedas[10], i1, i2, i3 ,i4, last = 0;

//Input
scanf("%d\n%d", &preco, &num_moedas);
for(i1=0; i1<num_moedas; i1++) scanf("%d", &moedas[i1]);

//gera possibilidades com as 4 moedas
for(i1=0; i1<num_moedas; i1++)
 for(i2=i1; i2<num_moedas; i2++)
  for(i3=i2; i3<num_moedas; i3++)
   for(i4=i3; i4<num_moedas; i4++)
 possibilidades[last++] = moedas[i1]+moedas[i2]+moedas[i3]+moedas[i4];

//ordena possibilidades
qsort(possibilidades, last, sizeof(int), compara);   

//procura do preço ideal
while(true)
{
 //se encontrar, imprime e sai do programa
 if(pesquisa_binaria(last, preco))
 {
  printf("%d\n", preco);
  break;
 }

 //se não encontrar, aumenta o preço
 preco++;
}

return 0;
}
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

não é por nada ... mas achas que essa função iterativa é suficientemente correta ?

imagina que N varia, lá vais tu mudar o código todo

eu digo para alterares o teu código para ser mais flexível nesse ponto porque passar o código para recursivo será mais direto

IRC : sim, é algo que ainda existe >> #p@p
Link to comment
Share on other sites

o uso de ciclos dentro dum uma função é chamado método iterativo, logo estou a referir-me ao método utilizador por ti apresentado no primeiro post

PS : a recursividade resolvesse facilmente com uma BFS das moedas possiveis

Edited by HappyHippyHippo
IRC : sim, é algo que ainda existe >> #p@p
Link to comment
Share on other sites

o uso de ciclos dentro dum uma função é chamado método iterativo, logo estou a referir-me ao método utilizador por ti apresentado no primeiro post

não é por nada ... mas achas que essa função iterativa é suficientemente correta ?

imagina que N varia, lá vais tu mudar o código todo

eu digo para alterares o teu código para ser mais flexível nesse ponto porque passar o código para recursivo será mais direto

Não percebi o que queres dizer com, imagina que o N varia.. Sim, o N varia de input para input, e pode ser o máximo de 10 N, mas as iterações conseguem gerar correctamente para essas variaçoes de N, não preciso de mudar o código..

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

o erro foi meu

o que quis dizer foi, se em vez de 4 moedas for outro número qualquer ...

Ah, certo, neste caso isso não acontece, o enunciado diz que a máquina só aceita 4 moedas.. Eu não coloquei o enunciado porque a minha dúvida é mesmo como construir uma função recursiva que me gere as possibilidades, tal como as minhas iterações.. Mas sim tens razão, se esse número variasse a minha solução nunca estaria correcta.

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

BFS é um modelo

tens de imaginar a criação das possibilidades como uma arvore

vou tentar desenhar para um conjunto de N = 3

0
|
+--n1 // (falta n2, n3)
|   |
|   +--n1+n2 // (falta n3)
|   |   |
|   |   +--n1+n2+n3
|   |
|   +--n1+n3 // (falta n2)
|       |
|       +--n1+n3+n2
|
+--n2 // (falta n1, n3)
|   |
|   +--n2+n1 // (falta n3)
|   |   |
|   |   +--n2+n1+n3
|   |
|   +--n2+n3 // (falta n1)
|       |
|       +--n2+n3+n1
|
+--n3 // (falta n1, n2)
   |
   +--n3+n1 // (falta n2)
   |   |
   |   +--n3+n1+n2
   |
   +--n3+n2 // (falta n1)
       |
       +--n3+n2+n1

o que acontece numa BFS, é que em vez de pesquisares {n1} e depois dentro de n1 pesquisares {n1, n2} e {n1, n3} e assim por diante, primeiro pesquosas ao mesmo nível : {n1}, {n2}, {n3}. só depois vais ao interior de cada.

no entanto como existe um limite baixo de profundidade nas soluções (4) podes muito bem implementar por DFS.

Edited by HappyHippyHippo
  • Vote 2
IRC : sim, é algo que ainda existe >> #p@p
Link to comment
Share on other sites

Basicamente, é um algoritmo recursivo para te achar as permutações.

void perm(int idx, int max, int total, int[] list) {
   if (idx == max) {
       // condição de paragem, imprime os idx primeiros elementos
   }
   else {
       int i;
       for (i = idx; i < total; i++) {
           // swap(idx, i)
           perm(idx+1, max, total, list);
           // swap(i, idx)
       }
   }
}

EDIT: Bem... esquece. Li mal o problema. Mas, basicamente, podes fazer as permutações para achar aquelas que são adequadas ao problema em causa.

Edited by KTachyon
  • Vote 1

“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Link to comment
Share on other sites

BFS é um modelo

tens de imaginar a criação das possibilidades como uma arvore

vou tentar desenhar para um conjunto de N = 3

0
|
+--n1 // (falta n2, n3)
| |
| +--n1+n2 // (falta n3)
| | |
| | +--n1+n2+n3
| |
| +--n1+n3 // (falta n2)
| |
| +--n1+n3+n2
|
+--n2 // (falta n1, n3)
| |
| +--n2+n1 // (falta n3)
| | |
| | +--n2+n1+n3
| |
| +--n2+n3 // (falta n1)
| |
| +--n2+n3+n1
|
+--n3 // (falta n1, n2)
|
+--n3+n1 // (falta n2)
| |
| +--n3+n1+n2
|
+--n3+n2 // (falta n1)
|
+--n3+n2+n1

o que acontece numa BFS, é que em vez de pesquisares {n1} e depois dentro de n1 pesquisares {n1, n2} e {n1, n3} e assim por diante, primeiro pesquosas ao mesmo nível : {n1}, {n2}, {n3}. só depois vais ao interior de cada.

no entanto como existe um limite baixo de profundidade nas soluções (4) podes muito bem implementar por DFS.

Eu prefiro uma DFS, já utilizei, ainda não estou muito confortável a criar uma queue para implementar a BFS.. :s

A minah condição de paragem para a DFS seria quando tenho uma soma de 4 moedas, certo?

Basicamente, é um algoritmo recursivo para te achar as permutações.

void perm(int idx, int max, int total, int[] list) {
if (idx == max) {
	// condição de paragem, imprime os idx primeiros elementos
}
else {
	int i;
	for (i = idx; i < total; i++) {
		// swap(idx, i)
		perm(idx+1, max, total, list);
		// swap(i, idx)
	}
}
}

EDIT: Bem... esquece. Li mal o problema. Mas, basicamente, podes fazer as permutações para achar aquelas que são adequadas ao problema em causa.

É uma hipótese, se o dizes, eu vou primeiro tentar uma dfs 🙂

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

gastadeiro

😄

Bem, seria algo como:

se iter == 4

guarda possibilidade soma

exit

loop i de todas as moedas

recursividade(soma+moedas, iter +1)

e perco-me no loop xD, é onde me engasgo sempre, é que assim ele nao gera todas as possibilidades

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

Esse algoritmo parece-me estar correcto, coloca o código para te podermos ajudar melhor a ver o problema.

Outra coisa, precisas mesmo de guardar a possibilidade de soma? Não podes logo fazer a comparação?

"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Link to comment
Share on other sites

Esse algoritmo parece-me estar correcto, coloca o código para te podermos ajudar melhor a ver o problema.

Outra coisa, precisas mesmo de guardar a possibilidade de soma? Não podes logo fazer a comparação?

Eu ainda não fiz o código com dfs, mas tenho aqui o original:

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
int possibilidades[10000];
int compara(const void *a, const void *b)
{
return (*(int*)a-*(int*)b);
}
bool pesquisa_binaria(int fim, int num)
{
int meio, inf, sup;
sup = fim-1;
inf = 0;

while(inf <= sup)
{
 meio = inf+(sup-inf)/2;
 if(num == possibilidades[meio])
  return true;
 if(num > possibilidades[meio])
  inf = meio+1;
 else
  sup = meio-1;
}
return false;
}
int main()
{
int preco, num_moedas, moedas[10], i1, i2, i3 ,i4, last = 0;

//Input
scanf("%d\n%d", &preco, &num_moedas);
for(i1=0; i1<num_moedas; i1++) scanf("%d", &moedas[i1]);

//gera possibilidades com as 4 moedas
for(i1=0; i1<num_moedas; i1++)
 for(i2=i1; i2<num_moedas; i2++)
  for(i3=i2; i3<num_moedas; i3++)
   for(i4=i3; i4<num_moedas; i4++)
 possibilidades[last++] = moedas[i1]+moedas[i2]+moedas[i3]+moedas[i4];

//ordena possibilidades
qsort(possibilidades, last, sizeof(int), compara);   

//procura do preço ideal
while(true)
{
 //se encontrar, imprime e sai do programa
 if(pesquisa_binaria(last, preco))
 {
  printf("%d\n", preco);
  break;
 }

 //se não encontrar, aumenta o preço
 preco++;
}

return 0;
}

@Skiller , tu deves-te lembrar deste problema, é o "Afinal ainda há metro", do topas deste ano..

Penso que não posso comparar logo, porque imagina que quero encontrar o preço 44 . Eu comparo em todas as sequencias que gero e não encontro em nenhuma.. Depois ia ter que aumentar o preço e voltar a fazer a dfs toda..

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

Inicializas uma variavel "Sol" com INT_MAX.

Quando atinge as 4 moedas no dfs verificas se esse valor é pelo menos X (em que X é o preço minimo), se for verificas se o valor da soma é menor que a solução anterior, se for, esta passa a ser nova solução.

Percebeste o que quis explicar?

"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Link to comment
Share on other sites

Inicializas uma variavel "Sol" com INT_MAX.

Quando atinge as 4 moedas no dfs verificas se esse valor é pelo menos X (em que X é o preço minimo), se for verificas se o valor da soma é menor que a solução anterior, se for, esta passa a ser nova solução.

Percebeste o que quis explicar?

Sim, percebi, imaginando que o preço minimo é 44, tenho de verificar sempre se o preço gerado pela dfs é maior ou igual que 44 e menor que a solução anterior.. Assim no final tenho o melhor valor encontrado. Isto, certo??

O meu problema agora é mesmo construir a dfs:

se iter == 4

se soma >= minimo

se soma<sol

altera sol

exit

loop i de todas as moedas

recursividade(soma+moedas, iter +1)

A condição de paragem penso que esteja bem, mas o loop não, porque não testa todas as possibilidades :x

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

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.