Backtracking probleme rezolvate

1. PERMUTĂRI. Se citeşte un număr natural N. Să se genereze permutările mulţimi {1, 2, …, N};

2. ARANJAMENTE. Se citesc două numere naturale N şi P (P<=N). Să se genereze toate submulţimile mulţimii {1, 2, …, N} de câte P elemente. Două submulţimi cu aceleaşi elemente la care ordinea acestora diferă sut considerate distincte. Mulţimea {1, 2, 3} este diferită de mulţimea {1, 3, 2}

3. COMBINĂRI. Se citesc două numere naturale N şi P (P<=N). Să se genereze toate submulţimile mulţimii {1, 2, …, N} de P elemente. Două submulţimi se consideră egale, dacă şi numai dacă au aceleaşi elemente, indiferent de ordinea în care acestea apar. Mulţimea {1, 2, 3} NU este diferită de mulţimea {1, 3, 2}

4. PERMUTĂRI GENERALE. Se citeşte N natural. Se citesc N numere întregi distincte. Să se genereze permutările mulţimii formate din numerele citite.

5. PERMUTĂRI DE CUVINTE. Se citeşte N natural. Se citesc N cuvinte. Să se genereze permutările mulţimii formate din cuvintele citite.

6. DAME. Se citeşte N natural. Să se aşeze N dame pe o tablă de şah de dimensiune N astfel încât oricare două dintre cele N dame să nu se atace. Două dame se atacă dacă sunt pe aceeaşi linie sau pe aceeaşi coloană sau pe aceeaşi diagonală.

7. PRODUS CARTEZIAN. Se citeşte N natural. Să se genereze produsul cartezian {1, 2, …, N} X {1, 2, …, N} X … X{1, 2, …, N} (de N ori).

8. PRODUS CARTEZIAN a N mulţimi cu câte M elemente. Se citeşte N natural. Se citesc N mulţimi: A1, A2, …, AN, fiecare conţinând câte M elemente (elementele unei mulţimi sunt distincte). Să se genereze produsul cartezian A1 X A2 X … AN.

9. PRODUS CARTEZIAN GENERAL. Se citeşte N natural. Se citesc N mulţimi: A1, A2, …, AN, conţinând k1, k2, …kN elemente (elementele unei mulţimi sunt distincte). Să se genereze produsul cartezian A1 X A2 X … AN.

10. ŞIR DE 0 SI 1. Să se genereze toate şirurile de numere de lungime N formate doar din elemente 0 şi 1.

11. DRAPELE TRICOLORE. Avem la dispoziţie 6 culori: alb, galben, roşu, verde, albastru, negru. Să se precizez toate drapelele tricolore care se pot proiecta, ştind că trebuie respectate următoarele reguli: (Regula 1:) orice drapel are culoarea din mijloc galben sau verde, (Regula 2: ) cele trei culori de pe drapel sunt distincte.

12. PARANTEZE. Se dă un număr natural N par. Să se determine toate şirurile de N paranteze care se închid corect. Exemplu: N =6 ((( ))), (( )( )), ( )( )( ), ( )(( )), (( ))( )

13. SUBMULŢIMILE UNUI MULŢIMI. Se consideră o mulţime A cu N elememte întregi. Să se genereze toate submulţimile acestei mulţimi. Mulţimea vidă este submulţime a oricărei mulţimi. Orice mulţime A este considerată submulţime a mulţimii A.

14. PARTIŢIILE UNEI MULŢIMI. Se consideră mulţimea A= {1, 2, …, N}. Se cer toate partiţiile acestei mulţimi. Submulţimile A1, A2, …, Ak constituie o partiţie a mulţimii A dacă sunt disjuncte între ele şi reuniunea lor este mulţimea A. Exemplu: o partiţie a mulţimii {1, 2, 3} este {1, 2} U {3}.

15. PROBLEMA COLORĂRII HARŢILOR. Find dată o hartă cu N ţări, se cer toate soluţiile de colorare a hărţii utilizând maxim 4 culori, astfel încât oricare dintre două ţări cu frontieră comună să fie colorate cu culori diferite.

16. PROBLEMA COMIS-VOIAJORULUI. Un comis-voiajor trebuie să viziteze un număr de N oraşe. Iniţial acesta se află într-unul din ele notat 1. Comis-voiajorul doreşte să nu treacă de două ori prin acelaşi oraş iar la întoarcere să revină în oraşul 1. Cunoscând legăturile dintre oraşe, se cere să se tipărească toate drumurile poibile pe care le poate efectua comis-voiajorul.

17. PROBLEMA PLĂŢII unei sume S utilizând N tipuri de monede. Se dau: suma S şi N tipuri de monede având valorile: a1, a2, .., an lei. Se cer toate modalităţile de plată exactă a sumei S utilizând aceste monede.

18. PARTIŢIILE UNUI NUMĂR NATURAL. Se citeşte un număr natural N. Se cere să se tipărească toate modurile de descompunere a sa ca sumă de numere naturale (Exemplu: pentru numărul 4: 1111, 112, 121, 13, 211, …).

19. DESCOMPUNERE. Să se decompună un număr natural N în toate modurile posibile ca sumă de p numere naturale distincte. (p<=N).

20. DESCOMPUNERE CA SUMA DE NUMERE PRIME. Fiind dat un număr natural N, se cere să se afişeze toate descompunerile numărului respectiv ca sumă de numere prime.

21. DELEGAŢII. Dintr-un grup de N persoane, dintre care p femei, trebuie formată o delegaţie de K persoane, din care L femei. Să se precizeze toate delegaţiile care se pot forma.

22. ARANJAMENTE DE LITERE. Se citesc de la tastatură două numere naturale N şi P. (0<N<P<12). Să se afişeze toate şirurile de P litere distincte, litere alese dintre primele N litere mari ale alfabetului englez. De exemplu pentru N=4 şi P=2: AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC.

23. DESCOMPUNERE ÎN NUMERE CONSECUTIVE. Se dă un număr natural N > 5 . Să se afişeze toate descompunerile lui N ca sumă de numere naturale consecutive.

24. COTROCENI. La palatul COTROCENI se ţine o conferinţă de presă la care trebue să ia cuvântul 5 purtători de cuvânt numiţi A, B, C, D, E. Afişaţi toate modurile de înscriere la cuvânt astfel încât persoana A să vorbească mai târziu decât persoana D şi persoana E să fie printre primele trei persoane care vorbesc.

25. SUBMULŢIMI DE SUMA S. Să se genereze toate submulţimile de câte M elemente ale unei mulţimi de N elemente pentru care suma elementelor să nu depăşească o valoare maximă Smax.