PROBLEME LA METODA BACKTRACKING

1. Generarea permutărilor

Se citeşte un număr natural n. Să se genereze permutările de n elemente ale mulţimii {1,2,…,n}.

Simulaţi executarea algoritmului pentru n=3.

2. Problema turelor

Să se determine toate posibilităţile de aranjare a n ture pe o tablă de şah de dimensiune nxn astfel

încât turele să nu se atace reciproc. Tura atacă piesele aflate pe aceeaşi linie sau coloană.

3. Problema reginelor

Să se determine toate posibilităţile de aranjare a n regine pe o tablă de şah de dimensiune nxn

astfel încât reginele să nu se atace reciproc. Regina atacă piesele aflate pe aceeaşi linie, coloană

sau diagonală.

4. Generarea produsului cartezian

Se citesc numerele naturale n şi p. Să se genereze toate elementele produsului cartezian

P=AxAx...xA=Ap, unde A={1,2,…,n}.

5. Generarea aranjamentelor

Se citesc două numere naturale n şi p. Să se genereze toate aranjamentele de n elemente luate

câte p ale mulţimii {1,2,…,n}. Simulaţi executarea algoritmului pentru n=4 şi p=2.

6. Generarea combinărilor

Se citesc două numere naturale n şi p. Să se genereze toate combinările de n elemente luate câte

p ale mulţimii {1,2,…,n}. Simulaţi executarea algoritmului pentru n=4 şi p=2.

7. Generarea submulţimilor

Se citeşte numărul natural n. Să se genereze toate submulţimile mulţimii {1,2,…,n}.

Simulaţi executarea algoritmului pentru n=3.

8. Generarea partiţiilor unui număr natural

Se citeşte numărul natural n. Să se genereze toate modurile de descompunere a lui n ca sumă de

numere naturale. Simulaţi executarea algoritmului pentru n=5.

9. Generarea partiţiilor

Fie mulţimea A={1,2,…,n}. Se numeşte partiţie a mulţimii A, un set de kn mulţimi care îndeplinesc

condiţiile de mai jos:

a) A1UA2U…UAk=A

b) AiAj=, i,j{1,2,…,n}

10. Plata unei sume cu bancnote de valori date

Se dau suma S şi n tipuri de bancnote având valori a1,a2,…,an lei. Se cer toate modalităţile de plată

a sumei S utilizând aceste bancnote. Se presupune că se dispune de un număr suficient din fiecare

tip de bancnotă.

11. Problema colorării hărţilor

Fiind data o hartă cu n ţări, se cere toate soluţiile de colorare a hărţii, utilizând cel mult 4 culori,

astfel încât două ţări cu frontieră comună să fie colorate diferit.

12. Generarea permutărilor unui vector

Se citesc cele n elemente ale unui vector a de numere întregi. Să se genereze permutările de n

elemente ale mulţimii {a1,a2,…,an}. Simulaţi executarea algoritmului pentru n=3.

13. Generarea produsului cartezian a n mulţimi

Se citesc numărul de elemente a n mulţimi A1, A2,...An în vectorul a=(a1,a2,...,an). Să se genereze

toate elementele produsului cartezian P=A1xA2x...xAn, unde Ai={1,2,…,ai}.

14. Generarea aranjamentelor de n elemente luate câte p ale unui vector

Se citesc cele n elemente ale unui vector şi numărul natural p. Să se genereze toate aranjamentele

de n elemente luate câte p ale mulţimii {a1,a2,…,an}. Simulaţi executarea algoritmului pentru n=4

şi p=2.

15. Generarea combinărilor de n elemente luate câte p ale unui vector

Se citesc cele n elemente ale unui vector şi numărul natural p. Să se genereze toate combinările de

n elemente luate câte p ale mulţimii {a1,a2,…,an}. Simulaţi executarea algoritmului pentru n=4 şi

p=2.

16. Generarea submulţimilor unei mulţimi

Se citesc cele n elemente ale unei mulţimi reprezentată prin vectorul a. Să se genereze toate

submulţimile mulţimii {a1,a2,…,an}. Simulaţi executarea algoritmului pentru n=3.

17. Generarea partiţiilor unei mulţimi

Se citesc cele n elemente ale unei mulţimi reprezentată prin vectorul a. Să se genereze toate

partiţiiile mulţimii {a1,a2,…,an}. Simulaţi executarea algoritmului pentru n=3.

18. Anagrame

Se citeşte un cuvânt cu n litere. Se cere să se tipărească toate anagramele cuvântului citit. O

anagram a unui cuvânt reprezintă o rearanjare a literelor care formează cuvântul, astfel încât să

obţinem un cuvânt diferit, dar care are aceleaşi litere.

19. Ecuaţie cu numere naturale

Folosind metoda backtracking găsiţi toate soluţiile natural ale ecuaţiei: 3x+y+4xz=100.

20. Şiruri de 0 şi 1

Se citesc două numere naturale a şi b, reprezentând numărul de cifre de 1 şi respectiv de 0 dintr-un

şir de lungime a+b. Să se genereze toate şirurile de lungime a+b care pot fi formate respectând

această regulă, precum şi numărul acestora. Simulaţi executarea algoritmului pentru a=2 şi b=3.

21. Generarea şirurilor de paranteze

Se dă un număr natural n. Să se determine toate şirurile de paranteze care se închid correct.

Simulaţi execuţia algoritmului pentru n=6.

22. Săritura calului

Se consideră o tablă de şah nxn şi un cal plasat în colţul din stânga, sus. Se cere să se afişeze un

drum al calului pe table de şah, astfel încât să treacă o singură dată prin fiecare pătrat al tablei.

23. Problema labirintului (ieşirea din labirint)

Se dă un labirint sub formă de matrice cu m linii şi n coloane. Fiecare element al matricei are

valoarea 0 dacă se poate trece prin acea cameră şi 1 dacă este zid. Într-una din camera, de

coordonate ax şi bx, se găseşte un om. Se cere să se găsească toate ieşirile din labirint, ştiind că nu

este permis ca un drum să treacă de două ori prin aceeaşi camera

24. Problema bilei

Se dă un teren sub formă de matrice cu m linii şi n coloane. Fiecare element a[i,j] al matricei

reprezintă altitudinea pătratului de coordonate i,j de pe teren. Într-un pătrat de coordonate lin, col

se găseşte o bilă. Ştiind că bila se poate deplasa în orice direcţie aflată la nord, est, sud sau vest pe

un pătrat cu altitudine strict inferioară celei pe care se găseşte bila. Se cere să se găsească toate

posibilităţile ca bila să părăsească terenul.

25. Permutări speciale

Să se genereze permutările speciale ale mulţimii {1,2,…,n} cu proprietatea că pentru oricare

permutare specială p există indicele i, 1in, astfel încât p[i]=i. Câte permutări speciale de n

elemente există ? Simulaţi executarea algoritmului pentru n=3.