Backtracking – generare permutari si combinari
18Cu totii stim ca Backtracking este una din cele mai cunoscute tehnici de programare. Ideea din spatele acestui algoritm este de a genera toate solutiile posibile si a le abandona in cazul in care observa ca nu indeplinesc conditiile necesare. Datorita generarii tuturor solutiilor, complexitatea algoritmului este foarte mare, dar duce sigur la generarea tuturor posibilitatilor valide. Din aceasta cauza, e o tehnica foarte cunoscuta in randul programatorilor (in special a celor care participa la concursuri si olimpiade de informatica) deoarece este considerata solutia ce trebuie abordata in cazul in care nu ai nici o idee.
Structura unei functii backtracking
void back(int k) { if(reject_sol(k)) return; if(accept_sol(k)) show_sol(k); for(i=0;i<n;i++) { v[k]=set(); back(k+1); v[k]=unset(); } }
Generarea tuturor permutarilor
Problema : Sa se genereze toate permutarile multimii {1, 2, …N}, in ordine lexicografica.
Solutie : Din moment ce problema ne cere generarea tuturor solutiilor, este evident ca vom avea nevoie de o abordare backtracking.
#include<cstdio> int a[10],b[10]; void back(int k,int len) { if(k-1 == len) //afisam solutia { for(int i = 1; i <= len;i++) printf("%d ",a[i]); printf("\n"); } else { for(int i = 1; i <= len; i++) if(!b[i]) //daca valoarea nu-i folosita { a[k] = i; b[i] = 1; //o folosim back(k+1,len); //trecem la pasul urmator b[i] = 0; //o eliberam } } } int main() { freopen("permutari.in","r",stdin); freopen("permutari.out","w",stdout); int n; scanf("%d",&n); back(1,n); fclose(stdin); fclose(stdout); return 0; }
Generarea tuturor combinarilor de n luate cate k
Problema : Sa se genereze toate combinarile de N luate cate K in ordine lexicografica.
Solutie : Din moment ce si aceasta problema ne cere generarea tuturor posibilitatilor este evident ca solutia este una ce are nevoie de o abordare backtracking.
#include<cstdio> int a[19],b[19]; void back(int k,int len,int max) { if(k-1 == max) //afisam solutia { for(int i = 1; i <= max;i++) printf("%d ",a[i]); printf("\n"); } else { for(int i = 1; i <= len; i++) if(!b[i] && a[k-1] < i) //ne asiguram ca generam solutiile crescatoare si unice { a[k] = i; b[i] = 1; //o folosim back(k+1,len,max); //trecem la pasul urmator b[i] = 0; //o eliberam } } } int main() { freopen("combinari.in","r",stdin); freopen("combinari.out","w",stdout); int n,k; scanf("%d %d",&n,&k); back(1,n,k); fclose(stdin); fclose(stdout); return 0; }
Aplicatii Backtracking
1. Generarea aranjamentelor
2. Problema damelor
3. Problema turelor
4. Generarea produsului cartezian a n multimi
5. Sa se genereze n perechi de parantezari care se inchid corect
6. Cel mai lung prefix
Concluzie
Aceasta metoda este extrem de raspandita si de utila in cazul problemelor in care generarea tuturor solutiilor este necesara. De asemenea, in cazul concursurilor este una din cele mai populare modalitati de „furare” a catorva puncte.
Referinte
http://infoscience.3x.ro/c++/pbbacktracking.html http://infoarena.ro/problema/combinari http://infoarena.ro/problema/permutari http://en.wikipedia.org/wiki/Backtracking http://www.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch19.html
Salut Andrei!
Te vad baiat istet si pari priceput intr-ale informaticii poti sa ma ajuti cu un program care sa-mi desfasoare 13 /14 numere luate cate 6,iar numerele sa fie afisate in ordine crescatoare?
Am nevoie de asta pentru a finaliza o schema redusa loto cu 49 de numere care sa poata fi jucata de un grup mai mare de persoane.
De asemenea am nevoie si de un program care sa-mi arate si cate variante cu 4,5,6 numere au iesit din schema si care sunt acele variante.Eventual sa-mi afiseze nr de ordine.Sa-mi indice variantele castigatoare si cate sunt.
Schema e finalizata am nevoie de ce ti-am scris.
Poate colaboram daca esti interesat si nu esti ocupat.
Poate fi profitabila colaborarea in viitor.Cine stie!
Te saluta un batran.
Generarea acelor valori de 13/14 numere luate cate 6 este chiar aplicatia a doua ce face exact ceea ce doresti. Stabilesti n si k in fisierul de intrare si in cel de iesire va genera tot.
13 6
Legat de acele variante, nu am inteles dorinta. 🙂
Salut,am nevoie de un program c++ care sa genereze grupe de cate 2 a 18 numere cu valoare unica ( sa nu se repete)
Salut.
Deci am problema asta la info si nu imi mai amintesc backtrackingul decat structura generala 🙁
There are n cubes, each of them characterized by its color and the length of the edge.
Generate, with some of these cubes, a maximum height tower, under the following conditions:
a) a cube is placed on another only if its edge length is less than the edge length of the cube
placed bellow it.
b) two neighboring cubes must have different colors.
Salut,
Scrie te rog pe forum ca sa pastram subiectul curat. 🙂
Salut Andrei !
Vreau sa-ti cer ajutorul. Ce trebuie modificat in programul care genereaza combinarile pentru a le filtra. De exemplu vreau sa renunt la cele care au 3 numere consecutive (sau mai multe). Care ar fi conditia si unde trebuie adaugata in program.
Multumesc anticipat.
Linia 15. Daca ai intrebari de algoritmica le poti formula pe http://www.worldit.info/forum.
buna, am si eu de facut o prb ptr atesta cu loto si chiar nu am idee cum se face,ai putea sa ma ajuti?:D
Salutare , as vrea sa stiu cum pot folosi si eu programul acela cu generarea numerelor ,combinari n luate cate k
poti face si pt aranjamente?
salut…..
sper sa ma intelegi in ce vreau sa iti spun, nu ma pricep la info….as dorii daca se poate un program in care sa adaug eu 20- 25 numere si sa imi faca combinatii de cate 6….generatoare de numere am gasit la infinit, dar unul in care sa imi combine numerele alese de mine, nu
Salut,asi vrea sa stiu daca se poate sa scoat toate combinatiile din 6 meciuri(pariuri sportive) cum asi putea sa fac acest lucru ?:(te rog mult daca stii ajuta-ma:(;)
sal ! spune mi te rog cum combin 13 nr pe var de 5 nr sa am sanse 70_80%castig ! tu esti foarte bun la cifre sa dea d zeu sa fii sanatos si sa progresezi in continuare
salut am si eu o mica intrebare: am 6 meciuri de fotbal, si pot sa aleg intre 1,x,2( adica castiga echipa gazda, egal, castiga echipa oaspete), cum pot sa aflu care sut toate variantele posibile, care pot sa iasa?
ai putea face un program care sa genereze toate combinatiile posibile cu urmatoarele elemente: (0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f,g) luate cate 32 de exemplu: (d41b5efe700ca03574f865fc9da81313)(asta ar fi o aranjare).
Buna Andrei
Ma poti ajuta si pe mine cu folosirea programului de generare a combinatiilor posibile cu 6 cifre de la 0-9.Am nevoie ugent,ti-as fi foarte recunocatoare daca m-ai putea ajuta.Multumesc
salut ,am 6 meciuri si cate 3 pronosticuri posibile la fiecare meci dar eu trebuie sa aleg doar un pronostic la fiecare meci si vreau sa stiu cate combinatii posibile exista?
Am si eu o intrebare: am un examen de dat la care am 6 intrebari cu cate 3 raspunsuri posibile dintre care doar unul este corect, cate variante sau mai bine zis combinatii de raspuns exista?
Mc frumos!