Testul nr 10
Metoda BACKTRACKING
Setul 1
1. Se citeste un numar natural n. Sa se genereze toate permutarile multimii {1, 2, ..., n}.
2. Sa se genereze toate solutiile de aranjare a n dame pe o tabla de sah de nxn, astfel incat acestea sa nu se
atace. (doua dame se ataca daca se afla pe linie, coloana sau diagonala).
3. Sa se afiseze toate partitiile unui numar natural n. Numim partitie a numarului natural n o multime de
numere nenule {p1,p2,p3,...pk} astfel incat: p1+p2+p3+...+pk=n.
4. Se dau suma S si n tipuri de monede avand valori de a1, a2, a3, ...., an lei. Se cer toate modalitatile de
plata a sumei S utilizand aceste monede.
5. Intr-un labirint, reprezentat ca o matrice L, cu n linii si m coloane, cu componente de 0 si 1 (1
semnificand perete si 0 culoar) se gaseste pe pozitia (xb,yb) o bucata de branza, iar pe pozitia (xs, ys) un
soricel. Afisati toate posibilitatile soricelului de a ajunge la branza, stiind ca el se poate deplasa numai pe
culoar, iar directiile posibile de miscare ale soricelului sunt: N, NE, E, SE, S, SV, V, NV.
6. Pe o tabla de sah de dimensiune nxn, se afla plasat un cal in coltul din stanga sus. Afisati toate
posibilitatile calului de a parcurge toata tabla de sah, fara a trece de doua ori prin aceeasi pozitie.
7. Generati toate submultimile de k elemente ale multimii {1,2, ... , n}, n si k se dau, iar k apartine multimii
{1, 2, ... , n}. (combinari de n luate cate k).
8. Fie n multimi A1, A2, ... , An de forma Ai={1, 2, .... , li} unde i apartine {1, 2, ... , n}. Afisati produsul
cartezian A1 x A2 x ... x An.
9. Se citesc n si p numere natrurale. Se cere sa se genereze toate submultimile multimii {1, 2, ..., n} de p
elemente. Doua multimi cu aceleasi elemente, la care ordinea acestora difera, sunt considerate distincte.
(aranjamente de n luate cate p).
10. Se da un numar natural n. Se cere sa se genereze toate submultimile multimii {1, 2 ,..., n.
11. Sa se scrie un program Pascal care sa calculeze cate perechi de numere naturale nu depasesc un numar
dat n si au cel mai mare divizor comun un numar natural dat d.
12.
13. Se da de la tastatura un numar natural nenul n<=14, care reprezinta dimensiunea unei table de sah.
a. Se cere sa determine in cate moduri pot fi asezate pe tabla de sah n ture, astfel incat oricare doua sa
nu se atace (doua ture se ataca daca ele se afla pe aceeasi linie sau pe aceeasi coloana).
b. Sa se genereze toate modalitatile de asezare pe tabla de sah a n ture astfel incat oricare doua sa nu se
atace.
14. In fisierul Numere.in se dau:
- pe prima linie un numar natural n<=15;
- pe a doua linie n numere naturale x[1], x[2], ..., x[n] mai mici sau egale cu 10000 separate printr-un
spatiu;
- pe a treia linie un numar natural S cu cel mult 9 cifre.
Se cere sa se determine sirurile de semne + si ce trebuiesc puse in fata numerelor x[1], x[2], ..., x[n]
pentru ca rezultatul expresiei obtinute sa fie egal cu S.
15. Sa se scrie in fisierul text Nre.out toate numerele de n cifre egale cu de k ori produsul cifrelor. n si k se
citesc de la tastatura, si 1<=n<=9, 1<=k<=10000.
Metoda BACKTRACKING
Setul 2
1. O grupa de studenti trebuie sa programeze m examene in n zile , n>=m. In cate moduri se pot programa examenele
stiind ca intr-o zi se poate programa cel mult un examen. Sa se genereze toate posibilitatile de programare a
examenelor, fara sa se foloseasca recursivitatea.
2. Cate numere naturale diferite se pot forma cu cifrele 1, 2, 3, ... , n, daca in fiecare astfel de numar orice cifra apare
cel mult odata? Se va citi de la tastatura numarul n de cifre si se cere sa se genereze iterativ toate solutiile.
3. Exista n someri. Ei trebuie sa se reprofileze , fiecare in cate una din cele n meserii. Scolarizarea somerului i in
meseria j prezinta costul c(i,j). Somerii trebuie sa se scolarizeze fiecare in cate o meserie diferita de a celorlalti. Se
citesc de la tastatura n si apoi tabloul bidimensional c(n,n). Sa se precizeze toate posibilitatile de atribuire a celor n
meserii pentru cei n someri si care este costul total al scolarizarii tuturor pentru fiecare repartizare a lor pe cele n
meserii.
4. La o admitere se dau n examene. La primul examen se pot obtine de la 0 la p1 puncte, la al doilea se pot obtine de
la 0 la p2 puncte, etc. Pentru reusita, un candidat trebuie sa obtina cel putin m puncte in total. Sa se scrie un
program care genereaza toate variantele de punctaje ce trebuie obtinute la cele n examene si care conduc la
reusita.
5. Se citeste de la tastatura numarul natural n. Sa se foloseasca metoda backtracking pentru generarea tuturor
matricilor patratice binare de dimensiune nxn, cu proprietatea ca in fiecare coloana exista exact o cifra de 0.
6. Se da o tabla de sah de dimensiuni nxn patrate. Sa se aseze pe ea n regi, cate unul pe o linie, astfel incat sa nu se
atace oricare 2 dintre ei.
7. Sa se afiseze, cate unul pe o linie, toate subsirurile strict crescatoare de lungime k (k<10) ale unui sir de numere
reale date. Sirul se citeste din fisierul text Sir.in, iar k de la tastatura.
8. Pentru un cuvant de cel mult 20 de litere mari, cuvant citit de la tastatura, sa se afiseze in ordine lexicografica toate
cuvintele care contin toate literele distincte ale cuvantului dat si care nu contin doua consoane sau doua vocale
consecutive. Daca nu exista se va afisa mesajul IMPOSIBIL.
9. Sa se genereze k vectori diferiti, fiecare vector generat fiind format din n elemente 1 si 0, suma elementelor sale
neavand voie sa depaseasca valoarea s. Valorile k, n si s se citesc de la tastatura, vectorii generati fiind salvati in
fisierul P3.out, cate unul pe o linie, elementele liniei fiind despartite prin cate un spatiu.
10. Utilizand m culori (maximum 5), numerotate de la 1 la m, sa se coloreze in toate modurile posibile n piloni
(maximum 10), care initial sunt albi, aflati pe o suprafata oarecare, daca acestia se vad intrei ei si doi piloni care
se vad intre ei nu trebuie sa aiba aceasi culoare. Pilonii sunt in relatie se vad intre ei daca orice linie imaginara
care uneste doi piloni nu trece printr-un camp ocupat de alt pilon. Datele de intrare sunt: numarul n de piloni,
perechi x si y care semnifica faptul ca x si y se vad, numarul m de culori, si denumirile culorilor. Se cere sa se
afiseze toate solutiile posibile de colorare a pilonilor.
11. Intr-o mare inchisa sunt n porturi, maxim 10. Stationarea intr-un port se taxeaza printr-un cost asociat. Sa se
stabileasca toate voiajele distincte dintre p porturi (p<=n) care nu depasesc un cost total de statioanre. Porturile au
denumiri de maxim 16 caractere, iar costurile si costul toatal sunt numere reale.
12. Sa se afiseze toate posibilitatile de aranjare pe o caseta a n melodii, codificate cu numerele naturale de la 1 la n,
astfel incat melodia x sa se cante dupa melodia y (x, y valori citite iar n<<10).
13. Se considera n piese de domino citite ca n perechi de numere naturale fiecare pe cate un rand de intrare. Sa se
afiseze toate solutiile de asezare a acestor piese intr-un lant-domino de lungime a citita de la tastatura, fara a roti
piesele. (Un lant-domino se alcatuieste din piese de domino astfel incat o piesa este urmata de o alta a carei prima
jumatate coincide cu jumatatea a doua a piesei curente).
14. Sa se elaboreze toate variantele de chestionare ce se pot obtine dintr-un set total de n intrebari (maxim 20) care sa
aiba intre a si b intrebari, iar intrebarile sa totalizeze p si maximum q puncte. Se citesc in ordine: numarul de
intrebari, apoi fiecare intrebare, text de maximum 100 de caractere, urmata de punctajul sau si la sfarsit limitele
a, b, p si q.
15. Se considera n cuburi (max. 10), numerotate de la 1 la n, de laturi si culori cunoscute. Datele fiecarui cub se citesc
de pe cate un rand de intrare, in ordinea: nr.cub, latura, culoare. Sa se numere si alcatuiasca toate turnurile posibile
din h cuburi astfel incat fiecare turn sa aiba stabilitate (orice cub se aseaza peste un cub cu latura mai mare sau
egala cu a lui) si sa nu existe doua cuburi consecutive de aceeasi culoare. Fiecare solutie se va lista distinct, asrfel
ca utilizatorul sa aiba timp sa o citeasca, va specifica numarul turnului si va cuprinde h grupuri de informatii de
tipul: nr. cub latura culoare.
16. Sa se alcatuiasca toate sirurile posibile din n numere naturale a1, a2, ... , an, citite, astfel incat in orice sir creat sa
nu existe doua numere consecutive asezate alaturi. Solutiile se vor afisa secvential, astfel incat utilizatorul sa le
poata citi.
17. Se citesc de la tastatura un numar natural n (n<=20) si un numar natural v (v<n). Sa se scrie un program care
afiseaza toate numerele de la 1 la n in toate modurile posibile astfel incat intre oricare doua numere succesive
diferenta in modul sa fie mai mare decat v. Datele de iesire se vor scrie in fisierul Iesire.dat. Daca nu exista nici
o solutie, se va scrie in fisierul de iesire un mesaj corespunzator.
