• Acasă
  • Despre noi
  • Autori
  • Mărturii
  • Arhivă
  • Trimite Articol
  • Contact

WORLDIT

Lumea în 1 și 0.

  • Știri
    • Tehnologie
    • Tehnologie mobilă
    • Securitate
    • Developers
    • Știință
    • Benzi desenate
    • Jocuri
    • Intern
  • Tehnic
    • Browser
    • C#
    • C/C++
    • Challenge
    • HTML/CSS
    • Javascript, Ajax, jQuery
    • Open Source
    • PHP
    • Python
    • Securitate IT
    • Socializare
    • WordPress
    • Altele
  • Recenzii
  • Interviuri
  • Evenimente

Backtracking – generare permutari si combinari

18
  • Publicat de Andrei Avădănei
  • în C/C++ · Tehnic
  • — 20 mart., 2010 at 8:00 am

Cu 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

Etichete: aranjamentebacktrackingbacktracking in plangcombinarigenerare aranjamentegenerare combinarigenerare permutari

— Andrei Avădănei a scris 1246 articole

Andrei scrie pe worldit.info din vara lui 2011. Este fondatorul Asociatiei Centrul de Cercetare in Securitate Informatica din Romania - CCSIR si coordoneaza DefCamp, cea mai importanta conferinta de securitate informatica & hacking din Europa Centrala si de Est. Andrei ofera in cadrul Bit Sentinel servicii de securitate informatica, penetration testing, security management, recuperarea de pe urma unui atac cibernetic, training-uri si workshop-uri.

  • Articolul anterior Impresii – Deschidere Moisil Iasi
  • Articolul următor BitDefender – greseala imensa

18 Comentarii

  1. claudiu spune:
    aprilie 24, 2010 la 6:34 pm

    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.

  2. Avadanei Andrei spune:
    aprilie 24, 2010 la 11:56 pm

    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. 🙂

  3. Alexandru spune:
    iunie 26, 2010 la 8:03 pm

    Salut,am nevoie de un program c++ care sa genereze grupe de cate 2 a 18 numere cu valoare unica ( sa nu se repete)

  4. Daniel spune:
    noiembrie 15, 2010 la 3:01 pm

    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.

  5. Andrei Avadanei spune:
    noiembrie 16, 2010 la 2:01 pm

    Salut,

    Scrie te rog pe forum ca sa pastram subiectul curat. 🙂

  6. Dan spune:
    martie 7, 2011 la 12:02 am

    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.

  7. Andrei Avădănei spune:
    martie 7, 2011 la 12:23 am

    Linia 15. Daca ai intrebari de algoritmica le poti formula pe http://www.worldit.info/forum.

  8. cora spune:
    mai 5, 2011 la 4:27 pm

    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

  9. dorin spune:
    iunie 25, 2011 la 4:10 pm

    Salutare , as vrea sa stiu cum pot folosi si eu programul acela cu generarea numerelor ,combinari n luate cate k

  10. kraster spune:
    august 24, 2011 la 7:52 pm

    poti face si pt aranjamente?

  11. dacu spune:
    octombrie 10, 2011 la 12:42 am

    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

  12. jorkotina spune:
    mai 23, 2012 la 1:15 am

    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:(;)

  13. dan spune:
    februarie 18, 2013 la 4:05 pm

    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

  14. Deac Seby spune:
    aprilie 19, 2013 la 8:37 pm

    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?

  15. edward spune:
    mai 12, 2014 la 10:50 am

    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).

  16. elissa spune:
    octombrie 11, 2014 la 1:51 am

    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

  17. andrei spune:
    noiembrie 14, 2014 la 2:09 pm

    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?

  18. Ilina Danke Nicu Daniel spune:
    septembrie 8, 2015 la 12:35 am

    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!


  • Facebook

    WorldIT.info
  • Ultimele Atacuri Cibernetice din Romania – RO Hacked

    [wp_rss_retriever url="https://rohacked.bit-sentinel.com/feed/" excerpt="none" items="5" read_more="false" new_window="true" thumbnail="false" cache="0"] RO Hacked este registrul atacurilor cibernetice din România.
  • Caută

  • Articole Recomandate

    • Recent Posts
    • Tags
    • Număr record de participanți la DefCamp 2015, cel mai important eveniment dedicat securității cibernetice din Europe Centrala si de Estdecembrie 2, 2015
    • La DefCamp 2015 vei afla prin ce tehnici pot fi evitate măsurile de securitate ale sistemelor informatice criticeoctombrie 16, 2015
    • Ultima sansa sa rezervi bilete de tip Early Bird la DefCamp 2015septembrie 1, 2015
    • 15 sfaturi despre cum poti deveni un programator bun venite de la specialisti romaniaugust 4, 2015
    • algoritmica Android antivirus Apple Avadanei Andrei benzi desenate BitDefender blog browser C++ Chrome concurs eveniment Facebook Firefox Google google chrome hacking html5 infografic informatica internet Internet Explorer IT javascript linux Microsoft Mozilla Firefox online PHP programare retea sociala review Romania securitate Tehnologie Twitter web Windows Windows 7 Wordpress WorldIT worldit.info Yahoo! YouTube
  • mai 2022
    L Ma Mi J V S D
     1
    2345678
    9101112131415
    16171819202122
    23242526272829
    3031  
    « dec.    
  • Link-uri Sponsorizate

    • laptop second hand

    • Calculatoare Second Hand

    • cod voucher pc garage

  • Home
  • Tehnic
  • C/C++
  • Backtracking – generare permutari si combinari
  • Important

    • Bit Sentinel
    • Centrul de Cercetare în Securitate Informatică din România
    • DefCamp
  • Prieteni

    • BetiT.ro
    • bijuterii handmade
    • Computerica | Resurse gratuite PC
    • Descopera.org
    • Gadgeturi si IT – Giz.ro
  • Prieteni

    • PC – Config
    • RO Hacked
    • Stiri IT

Copyright © 2009-2014 WORLDIT. Toate drepturile Rezervate.
Termeni și condiții | Contact | Licența Creative Commons