cine imi rezolva si mie tema pe vacanta la info?

        

Temă Backtracking

1. Se citesc de la tastatură un număr natural n şi un număr natural v (v<n). Să se scrie un program care afişează toate numerele de la 1 la n în toate modurile posibile astfel încât între oricare două numere succesive diferenţa în modul să fie mai mare decât v.
2. La un festival de muzică pop, s-au înscris n melodii, codificate 1,2,3,…,n (n>=4). Să se afişeze toate posibilităţile de a stabili ordinea intrării în concurs a melodiilor, ştiind că melodiile m1 şi m2 trebuie să evolueze a doua, respectiv penultima (m1, m2
   {1, 2,…, n}).
3. Să se afişeze toate posibilităţile de aranjare pe o casetă a n melodii, codificate cu numere naturale de la 1 la n, astfel încât melodia x să se cânte după melodia y.
4. Să se genereze toate numerele formate din n cifre distincte (n<10). Ex.: n=2, se vor afişa numerele: 10,12,13,…,98.
5. Să se genereze toate numerele de lungime n „strict crescătoare”, adică numerele care au cifre distincte şi strict crescătoare. Ex. : pt. n=2, 12, 13, 14, 15,…, 23, 24,…., 89.
6. Să se afişeze toate numerele de n cifre ale căror prefixe sunt divizibile cu 2. Ex.: n=3, se vor afişa numerele: 200,202,204,…,886,888.
7. Se consideră un număr natural n. Să se afişeze toate numerele care se pot obţine prin reaşezarea cifrelor numărului dat. Indicaţie : Se construieşte vectorul cifrelor numărului în stivă se vor pune indicii vectorului. Ex. n=31872 à v=(2,7,8,1,3), nc=5 (nc numărul de cifre), pe stivă vom pune indicii {1,2,…,nc}.
8. Să se afişeze toate permutările unei mulţimi formate din n numere naturale a1, a2,…,an citite dintr-un fişier de intrare. Indicaţie : în stivă se vor pune indicii vectorului {1,2,…,n}.
9. Să se afişeze toate modurile de aranjare a elementelor unui şir dat de n numere întregi, astfel încât în şirul rezultat să nu existe două elemente alăturate negative. Indicaţie : în stivă se vor pune indicii vectorului {1,2,…,n}.
10. Să se genereze toate şirurile de lungime n formate numai din literele A şi M, şirurile să nu aibă două litere de A alăturate. Ex.: pt. n=3 avem: MMM, AMM, MAM, MMA, AMA. Indicaţie : se vor codifica Aà1, Mà2 ; se va pune în stivă mulţimea {1,2}.
11. Se consideră un număr natural n. Să se genereze toate şirurile distincte formate din numere din mulţimea {1,2, …,n}, cu n<10, pentru care valorile impare se găsesc pe poziţii impare. Ex. n=4 soluţiile sunt: 1 2 3 4, 1 4 3 2, 3 2 1 4, 3 4 2 1.
12. Să se genereze toate numerele prime de n cifre formate numai cu ajutorul cifrelor {0,2,9}. Valoarea numărului natural n se va citi de la tastatură. Ex. n=3, se vor afişa: 229, 929.
13. Să se genereze toate şirurile de n cifre nenule pentru care oricare două cifre alăturate sunt fie ambele pare fie ambele impare. Ex. n=2 , se vor afişa: 11, 13, 15, 17, 19, 22, 24, 26, 28, 33, 35, 37, 39, 44, 46, 48, etc.
14. Să se afişeze toate posibilităţile de a aranja elementele unei mulţimi formate din n numere naturale a1, a2,…,an citite dintr-un fişier de intrare în grupe de p elemente distincte.
15. Se citesc de la tastatură două numere naturale n şi m (0<m<12). Să se afişeze toate şirurile de n litere distincte, litere alese dintre primele m ale alfabetului englez.  Ex pentru n=2 şi m=4 se afişează, nu neapărat în această ordine, şirurile: AB, BA, AC, CA, AD, DA, BC, CB, BD, DB, CD.
16. Să se genereze toate şirurile strict crescătoare formate din numere naturale cu proprietatea că primul element din şir este n, iar ultimul este n+p. Numerele naturale n şi p sunt citite de la tastatură. Ex. n=7, p=3, se vor afişa nu neaoărat în această ordine: 7 8 9 10, 7 8 10, 7 9 10, 7 10.
17. Să se genereze toate şirurile distincte de n (n<=6) note muzicale din mulţimea {do, re, mi, fa, sol, la, si}.
18. Să se afişeze toate numerele de câte n cifre (0<n<=10) cu suma cifrelor egală cu S valoare întreagă dată.

