•INSiDe123
Strain
Karma: 0
Deconectat
Mesaje: 12
|
|
« : Martie 04, 2009, 17:50:47 » |
|
Sal... Ma cheama andrei .. braila /17 ani /cls 10 Acum ma pregatesc pt oji .. si vreau sa invat backtraking ( nusht daca am scris corect ) si generare de sublultimi . Anu' trecut am ratat calificarea pt ca nu stiam astea.. Am cautat prob rezolvate dar nu am inteles prea bn limbaju.. Plz .. daca aveti vreo aplicatie cu ce am eu nev , in C++ ( de preferat in care sa folositi iostream sau fstream ) .. sau un link ceva .. MS
|
|
|
Memorat
|
|
|
|
•alexandru92
|
|
« Răspunde #1 : Martie 04, 2009, 17:56:09 » |
|
Salut si eu is a 10 . Back e o metoda destul de greu de inteles, la inceput . Acuma trebuie sa intelegi se foloseste cand alta metoda de rezolvare nu exista. Uite pt generare de multimii sper sa inetlegi #include<iostream.h> #include<conio.h> int n,v[10000]; void subm(int); //programul pt backtraking, l-am facut recursiv int main() {clrscr(); cout<<"n="; cin>>n; subm(1); //apelez ca sa pun primul elemnt in vector ;) getche(); } void out(int k) //program de afisare { for(int i=1;i<=k;++i) cout<<v[i]<<" "; cout<<endl; } void subm(int k) //acum incepe "problema" { for(int i=v[k-1]+1;i<=n;++i) //cum toate elementele intr-o submultime trebuie sa fie in ordine crescatoare, logic ca urmatorul element //este de la anterior +1 , nu? { v[k]=i; //il pun in vector out(k); //afisez submultimea astfel creata subm(k+1); //si urc o pozitie } //Acest lucru se repeta pana cand conditia de oprire, evidenta i<=n, nu mai poate fi indeplinita, atunci se revine cu un pas inapoi, datorita //recursivitatii, si daca se poate se pune un alt element pe pozitia respectiva si se urca iaras. Acest lucru se intampla pana cand stiva e goala :)
}
C-am asta e programul Ca sa intelegi mai bine fa un debug pt n=3, sau un numar. Intelegi mai bine asa Poti descrie problema de anul trecut la care ai picat din cauza back-ului?
|
|
« Ultima modificare: Martie 04, 2009, 18:06:50 de către alexandru »
|
Memorat
|
|
|
|
•Mishu91
|
|
« Răspunde #2 : Martie 04, 2009, 18:13:43 » |
|
In arhiva educationala se gasesc problemele Generare de permutari si Combinari. Acolo gasesti sursele oficiale si linkuri catre alte site-uri unde gasesti informatii foarte utile
|
|
|
Memorat
|
|
|
|
•toni2007
|
|
« Răspunde #3 : Martie 04, 2009, 18:14:32 » |
|
Pai presupun ca problema de la judeteana, pluricex . Era singura care se facea cu back.
|
|
|
Memorat
|
|
|
|
•alexandru92
|
|
« Răspunde #4 : Martie 04, 2009, 18:18:33 » |
|
Pai presupun ca problema de la judeteana, pluricex . Era singura care se facea cu back. Nu, nu se face cu back. Am incercat eu.... si pt multe teste depaseste timpul de executie. In rezolvarea oficial propuneau un fel de algoritm succesor
|
|
|
Memorat
|
|
|
|
•Mishu91
|
|
« Răspunde #5 : Martie 04, 2009, 18:20:23 » |
|
Cu back se face... generarea combinarilor
|
|
|
Memorat
|
|
|
|
•gabitzish1
|
|
« Răspunde #6 : Martie 04, 2009, 19:05:26 » |
|
Salut si eu is a 10 . Back e o metoda destul de greu de inteles, la inceput . Acuma trebuie sa intelegi se foloseste cand alta metoda de rezolvare nu exista. Se mai foloseste si pentru a testa corectitudinea unei alte solutii, sau pentru a prinde cateva puncte cand nu reusesti sa rezolvi problema altfel, mai eficient.
|
|
|
Memorat
|
|
|
|
•alexandru92
|
|
« Răspunde #7 : Martie 04, 2009, 19:26:35 » |
|
ok.problema pluricex am testat-o ieri cu back si mi-a dat 40pct.din cauza....ca TIME LIMIT EXCEEDED, acuma acelasi program .........am luat 100, mi se pare doar mie ciudat.........?..plus daca pun if(!a) return 0; i-au 50 pct daca pun if(a==0) return 0; ... i-au 100pct expresiile nu sunt echivalente ? a.......am uitat am folosit evaluatorul de la oji 2008 , sa nu se confunde cu cel de pe sit .
|
|
« Ultima modificare: Martie 04, 2009, 20:31:52 de către alexandru »
|
Memorat
|
|
|
|
•toni2007
|
|
« Răspunde #8 : Martie 04, 2009, 21:07:32 » |
|
Nu stii sa implementezi . S-a luat 100 cu back anul trecut, toate persoanele care le-am intrebat cum au facut de 100 au raspuns ca au facut cu back. Vezi sa nu bagi int in loc de long si sa-ti cicleze pe unele teste.
|
|
|
Memorat
|
|
|
|
•alexandru92
|
|
« Răspunde #9 : Martie 05, 2009, 08:05:53 » |
|
Daca nu stiu sa implementez atunci de ce am luta 100pct la a doua evaluare?........si pe infoarena, desi aici trebuia sa mai optimizez putin ..in clasa a IX nici eu nu stiam back.....si mi se pare o prostie ce au facut, dar asta e offtopic
|
|
|
Memorat
|
|
|
|
•toni2007
|
|
« Răspunde #10 : Martie 05, 2009, 13:08:47 » |
|
Eu ziceam de borland, desi si pe infoarena, cand am scris postul nu luasei 100 daca nu ma insel. Mare atentie la "long" in loc de "int", nu tot ce merge pe infoarena va merge si in borland sau invers.
|
|
|
Memorat
|
|
|
|
•INSiDe123
Strain
Karma: 0
Deconectat
Mesaje: 12
|
|
« Răspunde #11 : Martie 05, 2009, 19:00:03 » |
|
ms mult.. back l-am inteles cam 80% ... si generare submultimi cam la fel...
|
|
|
Memorat
|
|
|
|
•alexandru92
|
|
« Răspunde #12 : Martie 05, 2009, 19:51:51 » |
|
daca l-ai inteles 80%......ce neclaritati ai?... poti sa intrebi
|
|
|
Memorat
|
|
|
|
•INSiDe123
Strain
Karma: 0
Deconectat
Mesaje: 12
|
|
« Răspunde #13 : Martie 06, 2009, 18:29:48 » |
|
cand am zis 80 % ma refeream la faptu ca am inteles cum functioneaza metodele.. insa nu le stapanesc pe deplin.. ms inca odata
|
|
|
Memorat
|
|
|
|
•INSiDe123
Strain
Karma: 0
Deconectat
Mesaje: 12
|
|
« Răspunde #14 : Martie 09, 2009, 10:35:44 » |
|
mai am o intrebare.. o postez tot aici trebuie sa aflu cate combinatii de x pe y pozitii exista .. exemplu : x=2 y=5 avem : x x _ _ _ x _ x _ _ x _ _ x _ x _ _ _ x _ x x _ _ _ x _ x _ _ x _ _ x _ _ x x _ _ _ x _ x _ _ _ x x .. deci in total 10 posibilitati... si am nevoie de o formula.. sau ceva.. am facut cateva exemple si am obs o anumita regula (ceva cu simetrie fata de y/2 ) .. insa nu am putut sa generalizez ..
|
|
|
Memorat
|
|
|
|
•andrei-alpha
Client obisnuit
Karma: 103
Deconectat
Mesaje: 91
|
|
« Răspunde #15 : Martie 09, 2009, 10:51:30 » |
|
Adica in cate moduri poti alege (x+1) numere care dau suma y-x. Asta poti sa faci tot cu back. Faci backul ca si la combinari numai ca la fiecare moment alegi un numarr intre 0 si suma ramasa. De exemplu daca ai x=2 si y=5 si numerele : 2,1,0 asta insemana ca va fi _ _ x _ x. Sper ca ai inteles.
|
|
|
Memorat
|
|
|
|
•INSiDe123
Strain
Karma: 0
Deconectat
Mesaje: 12
|
|
« Răspunde #16 : Martie 09, 2009, 11:38:19 » |
|
ms de sugestie.. dar intre timp am reusit sa fac o functie care calculeaza ce doream ... cred ca e mai rapida decat backul int comb (int a,int b) {if(b==1) return a; if(b==a) return 1; if(b>a) return 0; int x=comb(a-1,b)+comb(a-1,b-1); return x; }
|
|
|
Memorat
|
|
|
|
•toni2007
|
|
« Răspunde #17 : Martie 09, 2009, 12:15:41 » |
|
Ce faci tu acolo e triunghiul lui pascal . Poti face mai rapid, cu programare dinamica: for (i = 1; i <= N; ++ i) for (j = 1; j <= i; ++ j) C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
(Initializezi la fel ca la functie matricea). Cand vei avea nevoie de Combinari de N luate cate K, iei C[N][K] din matrice. Tot asa poti face cu memoizare: int memo(int N, int K) { if (cache[N][K] != -1) return cache[N][K]; return cache[N][K] = memo(N - 1, K) + memo(N - 1, K - 1); }
Aici trebuie initializata matricea cu -1 peste tot, in afara de acele initializari de la prima.
|
|
|
Memorat
|
|
|
|
•devilkind
|
|
« Răspunde #18 : Martie 09, 2009, 12:28:37 » |
|
asta faci daca ai nevoie de mai multe combinari. Dar daca te intereseaza doar combinari de N luate cate K exista formula:
C = N! / (K! * (N - K)!)
(N! = N factorial = 1 * 2 * 3 ... * N)
|
|
|
Memorat
|
|
|
|
•INSiDe123
Strain
Karma: 0
Deconectat
Mesaje: 12
|
|
« Răspunde #19 : Martie 10, 2009, 12:30:01 » |
|
ms la amundoi pt idei.. formula aceea o cautam eu
|
|
|
Memorat
|
|
|
|
•INSiDe123
Strain
Karma: 0
Deconectat
Mesaje: 12
|
|
« Răspunde #20 : Martie 13, 2009, 19:37:44 » |
|
inca o intrebare cum fac un back.. care genereaza combinatii de numere de la x la n .. luate cate k , unde n<k ex: pt x=0,n=1,k=5 00000 10110 11100 etc
|
|
|
Memorat
|
|
|
|
•alexandru92
|
|
« Răspunde #21 : Martie 13, 2009, 20:23:06 » |
|
void back(int c) { if(c==k+1) out(c); else for(int i=x;i<=n;++i) {v[c]=i; back(c+1); } }
[later] nu l-am incercat pe pc .....deci de siguranta mai bine ii dai cateva teste
|
|
« Ultima modificare: Martie 13, 2009, 20:28:51 de către alexandru »
|
Memorat
|
|
|
|
•chera_lary
|
|
« Răspunde #22 : Martie 13, 2009, 23:31:32 » |
|
Nu, nu se face cu back. Am incercat eu.... si pt multe teste depaseste timpul de executie. Ba da! Merge cu back! Am rezolvat-o cu back si am luat 100 de puncte pe ea! Bine asta dupa ce am ajuns acasa!
|
|
|
Memorat
|
|
|
|
|