polska Posted August 1, 2012 at 02:46 PM Report Share #471213 Posted August 1, 2012 at 02:46 PM (edited) 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 August 1, 2012 at 02:48 PM 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 More sharing options...
HappyHippyHippo Posted August 1, 2012 at 02:56 PM Report Share #471214 Posted August 1, 2012 at 02:56 PM 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 Portugol Plus Link to comment Share on other sites More sharing options...
polska Posted August 1, 2012 at 03:07 PM Author Report Share #471215 Posted August 1, 2012 at 03:07 PM 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 Estas a falar da função recursiva ou da maneira que eu fiz? 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 More sharing options...
HappyHippyHippo Posted August 1, 2012 at 03:08 PM Report Share #471216 Posted August 1, 2012 at 03:08 PM (edited) 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 August 1, 2012 at 03:11 PM by HappyHippyHippo IRC : sim, é algo que ainda existe >> #p@p Portugol Plus Link to comment Share on other sites More sharing options...
polska Posted August 1, 2012 at 03:13 PM Author Report Share #471217 Posted August 1, 2012 at 03:13 PM 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 More sharing options...
HappyHippyHippo Posted August 1, 2012 at 03:15 PM Report Share #471218 Posted August 1, 2012 at 03:15 PM o erro foi meu o que quis dizer foi, se em vez de 4 moedas for outro número qualquer ... IRC : sim, é algo que ainda existe >> #p@p Portugol Plus Link to comment Share on other sites More sharing options...
polska Posted August 1, 2012 at 03:20 PM Author Report Share #471219 Posted August 1, 2012 at 03:20 PM 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 More sharing options...
HappyHippyHippo Posted August 1, 2012 at 03:30 PM Report Share #471220 Posted August 1, 2012 at 03:30 PM ok, se o enunciado o diz, estás na boa. nesse caso : PS : a recursividade resolvesse facilmente com uma BFS das moedas possiveis tens ainda a facilidade de terminar a recursividade quando existem 4 moedas selecionadas IRC : sim, é algo que ainda existe >> #p@p Portugol Plus Link to comment Share on other sites More sharing options...
polska Posted August 1, 2012 at 03:42 PM Author Report Share #471223 Posted August 1, 2012 at 03:42 PM ok, se o enunciado o diz, estás na boa. nesse caso : tens ainda a facilidade de terminar a recursividade quando existem 4 moedas selecionadas Uma bfs foi algo que ainda não codei 😄 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 More sharing options...
HappyHippyHippo Posted August 1, 2012 at 03:56 PM Report Share #471224 Posted August 1, 2012 at 03:56 PM (edited) 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 August 1, 2012 at 03:56 PM by HappyHippyHippo 2 Report IRC : sim, é algo que ainda existe >> #p@p Portugol Plus Link to comment Share on other sites More sharing options...
KTachyon Posted August 1, 2012 at 03:58 PM Report Share #471225 Posted August 1, 2012 at 03:58 PM (edited) 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 August 1, 2012 at 04:01 PM by KTachyon 1 Report “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 More sharing options...
polska Posted August 1, 2012 at 07:58 PM Author Report Share #471239 Posted August 1, 2012 at 07:58 PM 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 More sharing options...
HappyHippyHippo Posted August 1, 2012 at 08:30 PM Report Share #471240 Posted August 1, 2012 at 08:30 PM A minah condição de paragem para a DFS seria quando tenho uma soma de 4 moedas, certo? pelo que dizes, sim. agora não sei que liberdade tens de arranjar uma solução com menos de 4 moedas ... IRC : sim, é algo que ainda existe >> #p@p Portugol Plus Link to comment Share on other sites More sharing options...
polska Posted August 1, 2012 at 10:25 PM Author Report Share #471248 Posted August 1, 2012 at 10:25 PM pelo que dizes, sim. agora não sei que liberdade tens de arranjar uma solução com menos de 4 moedas ... não tenho 😄 , tem de ser 4 moedas. 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 More sharing options...
HappyHippyHippo Posted August 1, 2012 at 10:26 PM Report Share #471249 Posted August 1, 2012 at 10:26 PM não tenho 😄 , tem de ser 4 moedas. gastadeiro IRC : sim, é algo que ainda existe >> #p@p Portugol Plus Link to comment Share on other sites More sharing options...
polska Posted August 1, 2012 at 10:31 PM Author Report Share #471251 Posted August 1, 2012 at 10:31 PM (edited) 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 August 1, 2012 at 10:35 PM 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 More sharing options...
skiller10 Posted August 1, 2012 at 11:00 PM Report Share #471252 Posted August 1, 2012 at 11:00 PM 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 More sharing options...
polska Posted August 1, 2012 at 11:52 PM Author Report Share #471254 Posted August 1, 2012 at 11:52 PM 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 More sharing options...
skiller10 Posted August 2, 2012 at 03:43 PM Report Share #471300 Posted August 2, 2012 at 03:43 PM 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 More sharing options...
polska Posted August 2, 2012 at 08:10 PM Author Report Share #471319 Posted August 2, 2012 at 08:10 PM (edited) 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 August 2, 2012 at 08:11 PM 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 More sharing options...
Recommended Posts
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 accountSign in
Already have an account? Sign in here.
Sign In Now