19.  Orice număr natural se poate scrie ca sumă de termeni numere naturale nenule. Astfel 4=3+1= 2+2= 2+1+1= 1+1+1+1, deci în patru moduri. Să se scrie numărul n ca sumă de numere naturale şi să se afişeze numărul de posibilităţi descoperite

1. Fiind dat un număr natural pozitiv n, să se producă la ieşire toate descompunerile sale ca sumă de numere prime.
2. Se citeşte n număr natural. Să se afişeze toate numerele naturale formate din cifre distincte nenule care sunt mai mici decât n şi care au aceeaşi sumă ca n. Ex. n=312, se vor genera: 123, 132, 15, 213, 231, 24, 42, 51, 6.
3. Orice număr natural impar poate fi descompus în suma de numere pare +1. Astfel numărul 9 poate fi scris astfel: 1+2+2+2+2, 1+2+2+4, 1+2+6, 1+4+4, 1+8. Pentru un număr natural n citit să se genereze după acelaşi procedeu toate posibilităţile de descompunere.
4. Să se genereze folosind metoda backtracking recursiv toate posibilităţile de aranjare a n (număr par) paranteze rotunde astfel încât ele să formeze o succesiune corectă (oricărei paranteze rotunde închise să-i corespundă o paranteză rotundă deschisă care să-i preceadă).
5. Fiind dat un număr natural pozitiv n, să se producă la ieşire toate descompunerile sale ca sumă de numere prime. Ex. n=10, descompunerile posibile sunt: 2+2+2+2+2, 2+2+3+3, 2+3+5, 5+5.
6. Se consideră un şir cu n elemente numere întregi a1, a2,…,an.  Să se determine toate posibilităţile de alegere a semnelor + şi – pentru care ±a1±a2±…±an=S, cu S număr întreg citit de la tastatură.

26.  Se consideră n oraşe numerotate de la 1 la n. Un comis voiajor trebuie să-şi prezinte produsele în toate cele n oraşe plecând dintr-un oraş x, trecând o singură dată prin fiecare oraş şi întorcându-se în oraşul din care a plecat. Ştiind reţeaua de drumuri de acces ce leagă oraşele (aflată într-un fişier de intrare „oraşe.in”) să se afişeze toate traseele posibile.

1. Se citesc 9 denumiri de culori (maximum 16 caractere fiecare) din care trebuie să se alcătuiască toate drapelele tricolore posibile, cu condiţia ca la mijloc să fie numai o culoare din ultimele două citite. Fiecare soluţie va apărea pe rând, câte una, la cererea utilizatorului (acţionarea unei taste).

28.  Se cere să se coloreze o hartă cu n ţări, folosindu-se numai 4 culori, oricare două ţări vecine să fie colorate diferit. Harta este reţinută într-un fişier de intrare „tara.in” sub forma unei matrici, unde elementele matricii au valoarea 1 dacă ţara i este vecină cu ţara j şi 0 în caz contrar.29.  Se consideră n număr natural dat. Se cere să se genereze toate submulţimile mulţimii {1,2, …,n}.Ex.: n=3 submulţimile sunt: {1};{2};{3};{1,2};{1,3};{2,3};{1,2,3}30.  Se consideră n intervale întregi identificate prin cele două capete (x,y). Să se genereze toate secvenţele de intervale cu reuniunea vidă. Ex. n=3, şi intervalele: (2,5), (3,6), (7,10) se vor afişa soluţiile: (2,5) (7,10);  (3,6) (7,10).

1. Se citeşte de la tastatură un număr natural n<=14, care reprezintă dimensiunea unei table de şah. Să se genereze toate modalităţile de aranjare pe tablă a n ture, astfel încât oricare două ture să nu se atace. Rezultatele se vor afişa în fişierul ture.txt.
2. Se citeşte de la tastatură un număr natural n<=14, care reprezintă dimensiunea unei table de şah. Să se genereze toate modalităţile de aranjare pe tablă a n regine, astfel încât oricare două regine să nu se atace. Rezultatele se vor afişa în fişierul regine.txt.

No Comments

No comments yet.

Comentarii RSS URI identificator TrackBack

Lăsați un comentariu

Name (necesar)

Mail (will not be published) (necesar)

Website