RECONVERSIE PROFESIONALĂ ÎN INFORMATICĂ LUCRARE DE ABSOLVIRE Coordonator științific, Conf. dr. Doru Anastasiu POPESCU Absolvent, Mihaela Mioara PIRNĂ… [622336]

1
UNIVERSITATEA DIN PITEȘTI
FACULTATEA DE ȘTIINȚE,
EDUCAȚIE FIZICĂ ȘI INFORMATICĂ
RECONVERSIE PROFESIONALĂ ÎN INFORMATICĂ

LUCRARE DE ABSOLVIRE

Coordonator științific,
Conf. dr. Doru Anastasiu POPESCU

Absolvent: [anonimizat] 2017

2
UNIVERSITATEA DIN PITEȘTI
FACULTATEA DE ȘTIINȚE,
EDUCAȚIE FIZICĂ ȘI INFORMATICĂ
RECONVERSIE PROFESIONALĂ ÎN INFORMATICĂ

TEHNICI DE PROGRAMARE
UTILIZATE ÎN REZOLVAREA
PROBLEMELOR DE NUMĂRARE

Coordonator științific,
Conf. dr. Doru Anastasiu POPESCU

Absolvent: [anonimizat] 2017

3

CONTENTS
INTRODUCERE ………………………….. ………………………….. ………………………….. ………………………….. …………………….. 5
1. PROBLEME DE NUMĂRARE ………………………….. ………………………….. ………………………….. ………………………… 6
1.1 Definirea termenilor ………………………….. ………………………….. ………………………….. ………………………….. ……….. 6
1.2 Metode de rezolvare a problemelor de numărare ………………………….. ………………………….. ……………………… 6
2. TEHNICI DE PROGRAMARE ………………………….. ………………………….. ………………………….. ………………………… 9
2.1 Analiza algoritmilor ………………………….. ………………………….. ………………………….. ………………………….. ……….. 9
2.2 Metode de construire a algoritmilor ………………………….. ………………………….. ………………………….. …………… 11
3.METODA BACKTRACKING ………………………….. ………………………….. ………………………….. …………………………. 13
3.1 Descrierea metodei backtracking ………………………….. ………………………….. ………………………….. ……………….. 13
3.2 Implementarea metodei backtracking ………………………….. ………………………….. ………………………….. ………… 15
3.3 Probleme rezolvabile prin metoda backtracking ………………………….. ………………………….. ……………………… 18
3.3.1Generarea permutărilor ………………………….. ………………………….. ………………………….. …………………………. 18
3.3.2 Generarea numerelor naturale ………………………….. ………………………….. ………………………….. ……………… 20
3.3.3 Generarea combinărilor ………………………….. ………………………….. ………………………….. ……………………….. 21
3.3.4 Problema damelor ………………………….. ………………………….. ………………………….. ………………………….. …… 23
3.3.5 Problema colorării hărților ………………………….. ………………………….. ………………………….. …………………. 26
3.3.6 Problema determinării subșirului comun de lungime maximă ………………………….. ………………………….. . 29
3.3.7 Generarea submulțimilor ………………………….. ………………………….. ………………………….. ……………………… 32
4. METODA PROGRAMĂRII DINAMICE ………………………….. ………………………….. ………………………….. ……….. 36
4.2 Implementarea metodei programării dinamice ………………………….. ………………………….. ……………………….. 39
4.3 Probleme rezolvabile prin metoda programării dinamice ………………………….. ………………………….. ………… 39
4.3.1 Afișarea unei secvențe crescătoare de lungim e maximă a unui vector ………………………….. …………….. 39
4.3.2 Problema subșirului comun maximal ………………………….. ………………………….. ………………………….. …… 42
4.3.3 Problema sumei maxime într -un triunghi ………………………….. ………………………….. …………………………. 45
4.3.4 Problema subșir crescător de lungime maximă. ………………………….. ………………………….. ………………… 48
4.3.5 Problema rucsacului ………………………….. ………………………….. ………………………….. ………………………….. .. 51
4.3.6 Numarul de secvente pare de lungime maxima intr -un vector ………………………….. ………………………… 55
Concluzii ………………………….. ………………………….. ………………………….. ………………………….. ………………………….. …… 58
BIBLIOGRAFIE ………………………….. ………………………….. ………………………….. ………………………….. …………………… 59
ANEXE ………………………….. ………………………….. ………………………….. ………………………….. ………………………….. …….. 60

4

LISTA FIGURILOR

Fig. 3.3.1 Exemplu de date pentru generarea permutărilor
Fig. 3.3.2 Exemlu de date pentru generarea numerelor naturale
Fig. 3.3.3 Exemplu de date pentru generarea combinărilor
Fig. 3.3.4 Exemplu de date pentru problema damelor
Fig. 3.3.5 Exemplu de date pentru problema colorării hărților
Fig. A.2.1 Exemplu de date pentru calculul CMMDC prin tehnica divide et
impera

LISTA TABELELOR

Tab.3.3.6 Exemplu de date pentru determinarea subșirului comun de lungime
maximă
Tab. 3.3.7 Exemplu de date pentru deteerminarea sumei de lungime maximă
într-un triunghi
Tab. 4.3.1 Exemplu de date pentru afișarea unei secvențe crescătoare de
lungime maximă într -un vector
Tab 4.3.3 Ex emplu de date pentru afițarea sumei de lungime maximă într -u
triunghi – metoda programării dinamice
Tab. 4.3.44 Exemplu de date pentru afișarea subșirului crescător de lungime
maximă
Tab. 4.3.5 Exemplu de date pentru rezolvarea problemei rucsacului.
Tab. 4 .3.6 Exemple de date pentru numărulde secvențe pare de lungime
maximă într -un vector

5
Tab. A.1.1 Exemplu de date pentru rezolvarea problemei spectacolelor prin
tehnica greedy
INTRODUCERE

Diversitatea și complexitatea problemelor de numărare precum și proiectarea
unor algoritmi de rezolcare a acestora care să conducă la scrierea unor programe pe
calculator eficiente reprezintă o provocare pentru orice pasionat de calculatoare.
Pornind de la aceste aspecte și respectând etapele parcurse în rezolvarea une i
probleme pe calculator ( analiza problemei, proiectarea algoritmului și
implementarea alogoritmului printr -un program pe calculator) lucrarea de față își
propune să ofere o imagine asupra modului în care cele două tehnici de programare
abordate backtrack ink și programare dinamică contribuie la rezolvarea unor
probleme compexe prin reducerea efortului programatorului la câteva sarcini.
Astfel printre avantajele utilizării acestor metode amintim: algoritmul este ușor de
gândit, ușor de implementat, nu neces ită foarte mult studiu, oferă întotdeauna
soluțua optimă, folosesc memorie puțină.
Lucrarea de față este structurată în 4 capitole. Capitolul 1 tratează tema
problemelor de numărare, tipuri de probleme și metode de rezolvare folosite în
matematică. Acest c apitol este important în prima etapă a rezolvării unei probleme
cu ajutorul calculatorului, mai exact analiza problemei. Capitolul 2 tratează tema
tehnicilor de programare, definirea termenilor, definirea algoritmilor, tipuri de
algoritmi, metode de constr uier a algoritmilor. Capitolul 3 tratează problema
implementării în C++ a unor probleme utilizând tehnica backtracking. În acest
capitol găsim informații despre metodă – o scurtă descriere, construirea
algoritmului, implementarea lui și aplicații ale metod ei în rezolvarea unor
probleme. Capitolul 4 tratează problematica implementării în C++ a unor probleme

6
utilizând metoda programării dinamice, descrierea metodei, construirea
algoritmului, implementare și aplicații ale metodei în rezolvarea unor probleme .

1. PROBLEME DE NUMĂRARE

1.1 DEFINIREA TERMENILOR

Problemele de numărare reprezintă una din cele mai diverse ramuri ale
matematicii – combinatorica. Putem spune că este o ramură aflată în plină
dezvoltare, complexă și diversă, nu atât din punctul de ved ere al cantității de
informație cât mai ales din punctul de vedere al multitudinii strategiilor de
rezolvare. Deși există preocupări în domeniu încă din secolul al III – lea (d.H),
perioadă în care apare într -un manuscris formula(
) =
, fundamentarea
propriu -zis științifică a teoriei combinărilor și permutărilor îi aparține lui
G.W.Leibnitz (1646 -1716) în ”Dizertație despre arta combinatorie”.
În ceea ce privește definirea conceptului, nu putem vorbi de o definiție exactă,
însă o caracter izare completă găsim în manualul de clasa a X -a 1. Problema centrală
a combinatoricii este de selectare a unor grupe de obiecte după anumite reguli și
determinarea numărului de moduri în care se poate face acest lucru. Există
probleme în care regulile după care se formează grupele sunt simple și atunci
rezolvarea constă în numărarea acestora, dar există și probleme complicate în care
modul de formare a grupelor este complex și atunci accentul cade pe stabilirea
existenței grupelor sau pe găsirea metodelor de construire a acestora.

1.2 METODE DE REZOLVARE A PROBLEMELOR DE NUMĂR ARE

1 Panaitopol L., Bălucă M. , Manual de clasa a X -a, Editura Gil, 2001

7

Există probleme de combinatorică simple a căror soluție vine de la sine (
exemplu: într -un șir finit de numere reale suma oricăror k numere consecutive este
negativă, în timp ce suma oricăror j numere consecutive este pozittivă, aflați
numărul maxim de elemente al șirului), însă există și probleme complexe a căror
soluție o găsim prin aplicarea unor metode de rezolvare .Vom trece în revistă
metodele de rezolvare a problemelor de numărare. O desciere complexă a acestor
metode o găsim în manualul de matematică de clasa a X -a.2
1. Metoda inducției matematice prin care pornind de la propoziții advărate
pentru valori particulare (numere naturale) se construiesc propoziții generale, P(n),
n ∈ N, care pot fi adevărate sau false. Principiul inducției matematice este
următorul: dacă o propoziție P(n) care depinde d e numărul natural n, n ≥ m, m
număr natural fixat și este adevărată pentru n=m și pentru n=k, rezultă că ea este
devărată și pentru numărul natural n=k+1 atunci propoziția P(n) este adevărată
pentru oricare număr n ≥ m;
2. Metoda mulțimilor finite ordonate reprezintă o categorie specială a
problemelor de numărare pe care le găsim în literatura de specialitate sub
denumirea de combinatorică, care cer să se determine numărul de elemente dintr -o
mulțime finită sau numărul de funcții cu domeniul sau codomeniul mul țimi finite.
Definițis unei astfel de mulțimi este: Mulțimea se numește finită dacă există o
funcție bijectivă f:{1,2,….,n} → A. Numărul n al mulțimii A se numește cardinalul
mulțimii A. Notație: n=card(A); convenție card( Ø)=0 ;
3. Permutări – mulțimile ordonate cu n elemente care se obțin prin ordonarea
unei mulțimi finite cu n elemente se numesc permutări ale acestei mulțimi;Notație:
numărl P(n) al tuturor permutărilor unei mulțimi A cu n elemente, cu n ∈ N* este P n
=1· 2 · ….. .. ·n;

2 Udriște c., Țevy I., Necșuleu G., necșuleu I., Gușatu M., Crăciun M., Saulea T., Nicula V., matemarică manual pentru
clasa a X -a, Editura Fair Partners, 2005, capitolul 5.

8
4. Aranjamente – submulțimile ordonate de câte k elemente, k ≤ n, care se
pot forma cu cele n elemente ale unei mulțimi finite se numes aranjamente de n
luate câte k. Exemplu: fie A o mulțime cu n elemente, n ∈ N* , și fie k ≤ n, un
număr natural fixat , numărul aranjamentelor ( din A) de n elemente luate câte k este
= n(n -1)············(n -k+1) sau =
=
;
5. Combinări definiție: fie 0 ≤ k ≤ n, k ∈N, n ∈ N*.Submulțimile cu câte k
elemente ale unei mulțimi finite cu n elemente se numesc combinări de n elemenete
luate câte k elemente. Notație: numărul tuturor combinărilor de n elemente luate
câte k. Într -o mulțime A cu n elemente și k un număr fixat, as tfel încât n ∈ N* și k
∈ N, k ≤ n, numărul tutror combinărilor de n elemente luate câte kj este
=
=

6. Binomul lui Newton pentru a și b numere reale și n ∈ N* este adevărată
egalitatea
(a+b)n = an + an-1 b + ··· + an-kbk + ··· + bn
O strategie mai generală de rezolvare a problemelor de combinatorică este
împrumutată din domeniul algoritmilor. Conform algoritmilor problema de rezolvat
se descompune într -o serie de probleme mai mici, se soluționea ză aceste porțiuni și
apoi se combină soluțiile obținute pentru a obține rezultatul final.

9

2. TEHNICI DE PROGRAMARE

Ce este un program? Un program înseamnă exprimarea unui algoritm într -un
limbaj de programare. Un limbaj de programare 3 este un limbaj artificial, riguros
întocmit, care permite descrierea algoritmilor astfel încât să poată fi transmiți
calculatorului cu scopul ca acesta să efectueze operațiile specificate.Vom vorbi în
continuare despre algoritm, analiza, proiectarea și im plementarea algoritmilor
pentru rezolvaarea problemelor de numărare. O definiție pe care am putea să o dăm
unui algoritm este metodă de rezolvare a unui anumit tip de problemă, metodă care
poate fi implementată pe calculator.4 Un algoritm este esența absol ută a unei rutine
și constă într -un număr finit de pași, fiecare pas necesitând una sau mai multe
oprații. În funcție de complexitatea problemelor se aleg tehnicile de programare
care vor fi folosite. Astfel etapele care vor fi parcurse sunt următoarele:
1. Analiza care presupune înțelegerea corectă a cerinței problemei și
verificarea constrângerilor (timp de execuție, memorie, etc)
2. Proiectarea în funcție de timpul alocat rezolvării problemei;
3. Implementarea care presupune scrierea codului, depanarea și testare a;

2.1 ANALIZA ALGORITMILOR

Prin analiza unui algoritm se înțelege identificarea resurselor necesare pentru
executarea algoritmului: timpul de execuție și memoria5. Aând în vedere
complexitatea și diversitatea metodelor de rezolvare a problemelor de numă rare,
analiza algoritmilor este necesară atunci când există mai mulți algoritmi de

3 Algoritmi ș i structuri de date, Note de curs ,Olidej.wikispaces.com, , accesat iunie 2017
4 Andonie R., Gârbacea I., Algoritmi fundamentali, o perspectivă C++, editura Libris, Cluj Napoca, 1995
5 Miloșescu M., Informatică intensiv C++, Manual pentru clasa a XI -a, Edi tura didactică și pedagogică, R.A.,2013

10
rezolvare a aceleiași probleme și trebuie ales cel mai bun din punctul de vederee al
eficienței. Eficiența unui algoritm este dată de timpul necesar pentru executarea
algori tmului. Timpul de execuție al unui algoritm se exprimă prin numărul de
operații de bază executate în funcție de dimensiunea datelor de intrare: T(n). În
compararea a doi algoritmi, din punct de vedere al timpului de execuție, este
important să se aleagă un itatea de măsura care se va folosi, adică operația de bază
executată în cadrul algoritmilor, numărându -se de câte ori se execută aceasta în
cadrul fiecărui algoritm. Operația de bază este o operație elementară, sau o
succesiune de operații elementare, a că ror execuție nu depinde de valorile datelor
de intrare. În funcție de ordinul de complexitate al unui algoritm – dat de timpul de
execuție estimat prin ordinul de mărime al numărului de execuții ale operației de
bază distingem:
1. Algoritmi liniari , ordin de complexitate O(n). Exemplu pentru structura
repetitivă: for(i=1;i<=n; i=i+k {…….}, numărul de execuții ale corpului
structurii este f(n)=n/k → o(n)=n;
2. Algoritmi polinominali , ordin de complexitate O(nm)(observaație: dacă
m=2 algoritmul este pătratic, dacă m=3 algoritmul este cubic). Exemplu
pentru structura repetitivă: for(i=n;i<=n; i=i+p) {……..}, for(j=n;j<=n;
j=j+q) {……..}, numărul de execuții ale corpului structurii este f(n)=
(n/p)*(n/q)=n2/(p+q) →O(n)=n2;
3. Algoritmi exponențiali, ordin de complexitate este O(kn) . Exemplu:
algoritmul de tip O(n!) este tot de tip exponențial, deoarece : 1 x 2 x 3 x 4
x··· x n> 2 x 2 x 2 x ··· x 2 = 2n-1
4. Algoritm logaritmic, ordin de complexitate O(logn ). Exe mplu pentr
structura repetitivă for( i=1; i<=n; i=i*k) {……} numărul de execții ale
corpului structurii este f(n) = log kn O(n)=logn;
5. Algoritm liniar logaritmic , ordin de complexitate O(nlogn).

11

2.2 METODE DE CONSTRUIRE A ALGORITMILOR

Având în vedere complexitatea problemelor de numărare și a metodelor de
reolvare atunci când procedăm la construirea algoritmuluide rezolvare putem
clasifica problemele în 3 clase:

Exemple: o problemă de generare a tuturor permutărilor unei mulțimi de
numere se încadre ază în clasa problemelor de numărare, o problemă de căutare a
unei valori precizate într -un șir de numere se încadrează în clasa problemelor de
decizie iar găsirea modalității de plată a unei sume s cu un număr minim de
bancnote se încadrează în clasa prob lemelor de optimizare. De asemenea pentru
rezolvarea unei probleme se pot folosi mai multe probleme de construire a
algoritmilor.
Construirea unui algoritm care rezolva o problemă presupune ca etapă
intermediară construcția modelului matematic corespunzato r problemei. Pentru de –
finirea modelului matematic se au în vedere următoarele aspecte:

Clase de
probleme
probleme de
enumerare
prin care se
găsesc toate
soluțiile posibile
probleme de
decizie
prin care se
precizează dacă
există sau nu cel
puțin o soluție
probleme de
optimizare
prin care se identifică
soluția optimă din
mulțimea de soliții
posibile

12

→ Construcția modelului matematic evidențiază și elimină aspecte ale
problemei care pot fi omise sau sunt formulate ambiguu.
→ Instrumentele matematice de invenstigare î n perspectiva identificării și
definirii soluției sunt mai puternice;
→ Definirea soluției în termenii modelului matematic ușurează foarte mult
procesul de construcție al algoritmului.
O metoda de proiectare a algoritmilor se bazeaza pe un anumit tip d e model
matematic si pune la dispozitie procedeee prin care se poate construi si implementa
un model particular corespunzator unei probleme. Definirea unui model matematic
cuprinde urmatoarele trei aspecte:
1. conceptual: presupune identificarea si co nceptualizarea componentelor
din domeniul problemei;
2. analitic: care presupune descoperirea tuturor relatiilor intre conceptele care
conduc la identificarea si descrierea solutiei;
3. computational: care face referire la evaluarea calitativa a algoritmul ui prin
care se construieste solutia.
Cele mai cunoscute metode de proiectare a algoritmilor sint urmatoarele:
divide -and-conquer, greedy, programarea dinamica, backtracking, branch -and-
bound.

13

3.METODA BACKTRACKING

Cu totii stim ca Backtracking este una din cele mai cunoscute tehnici de
programare. Ideea acestui algoritm este de a genera toate solutiile posibile și a le
abandona in cazul în care observa ca nu îndeplinesc condițiile necesare. Datorită
generării tuturo r soluțiilor, complexitatea algoritmului este foarte mare, dar duce
sigur la generarea tuturor posibilitatilor valide.

3.1 DESCRIEREA METODEI BA CKTRACKING

Această metodă generală de programare se aplică acelor probleme în care
soluția se poate reprezenta sub forma unui vector6 X = (x1, …, xn)ÎS unde S = S 1 x
… x S n , unde mulțimile S 1, …,S n sunt mulțimi finite având |Si| = si elemente. Pentru
fiecare problemă concretă sunt date anumite relații între componentele x 1 , … x n ale
vectorului X, numite condiții interne .
Mulțimea finită S = S 1 x S 2 x… x S n este denumită spațiul soluțiilor
posibile (este un produs cartezian). Soluțiile posibile care satisfac condițiile interne
se numesc soluții rezultat . Scopul utilizării metodei este de a det ermina toate
soluțiile rezultat și de a le afișa sau de a alege dintre ele una care maximizează sau
minimizează o eventuală funcție obiectiv dată.
O metoda simplă de determinare a soluțiilor rezultat constă în a genera
într-un mod oarecare toate soluțiile posibile și de a verifica dacă ele satisfac
condițiile interne. Dezavantajul constă în faptul că timpul cerut de această
investigare exhaustivă este foarte mare. Astfel, chiar pentru |Si| = 2, " i, timpul
necesar este de ordinul 2n, deci exponențial.

6 Valeriu LUPU, Algoritmi.Tehnici și limbaje de programare, Editura universității Ștefan cel Mare Suceava, p.73

14
Metod a backtracking urmărește să evite generarea tuturor soluțiilor
posibile. În acest scop, elementele vectorului X primesc pe rând valori în sensul că
lui xk i se atribuie o valoare numai dacă au fost atribuite deja valori lui x 1 ,… x k-1 .
Mai mult, odată o valoare pentru xn stabilită, nu se trece direct la atribuirea de
valori lui x k+1 , neîndeplinirea lor exprimând faptul că oricum am alege x k+1,…,xn nu
vom putea ajunge la o soluție rezultat, adică o condiție pentru care condițiile
interne să fie sati sfăcute. Evident că în cazul neîndeplinirii condițiilor de continuare
va trebui să facem o altă alegere pentru xk sau dacă Sk a fost epuizat să micșorăm
pe k cu o unitate încercând să facem o nouă alegere pentru x k etc.; această
micșorare a lui k dă numele metodei, ilustrând faptul că atunci când nu mai putem
avansa, urmărim înapoi secvența curentă din soluție. Este evident că între condițiile
de continuare și condițiile interne există o strânsă legătură. O bună alegere pentru
condițiile de continuare are c a efect o importantă reducere a numărului de calcule.
Algoritmul metodei backtracking poaate fi generalizat pentru orice
problemă care îndeplinește următoarele condiții:
1. Soluția problemei poate fi pusă sub forma unui vector V= {x 1, x2, ···x n}
ale cărui elemente x i aparțin unei mulțimi A i, astfel: x 1∈ A1, x2∈ A2, ···xn∈ An
2. Mulțimile A i sunt finite, iar elementele lor sunt numere întregi și se
găsesc într -o ordine bine stabilită.

Algoritmul Backtracking7 este următorul:
PAS1. Se alege primul element al soluției S: x 1∈ Ai;
PAS2. Cât timp nu au fost parcurse toate elementele mulțimii A 1 ( nu au fost
găsite toate soluțiile) execută :
PAS3. Pentru fiecare element al soluției execută:

7 Miloșescu M, Idem

15
PAS4. Se presupune că s -au găsit primele k elemente ale soluției (x 1, x2,
…x k) aparținând mulțimilor A 1, A2, A3,….Ak și se trece la căutarea
celui de al k+1 – lea element al soluției, x k+1, printre elementele
mulțimii A k+1. până se găsește primul element care îndepliește
condiția de continuare.
PAS5. Dacă există un eleme nt a i în mulțimea A k+1, astfel încât x k+1 = ai,
să aparțină soluției problemei, atunci se atribuie elementului x k+1
valoarea a i și se trecee la PASUl7 altfel , s trece la PASUL6.
PAS6. Deoarece s -au parcurs toate elementee mulțimii A k+1 și nu s -a
găsit nic i un element a i care să îndeplinească condiția de
continuare, se revine la elementul x k și se consideră generate
toate primele k -1 elemente ale souției : (x 1, x2, …x k-1, și pentru
elementul x k se reia căutarea cu următorul element din mulțimea
Ak, adică se reiau operațiile de la pasul4 pentru elementele x k al
soluției, însă nu cu primul element din mulțimea A k ci cu
elementul din mulțimea A k care se găsește imediat după cel care
a fost atribuit anterior elementului x k
PAS7. Se verifică dacă s -a găsit sol uția problemei, adică dacă s -au găsit
toate elementele mulțimii S. Dacă s-a găsit soluția problemei
atunci se afișează soluția, altfel, se trece la căutarea următorului
element al al soluției, reluaând operațiile de la Pasul 4.

3.2 IMPLEMENTAREA METODEI BACKTRACKING

Pentru implementarea metodei backtracking se folosesc snumite structuri de
date și subprograme. Astfel pentru a memora elementele soluției se folosește o
structură de date de tip stivă care este implementată printr -un vector – st.
Procedura de lucru cu structura de date de tip stivă:

16
 Se folosește variabila k pentru vârful stivei;
 Elementul xk al soluției în mometul în care a fost găsit se urcă în vârful
stivei prin incrementarea vârfului cu 1 (k++) pentru a căuta elementul
xk+1 al soluției, iar pentru a reveni la elementul xk-1 se coboară în stivă
prin decrementare cu 1 (k –);
 Dimensiunea inițială a stivei este 1 și conține valoarea primului element
al soluției (k min = 1);
 Elementul din vârful stivei va avea atribuită o valoare din mulțimea A k
care poate fi element al soluției. st[k] = a[i];
 După parcurgerea completă a mulțimilor A k stiva va avea dimensiunea
n(k max = n) corespunzătoare numărului de elemente al soluției.
 Valorile pe care le va avea vârful stivei sunt:
– inițial -1;
– la găsirea unei soluții – n;
– la terminarea algoritmului – 0.
Variabile de memorare utilizate de structura de date de tip stivă:
→ as – verifică dacă pentru elementul x k mai există succesor. Este o variabiă
logică și are ca valori 1 -true (există succesor) și o false (numai există
succesor)
→ ev – verifică dacă succesorul găsit vrespectă condiția de continuare. Este o
variabiă logică și are ca valori 1 -true (succesorul este element al soluției) și o
false (succesorul nu respectă condițiilede continuare șideci nu este element al
soluției);
→ n – verifică dimensiunea soluției.
Subrograme utilizare în implementarea metodei backtracking
ƨ subprogramul general valabil pentru toțo algoritmii de rezolvare (parte
fixă) care descrie strategia generală;
ƨ subprograme specifice condițiilor interne ale problemelor;

17
ƨ subprogramul init îndeplinește o funcție procedurală: inițializează
elementul din vârful stivei și atribuie valori din mulțimea solicitată;
ƨ subprogramul succesor îndeplinește funcția operand: verifică dacă mai există
succesor;
ƨ subprogramul valid îndeplinește funcția operand: verifică dacă valoarea
atribuită elementelor soluției îndeplinește condiția de continuare;
ƨ subprogramul soluție îndeplinește funcția operand: verifică dacă s -au
obținut toate elementele soluției;
ƨ subprogramul tipar îndeplinește funcția procedurală de afișare a
elementelor soluției.
Complexitatea algoritmului metodei backtracking
În funcție de numărul elementelor mulțimilor din care se aleg elementele
soluției există două cazuri:
1. Fiecare soluție are n elemente și fiecare mulțime Ai din care se alege
un elememeent al soluției are m eleemente ordinul de complexitate al
algoritmului este :
O(card(A 1) x card(A 2) x …..x card(A n)) = O(m x m x …..x m) = O(mn)
2. Numărul de elemente al mulțimilor Ai este di ferit ordinul de
complexitate al algoritmului este:
Notăm:
mmin= min(card(A 1) x card (A 2) x …. x card(A n)
și
mmax = max(card(A 1) x card (A 2) x …. x card(A n)
atunci:
ordinul de complexitate al algoritmului va fi cuprins între O(m minn)
O(m maxn)

18
3.3 PROBLEME DE NUMĂRARE CARE POT FI REZOLVATE PRIN METODA
BACKTRACKING

Pentru a putea fi rezolvată prin m etoda backtracking o problemă trebuie să
aibă una din caracteristici le următoare : se cere găsi rea tuturor soluțiilor posibile
sau n u se cunoaște un algoritm mai eficient.
Problemele care se rezolvă prin metoda backtracking pot fi împărțite în mai
multe grupuri de probleme cu rezolvări asemănătoare, in funcție de modificările pe
care le vom face în algoritm. Principalele grupuri de probleme sunt:
a) probleme în care vectorul soluție are lungime fixă și fiecare element
apare o singură dată în soluție;
b) probleme în care vectorul soluție are lungime variabilă și fiecare
element poate să apară de mai multe ori în soluție; exemple:
c) probleme în plan, a tunci când spațiul în care ne deplasăm este un tablou
bidimensional. Cele mai cunoscute unt:

3.3.1G ENERAREA PERMUTĂRILO R

Problemă : Să se genereze permutările unei mulțimi care îndeplinesc
următoarea condiție: pe poziție pară să fie număr par și pe poziție impară să fie
număr impar .
Exemplu:

Fig. 3.3.1 Generarea permutărilor

19

Soluție:
Gener ăm vectorul X=(X 1, X 2, …, X n) cu componenta Xi ∈ {1, 2, .., n}.
Xi ≠ X j ∀ i ≠ j
Componenta Xi este pară dacă i este par și componenta Xi este impar ă
dacă i este impar .
Conditii partiale :
Dacă s-au generat X 1 … X k-1 adaug ăm X k ∈ {1, 2, .., n} dac ă:
X[k]%2==k%2 si X[k] ≠ X[i]
Program C++:
#include <iostream>
using namespace std;
int n,x[100];
void afis()
{
int i;
for(i=1;i<=n;i++) //parcurgem vectorul x
cout<<x[i]<<" "; //afisam componenta de pe pozitia i
cout<<endl;
}
int cont(int k)
{
if(x[k]%2!=k%2) //verificam daca element curent are paritate diferita de
pozitia sa
return 0; //in caz afirmativ, solutia nu este corecta
int i;
for(i=1;i<k;i++) //parcurgem vectorul x pana la componenta curenta

20

if(x[k]==x[i]) / /daca se mai gaseste cel putin o componenta egala cu
cea curenta solutia nu este corecta
return 0;
return 1; //daca programul trece de cele 2 if -uri, solutia este corecta
}
void BT(int k)
{
int i;
if(k>n)
afis(); //daca k>n i nseamna ca avem o solutie si trebuie sa o afisam
else //altfel inseamna ca trebuie sa mai adaugam componente
for(i=1;i<=n;i++)
{
x[k]=i; //incarcam vectorul x cu valori intre 1 si n
if(cont(k))
BT(k+1); //daca este indeplinita conditia de existenta, adaugam
inca o componenta
}
}

3.3.2 GENERAREA NUMERELOR NATURALE

Problemă: Se dau n si q < 15 numere naturale. Afisați toate numerele cu n
cifre care conțin cifra 1 de q ori.
Exemplu:

21

Fig.3.3.2 Exemplu de date pentru generarea numerelor naturale
Solutie:
Generăm X=(X1, X2, …, Xn) cu Xi ∈ {0, 1, 2, .., 9}.
X1 ≠ 0 si numarul de cifre de 1 = q.
Condiții de continuare:
Dacă s -au generat X 1 … X k-1 adaugam Xk ∈ {0, 1, 2, .., 9} daca:
k=1 si Xk ≠ 0 si numarul de cifre de 1 ≤ q.
Daca k=n atunci adaugam X k daca numarul de cifre de 1 = q.
Program:

3.3.3 GENERAREA COMBINĂRILOR

Problema: Se citesc n și m numere naturale cu m <= n. Să se genereze toate
combinările de n elemente luate câte m.
Solutie:
1. Vom genera pe rând soluțiile problemei în vectorul X=(X 1,X2,X3,…,X n),
unde X k ∈ multimii {1, 2, …, n} .
2. Combinarile seamana cu permutarile asadar elementele nu au voie sa se repete.
In plus fata de permutari, trebuie sa punem conditia ca elementele sa fie in ordine
crescatoare. Dupa ce am generat X=(X 1, …, X k-1) adaugam X k doar daca pentru ∀
i=1,k -1 ave m X k Xi si X k > X k-1.
3. Obținem o soluție în momentul în care completăm vectorul cu n elemente.
Exemplu:

22

Fig. 3.3.3 Exemplu de date pentru generarea combinărilor
Program C++
#include <iostream>
using namespace std;
int n,m,x[100],nrsol;
int cont(int k)
{
int i;
for(i=1;i<k;i++)//parcurgem vectorul X pana la elementul k -1
if(x[i]==x[k]) //verificam daca exista elemente egale intre ele
return 0;
if(k> =2) //doar in cazul in care avem cel putin 2 elemente verificam daca
acestea sunt in ordine crescatoare
if(x[k -1]>x[k])
return 0;
return 1;
}
void afis()
{
for(int i=1;i<=m;i++)//parcurgem vectorul X (pana la m de
aceasta data) si afisam fiecare element
cout<<x[i]<<" ";
cout<<endl;

23
}
void BT(int k)
{
if(k>m) //daca k este mai mare ca m avem o solutie si trebuie sa o afisam
{
afis();
nrsol++;//numaram solutile
}
else
for(int i=1;i<=n;i++)
{
x[k]=i;
if(cont(k))
BT(k+1);
}
}
int main()
{
cout<<"n=";cin>>n;
cout<<"m=";cin>>m;
BT(1);
cout<<"Numarul de solutii: "<<nrsol;
return 0;
}
3.3.4 PROBLEMA DAMELOR

Problemă: Se dau N dame și o tablă de șah de dimensiune NxN. Să se găsească
toate modalitățile de a aranja toate damele astfel încât oricare două dame să nu se

24
atace. Două dame se atacă dacă se află pe aceeași linie, coloană sau diagonală. Se
cere să se afișeze toate solutiile si numarul lor.
Solutie:
Generam X=(X1, X2, …, Xn) cu Xi ∈ {1, 2, .., n}.
Conditii de continuare:
Dupa ce am generat X 1, X 2, …, X k-1 vom adauga X k daca:
– pentru ∀ i=1,k -1 avem X i Xk
– pentru ∀ i=1,k -1 avem |X k-Xi| |k-i|
Afisare:
Vom face afisare ca la un tablou bidimensional, X i reprezentand coloana pe care se
afla dama pe linia I , pentru ∀ i = 1, n.
Exemplu:

Fig. 3.3.4 Exemplu de date pentru problema damelor

Program C++:
#include < iostream>
#include <stdlib.h>
using namespace std;
int n,x[100],nrsol;
void afis()

25
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
if(x[i]==j) //X i reprezinta coloana pe care se afla dama
cout<<"D "; // vom afisa D pentru ca aici se afla o dama
else
cout<<"_ "; // vom afisa „_” pentru ca aici nu este nu se afla dama
cout<<endl;
}
cout<<endl;
}
int cont(int k)
{
for(int i=1;i<k;i++)
if(x[i]==x[k] || abs(x[k] -x[i])==abs(k -i)) //verificam conditiile de
continuare
return 0;
return 1;
}
void BT(int k)
{
if(k>n)
{
afis();
nrsol++;
}

26
else
for(int i=1;i<=n;i++)
{
x[k]=i;
if(cont(k))
BT(k+1);
}
}
int main()
{
cout<<"n=";cin>>n;
BT(1);
cout<<"Numarul de solutii: "<<nrsol;
return 0;
}
3.3.5 PROBLEMA COLORĂRII H ĂRȚILOR

Problemă : Se dau n țări, o matrice A si 4 culori, fiecare reprezentată de un
numar din mul țimea {1, 2, 3, 4}. Se cere s ă se calculeze toate posibilit ățiile de
colorare a h ărții astfel î ncât doua țări vecine s ă nu aib ă aceaș i culoare. Prima soluț ie
și num ărul total de solu ții se vor afisa pe ecran, iar restul solu țiilor in fisier.
Nota: dou ă țări sunt vecine daca A ij = 1, unde i si j reprezint ă țările.
Exemplu:
Pentru n=5 si matricea:
0 1 1 0 0
1 0 1 1 0
1 1 0 1 0
0 1 1 0 1

27
0 0 0 1 0

Fig. 3.3.5 Exemplu de date pentru problema colorării hărților
Matricea este patratică si simetrică. Pe diagonala principala elementele sunt nule.
Solutie:
Generam X=(X 1, X 2, …, X n) cu X i ∈ {1, 2, 3, 4}.
Condi ții de continuare:
După ce am generat X 1, X 2, …, X k-1 vom ad ăuga X k dacă:
– pentru ∀ i=1,k -1 avem A ik 1;
– pentru ∀ i=1,k -1 avem X k Xi;
Program C++:
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");
int A[100][100],x[100],n,nrsol;
void cit()
{
fin>>n; //citim n
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
fin>>A[i][j]; //citim elementele matricii A
}
void afis()
{

28
int i;
if(nrsol==1) //verificam daca avem prima solutie pentru a o afisa pe
ecran
{
cout<< "Prima solutie este: ";
for(i=1; i<=n; i++)
cout<<x[i]<<" ";
}
else //afisam solutia in fisier
for(i=1; i<=n; i++)
fout<<x[i]<<" ";
fout<<endl;
}
int cond(int k)
{
int i;
for(i=1; i<k; i++)
if((A[i][k]==1)&&(x[i]==x[k]))//verificam conditiile de continuare
return 0;
return 1;
}
void BT(int k)
{
int i;
if(k>n)
{
nrsol++;
afis();

29
}
else
for(i=1; i<=4; i++)
{
x[k]=i; //ii dam valoare lui x[k] pe una dintre cele 4 culori
if(cond(k))
BT(k+1);
}
}
int main()
{
cit();
BT(1);
cout<<endl<<"Numarul de solutii: "<<nrsol;
fin.close();
fout.close();
return 0;
}

3.3.6 PROBLEMA DETERMINĂRII SUBȘIRULUI COMUN DE LUNGIME
MAXIMĂ

Problemă: Se dau 2 vectori cu n, respectiv m componente. Se cere sa se
determine un subsir comun de lungime maxima.
Exemplu:
date.in date.out
7
8 2 5 9 4 2 7 2 9 4

30
6
1 3 2 7 9 4

Tab.3.3.6 Exemplu de date pentru determinarea subșirului comun de lungime
maximă

Solutia 1: (utilizand metoda backtracking):
Generam subsiruri ale lui X si verificam daca subsirul corespunzator este subsir si
in Y. Dintre aceste subsiruri pastram unul de lungime maxima in vectorul Z=(Z 1,
Z2, …,Z Max) -> vector cu indicii din X.
Pentru exemplul anterior avem Z=(2, 4, 5) iar Max=3 => X 2=2
X4=9
X5=4
Se va afisa X Z1, X Z2, …, X Zmax ;
Generam V=(V 1, V 2, …, V k) cu V i ∈ {1, 2, …, n}
Vi < V i+1 => V i ∈ {Vi-1+1, V i-1+2, V i-1+3, …}
Program C++:
#include < fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");
int x[100],y[100],a[100][100],alege[100][100],n,m,v[100],z[100],max;
void cit()
{
int i;
fin>>n;
for(i=1;i<=n;i++)
fin>>x[i];

31
fin>>m;
for(i=1;i<=m ;i++)
fin>>y[i];
fin.close();
}
int verif(int k)
{
int i,j;
j=1;
for(i=1;i<=k;i++)
{
while(j<=m && x[v[i]]!=y[j])
j++;
if(j>m)
return 0;
else
j++;
}
return 1;
}
void bt(int k)
{
int i;
if(verif(k -1))
if(k-1>max)
{
max=k -1;
for(i=1;i<=max;i++)

32
z[i]=v[i];
}
if(k<=n)
for(i=v[k -1]+1;i<=n;i++)
{
v[k]=i;
bt(k+1);
}
}
void afis()
{
int i;
for(i=1;i<=max;i++)
fout<<x[z[i]]<<" ";
fout<<endl;
}
int main()
{
cit();
bt(1);
afis();
return 0;
}

3.3.7 GENERAREA SUBMULȚIMILOR

33
Problemă: Să se genereze submulțimile unui număr natural n care care au
exact n/2 componente.
Exemplu:

Fig. 3.3.7 Exemplu de date pentru generarea submulțimilor

Solutie:
Multimea B ⊂ {1,2,…,n} se memoreaza folosind un vector X=(X 1, X 2, …,
Xn)
Xi = 1 daca i ∈ B;
Xi = 0 daca i nu apartine B;
Pentru a genera toate multimile B ⊂ {1,2,…,k} cu n/2 componente trebuie
să generăm vectorul X=(X 1, X 2, …, X n) cu componenta Xi ∈ {0, 1}. Suma
elementelor vectorului trebuie sa fie egala cu n/2.
Conditii de continuare:

34
S-au generat X 1,…., X k-1 si adaugam X k ∈ {0, 1}. Dacă suma de la 1 la k
din X i ≤ n/2, iar daca k=n trebuie ca suma de la 1 la k din X i = n/2.
Program C++:
#include <iostream>
using namespace std;
int n,x[100];
void afis()
{
int i;
for(i=1;i<=n; i++) //parcurgem vectorul x
if(x[i]==1) //verificam daca componenta de pe pozitia i este 1
cout<<i<<" "; //daca da, afisam pozitia
cout<<endl;
}
int cont(int k)
{
int i,s; //s este o variabila ce va fi folosita pentru a calcula suma
elementelor
s=0;
for(i=1;i<=k;i++)
s+=x[i]; //calculam suma componentelor lui x pana la pozitia k
if(s>n/2)
return 0; //daca suma este mai mare ca n/2, at unci solutia nu este
corecta;
if(k==n && s!=n/2)
return 0; //daca k este egal cu n si suma nu este n/2, atunci solutia nu
este corecta
return 1; //in cazul in care trece de cele 2 if -uri, solutia este corecta;

35
}
void BT(int k)
{
int i;
if(k>n)
afis(); //daca k>n inseamna ca avem o solutie si trebuie sa o afisam
else //altfel inseamna ca trebuie sa mai adaugam componente
for(i=0;i<=1;i++)
{
x[k]=i; //incarcam vectorul x cu valorile 0 si 1;
if(cont(k))
BT(k+1); //daca este indeplinita conditia de existenta, adaugam
inca o componenta
}
}
int main()
{
cin>>n; //citim pe n
BT(1); //incepem sa incarcam vectorul x de la componenta 1
return 0;
}

36

4. METODA PROGRAMĂRII DINAMICE

4.1 DESCRIEREA METODEI PR OGRAMĂRII DINAMICE

Metoda programării dinamice este o metodă de programare care se aplică
problemelor a căror soluție se poate construi dinamic în timp, adică deciziile care
conduc la obținerea rezultatului se pot lua pas cu pas, pe baza deciziilor de la
pasul/pașii precedenți8.
De obicei, metoda programării dinamice este adecvată în cazul problemelor
care solicită determinarea unui optim (minim sau maxim), în urma unui proces
decizional care se desfășoară în mai multe etape. , Astfel, se pornește de la o stare
inițială și la fiecare pas se ia o decizie care determină o nouă stare, până când se
ajunge la soluția finală, optimă.
Inițiatorul metodei, profesorul și cercetătorul Ric hard Bellman, a publicat în
1957 o carte cu titlul “Dynamic programming”, în care a enunțat principiul
optimalității:

8 Cerchez, Emanuela, Șerban, Marinel, Programarea în Limbajul C/C++ pentru liceu, Ed . Polirom,
Iași, 2005

37
O strategie are proprietatea că oricare ar fi starea inițială și decizia inițială,
deciziile rămase trebuie să constituie o strategie opti mă privitoare la starea care
rezultă din decizia anterioară.
Demonstrarea corectitudii algoritmului de rezolvare a unei probleme prin
programare dinamică se face, de cele mai multe ori, prin inducție matematică.
Metoda PD se poate aplica cu următoarele abo rdări:
: pentru rezovarea problemei se pleacă de la starea finală
Metoda înpoi : pentru rezovarea problemei se pleacă de la starea inițială
Metoda mixtă : o combinație a primelor două.
Programarea dinamică este o metodă de elaborare a alg oritmilor, care se
aplică de regulă problemelor în care se cere determinarea unui optim referitor la un
anumit criteriu (cel mai lung subșir, cea mai mare sumă, cel mai scurt drum etc).
Termenul a fost introdus în 1940 de către matematicianul american Rich ard
Bellman. O problemă ar putea fi rezolvată prin programare dinamică dacă poate fi
descompusă în subprobleme asemănătoare de dimensiuni mai mici și soluția optimă
a problemei depinde de soluțiile optime ale subproblemelor sale.
Când se poate folosi
blema P (de optimizare) având datele de intrare D poate fi rezolvată
prin rezolvarea aceleiași probleme P, dar cu datele deintrare d, unde d < D

Problema se poate descompune în sub -probleme suprapuse care pot fi
utlizate de mai multe ori
-problemelor pentru reutilizări viitoare
Caracteristici

Principiul optimalității

38

-o secvență optimă de decizii, fiecare decizie este optimă

Problemele care pot fi rezolvate utilizând PD se caracterizează prin următoarele
proprietăți:
1. Soluția optimă se alege dintr -o mulțime de soluții, fiecărei soluții putând să i se
asocieze o valoare. Alegerea soluției optime înseamnă alegerea soluției care are
valoarea optimă.(minimă sau maximă în funcție de cerința problemei).
2. substructura optimală – problema poate fi descompusă în subprobleme similare
cu problema inițială ce respectă principiul optimalității, iar soluțiile optime ale
subproblemelor determină soluția optimă a problemei inițiale (în acest caz s -ar
putea aplica și una dintre metodele Greedy sau Divide -et-Impera)
3. subprobleme superpozabile – subproblemele nu sunt independente ci se suprapun
(Divideet -Impera nu se poate aplica; redundanța foarte mari a operațiilor o face
inutilizabilă, vezi Fibonacci ); soluțiile subproblemelor se vor reține într -un tablou
(vector sau matrice).
4. Soluția problemei este dată de un vector S={x 1,x2,…,x m} și
→ există o mulțime finită A din care se poate alege un element x i al soluției;
→ fiecare etapă de determinare a unui el ement xi al soluției se bazează pe
rezultatele etapelor în care s -au determinat elementele anterioare ale soluției;
→ numărul de posibilități de a alege un element x i al soluției se reduce din
cauza cerințelor de optimizare și a restricțiilor impuse soluției .

Algoritmul proiectării dinamice

Etapele de rezolvare a unei probleme prin metoda programării dinamice sunt;

39
PAS1 Se demonstrează că problema are o substructură optimă folosind
metoda reducerii la absurd;
PAS2 Se caracterizează structura unei soluții optime prin descompunerea
problemei în subprobleme;
PAS3 Se definește recursiv valoarea soluției optime;
PAS4 Se calculează valoarea soluției optime într -o manieră de jos în sus
(”bottop –up);
PAS5 Se construiește soluția optimă din informațiile opținute p rin calcularea
valorii soluției optime.

4.2 IMPLEMENTAREA METODEI PROGRAMĂRII DINAMICE

Pentru implementarea metodei programării dinamice se vor folosi următoarele
subprograme:
ƨ subprogramul unit() – care inițializează variabilele de memorie și
structurile de date folosite pentru construirea soluției:
ƨ subprogramul p_dinamica() – care calculează valoarea soluției optime;
ƨ subprogramul afișează() – care afișează soluția problemei folosind
informațiile obținute prin calcularea valorii soluției optime.

4.3 PROBLEME REZOLVABILE PRIN METODA PROGRAMĂ RII DINAMICE

4.3.1 AFIȘAREA UNEI SECVENȚ E CRESCĂTOARE DE LUN GIME MAXIMĂ A
UNUI VECTOR

Problemă: Se da X=(X 1, X 2, …, X n). Vrem o secventa crescatoare de lungime
maxima.
Exemplu:

40
Date de intrare Date de iesire
10
8 2 5 9 4 5 9 10 20 3 4 5 9 10 20

Tab. 4.3.1 Exemplu de date pentru afișarea unei secvențe crescătoare de lungime
maximă într -un vector
Solutie:
1) Subproblema: determinam secventa crescatoare de lungime maxima care se
termina cu X i.
2) Structuri de date:
L[i]=lungime secventei crescatoare de lungime maxima care se termina in X i.
3) Formule de calcul
L[1]=1
∀ i = 2,n
Daca X[i -1]<X[i] atunci
L[i]=L[i -1]+1
Altfel
L[i]=1
4) Afisam solutia
Determinam Max din L si pozitia lui
Lpoz-Max+1 … L poz
Program:
#include <fstream>

using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");
int n,x[100],l[100]; /*declaram numarul de componente, vectorul componentelor

41
si un vector in care vom salva lungimile secventelor crescatoare */
void cit()
{
fin>>n; //citim numarul de componente
for(int i=1;i<=n;i++)
fin>>x[i]; //citim elementele vectorului
fin.close(); //inchidem fisierul de intrare
}
void PD()
{
int i;
l[1]=1; //fiind prima componenta, lungime secventei crescatoare va fi 1
for(i=2;i<=n;i++)
if(x[i -1]<x[i]) //verificam daca componentele sunt in ordine crescatoare
l[i]=l[i -1]+1; //in caz afirmativ, secventa curenta va creste cu o unitate
else
l[i]=1; //altfel se va incepe o noua secventa
}
void afis()
{
int Max,poz,i; //vom folosi variabila Max pentru a gasi secventa de l maxima si
variabila poz pentru afisarea acesteia
Max=l[1];
poz=1;
for(i=2;i<=n;i++) //parcurgem vectorul lungimilor
if(l[i]>Max) //verificam daca lungimea secv. cresc. care se termina in x[i]
este mai mare decat maxima curenta
{

42
Max=l[i]; //daca da, Max ia valoarea lui l[i]
poz=i; //iar pozitia devine i
}
for(i=poz -Max+1;i<=poz;i++)
fout<<x[i]<<" ";
}
int main()
{
cit();
PD();
afis();
fout.close();
return 0;
}
4.3.2 PROBLEMA SUBȘIRULUI COMUN MAX IMAL

Problema: Se dau 2 vectori cu n, respectiv m componente. Se cere sa se
determine un subsir comun de lungime maxima .
Descompunerea in subprobleme: determinarea unui subsir comun de lungime
maxima pentru X 1, X 2, …, X i si Y 1, Y 2, …, Y j => subproblema care depinde de i si j.
Structuri de date folosite:
Tabloul bidimensional A unde A ij este lungimea maxima a unui subsir
comun pt X 1, X 2, …, X i si Y 1, Y 2, …, Y j.
Tabloul bidimensional Alege unde Alege ij va avea valorile 1, 2 sau 3 . Valoarea 1 o
vom folosi pentru afisarea solutiei.
Formule de calcul:
1) A ij=A i-1j-1+1 daca X i=Y j => Alege ij=1;
2) A ij=A i-1j daca X i Yj si A i-1j Aij-1 => Alege ij=2;

43
3) A ij=A ij-1 daca X i Yj si A i-1j Aij-1 => Alege ij=3;
Cazuri particulare:
1) A i0=0, ∀ i=1,n;
2) A 0j=0, ∀ j=1,m;
Program C++:
#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");
int x[100],y[100],a[100][100],Alege[100][100],n,m;
void cit()
{
int i;
fin>>n;
for(i=1;i<=n;i++)
fin>>x[i];
fin>>m;
for(i=1;i<=m;i++)
fin>>y[i];
fin.close();
}
void PD()
{
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(x[i]==y[j])
{

44
a[i][j]=a[i -1][j-1]+1;
Alege[i][j]=1;
}
else
if(a[i -1][j]>=a[i][j -1])
{
a[i][j]=a[i -1][j];
Alege[i][j]=2;
}
else
{
a[i][j]=a[i][j -1];
Alege[i][j]=3;
}
}
void afis(int i,int j)
{
if(i>0 && j>0)
if(Alege[i][j]==1)
{
afis(i -1,j-1);
fout<<x[i]<<" ";
}
else
if(Alege[i][ j]==2)
afis(i -1,j);
else
afis(i,j -1);

45
}
int main()
{
cit();
PD();
afis(n,m);
fout.close();
return 0;
}

4.3.3 PROBLEMA SUMEI MAXIME ÎNTR -UN TRIUNGHI

Problemă: Se da un triunghi de dimensiune n cu numere naturale ca mai jos:
A11
A21 A22
A31 A32 A33
A41 A42 A43 A44
………………………..
An1 An2 An3 An4 … Ann
Definim notiunea da lant in triunghi ca fiind un sir de elemente care porneste din
A11 si contine care un nr de pe fiecare linie, orice doua elemente alaturate fiind in
situatia:
1 2
ssss sau ssss

Se cere sa se determine un lant cu suma elementelor maxima.

46
Exemplu:
DATE .IN DATE .OUT
4
5
2 1
1 4 2
1 5 5 3 16
5 2 4 5
Tab 4.3.3 Exemplu de date pentru afițarea sumei de lungime maximă într -u
triunghi – metoda programării dinamice
Solutie:
Subproblema: Determinati un lant de suma maxima de la (i, j) care se termina intr –
un element pe linia n.
Structuri de date:
B[i][j] = suma cea m ai mare a unui lant de la (i, j) la (n, j).
C[i][j] = 1 pentru situatia 1
= 2 pentru situatia 2
Relatii de recurenta:
B[n][j] = A[n][j] ∀ j = 1, n;
∀ i = n-1, 1
Daca B[i+1][j] > B[i+1][j+1]
B[i][j] A[i][j] + B[i+1][j]
C[i][j] 1
Altfel
B[i][j] A[i][j] + B[i+1][j+1]
C[i][j] 2

Program C/C++:

47
#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");
int n, a[100][100], b[100][100], c[100][100];
void cit()
{
int i,j;
fin>>n;
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
fin>>a[i][j];
fin.close();
}
void afis()
{
int i,j;
for(i=1; i<=n; i++)
{
for(j=1; j<=i; j++)
fout<<b[i][j]<<" ";
fout<<endl;
}
}
void PD()
{
int i,j;
for(j=1;j<=n;j++)

48
b[n][j]=a[n][j];
for(i=n -1;i>=1;i –)
for(j=1;j<=n;j++)
if(b[i+1][j]>b[i+1][j+1])
{
b[i][j]=a[i][j]+b[i+1][j];
c[i][j]=1;
}
else
{
b[i][j]=a[i][j]+b[i+1][j+1];
c[i][j]=2;
}
}
int main()
{
cit();
PD();
afis();
return 0;
}
4.3.4 PROBLEMA SUBȘIR CRESC ĂTOR DE LUNGIME MAXI MĂ.

Fie n numar natural si vectorul X = (X 1, X 2, …, X n). Sa se gaseasca un subsir
de lungime maxima. In cazul in care nu exista se va afisa pe ecran textul „Nu
exista”.
Exemplu:

49
date.in date.out
10
7 5 1 6 2 9 1 1 10 20 5 6 9 10 20
Tab. 4.3.44 Exemplu de date pentru afișarea subșirului crescător de lungime
maximă
Solutie:
Subproblema: determinati sirurile crescatoare ce incep cu X i.
Structuri de date:
– Li = lungime maxima a unui subsir care incepe in componenta i a vectorului
X;
– Pi = pozitia ter menului urmator a lui X i in subsir;
Formule:
L[n] = 1;
P[n] = 0;
∀ i = n-1, 1
Max = 0;
poz = 0;
∀ j = i+1, n
daca L[j] > Max si X[i] < X[j]
Max L[j];
Poz j;
L[i] Max+1;
P[i] poz;

Afisarea solutiei:
Determinam maximul si pozitia acestuia in L.
Pentru exemplul dat: Max = 5 si poz = 2;
Afisam astfel:

50
cat timp ( poz>0 )
afiseaza X[poz];
poz = p[poz];

Program C/C++:
#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");
int n,Max,poz,x[100],l[100],p[100];
void cit()
{
fin>>n; //citim numarul de componente
for(int i=1;i<=n;i++)
fin>>x[i]; //citim elementele vectorului
fin.close(); //inchidem fisierul de intrare
}
void PD()
{
int i,j;
l[n]=1;
p[n]=0;
for(i=n -1;i>=1;i –)
{
Max=0;
poz=0;
for(j=i+1;j<=n;j++)

51
if(l[j]>Max && x[i]<x[j])
{
Max=l[j];
poz=j;
}
l[i]=Max+1;
p[i]=poz;
}
}
void afis()
{
while(poz)
{
fout<<x[poz]<<" ";
poz=p[poz];
}
}
int main()
{
cit();
PD();
afis();
fout.close();
return 0;
}
4.3.5 PROBLEMA RUCSACULUI

52
Problemă: Se dă n numaru natural si o multime de n obiecte, fiecare obiect
avand o greutate si un profit propriu. Se cere sa se gaseasca o submultime de
obiecte care are un profit maxim, dar sa nu depaseasca o greutate g data.
Exemplu:
date.in date.out
5 8
1 3
3 4
4 6
1 9
3 5 Suma maxima a profiturilor este 21
Tab. 4.3.5 Exemplu de date pentru rezolvarea problemei rucsacului.
Avem ca date de intrare:
– n, numarul total de obiecte ;
– g, greutatea maxima a obiectelor din rucsac ;
– Xi, greutatea obiectului i ;
– Yi, profi tul obiectului i ;
Vom folosi o functie maimare cu doi parametrii pentru a determina maximul dintre
2 numere.
int maimare(int a,int b)
{
if(a>b)
return a;
else
return b;
}
Subproplema : determinarea profitului maxim.
Structuri de date:

53
Matricea A unde A ij poate avea una din cele trei valori:
– 0, daca i = 0 ;
– Ai-1 j , daca i > 0 si j < X i ;
– maimare( A i-1 j , A i-1 j-x[i]+y[i] ) , daca i > 0 si j Xi ;

Formule de calcul : vom folosi o functie recursiva PD cu doi parametrii, i si j.
daca (i = 0)
atunci returneaza 0 ;
daca (A i j 0)
atunci returneaza A i j ;
daca (j < X i)
atunci returneaza A i-1 j = PD(i -1, j) ;
returneaza A i j = maimare( PD(i -1, j) , PD(i -1, j-Xi) + Y i ) ;
Afisare: vom afisa rezultatul functiei PD folosind ca parametrii valorile n si g.
Program C/C++:
#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");
int a[100][100], n, g, x[100], y[100];
void cit() //folosim o functie pentru citire
{
int i;
fin>>n>> g; //citim numarul de obiecte si greutatea maxima admisa
for(i=1; i<=n; i++)
fin>>x[i]>>y[i]; //citim greutatea, respectiv profitul fiecarui obiect
fin.close(); //inchidem fisireul de intrare

54
}
int maimare(int a,int b) //vom folosi o fucti e care ne determina numarul mai
mare dintre 2 valori
{
if(a>b)
return a;
else
return b;
}
int PD(int i,int j)
{
if(i==0)
return 0; //daca i este 0, atunci nu avem elemente
if(a[i][j]!=0)
return a[i][j]; //a[i][j] diferit de 0, inseamna ca avem un element
if(j<x[i])
return a[i -1][j]=PD(i -1,j);
return a[i][j]=maimare(PD(i -1,j),PD(i -1,j-x[i])+y[i]); //vom returna
valoarea mai mare deoarece avem nevoie de maxim
}
int ma in()
{
cit(); //apelam functia de citire
fout<<"Suma maxima a profiturilor este "<<rucsac(n,g); //afisam pentru
n elemente si greutatea data
fout.close();
return 0;
}

55

4.3.6 NUMARUL DE SECVENTE P ARE DE LUNGIME MAXIM A INTR -UN
VECTOR

Numim secvență pară într -un șir o succesiune de termeni ai șirului cu
proprietatea că sunt numere pare și că se află pe poziții consecutive în șir; orice
secvență are cel puțin doi termeni și este maximală în raport cu proprietatea
precizată (dacă i se ada ugă un alt termen, secvența își pierde această proprietate).
Lungimea secvenței este egală cu numărul termenilor săi.
Fișierul date.in conține un numar n si elementele vectorului X.
Problemă: Se cere să se afișeze pe ecran numărul de secvențe pare de
lungime maximă din șir.
Exemplu:
Date de intrare Date de iesire
9
8 2 6 4 5 2 10 20 13 Numarul de solutii este 1
Tab. 4.3.6 Exemple de date pentru numărulde secvențe pare de lungime maximă
într-un vector
Solutie:
1) Subproblema : determinam secventa crescatoare de lungime maxima care se
termina cu X i.
2) Structuri de date:
L[i]=lungime secventei crescatoare de lungime maxima care se termina in X i.
3) Formule de calcul
L[1]=1
∀ i = 2,n
Daca X[i]%2==0 atunci
L[i]=L[i -1]+1

56
Altfel
L[i]=1

4) Afisam solutia
Determinam Max din L.
Afisam numarul de solutii.
Program C++:
#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");
int n,x[100],l[100]; /*declaram numarul de componente, vectorul
componentelor
si un vector in care vom salva lungimile secventelor de
numere pare */
void cit()
{
fin>>n; //citim numarul de componente
for(int i=1;i<=n;i++)
fin>>x[i]; //citim elementele vectorului
fin.close(); / /inchidem fisierul de intrare
}
void PD()
{
int i;
l[1]=1; //fiind prima componenta, lungime secventei crescatoare va fi 1
for(i=2;i<=n;i++)
if(x[i]%2==0) //verificam daca componenta curenta este para

57
l[i]=l[i -1]+1; //in caz afirmativ, secventa curenta va creste cu o
unitate
else
l[i]=1; //altfel se va incepe o noua secventa
}
void afis()
{
int Max,nrsol,i; //vom folosi variabila Max pentru a gasi secventa de l
maxima
Max=l[1];
nrsol=0; //in var iabila nrsol vom salva numarul de solutii
for(i=2;i<=n;i++) //parcurgem vectorul lungimilor
if(l[i]>Max) //verificam daca lungimea secv. cresc. care se termina in
x[i] este mai mare decat maxima curenta
Max=l[i]; //daca da, Max ia valoarea lui l[i]
for(i=1;i<=n;i++)
if(l[i]==Max)
nrsol++; //daca lungime secventei pare pana la elementul curent este
egal cu maximul, crestem numarul de solutii
fout<<"Numarul de solutii este "<<nrsol; //afisam nt de solutii
}
int main()
{
cit(); //apelam functia de citire
PD();
afis(); //apelam functia de afisare
fout.close(); //inchidem fisierul de iesire
return 0;

58
}

CONCLUZII

În mod asemănător, aceeași diferență de abordare va exista între doi
algoritmi de soluționare a aceleași probleme, unul recursiv – backtracking – și altul
iterativ – proiectat prin metoda programării dinamice.
Indiferent de forma particulară ce o poate lua sau de modul în care este
“citită” în final soluția, esențialul constă în faptul că backtracking -ul este o metodă
de programare ce conține obligatoriu gestiune de stivă . Lipsa instrucțiunilor,
explicite sau “transparente”, de gestionare a stivei într -un program (de exemplu,
lipsa a pelului recursiv), este un indiciu sigur de recunoaștere a faptului că acel
algoritm nu folosește metoda sau strategia de rezolvare BackTracking.
Programarea dinamică este o metodă sau strategie ce își propune să
elimine dezavantajele metodei recursive care, în ultimă instanță, am văzut că se
reduce la parcurgerea în adâncime a arborelui apelurilor recursive (adică
backtracking). Dezavantajele acestei metode provin din faptul că, pentru a ține
minte pașii gata calculați și a evita repetarea calculării lor ( în termeni de grafuri,

59
pentru a evita calcularea repetată a unor noduri pe ramuri diferite ale arborelui
apelurilor recursive), este nevoie de punerea la dispoziție a extra -spațiului de
memorare necesar și de un efort suplimentar dat de gestiunea de memori e
suplimentară.

BIBLIOGRAFIE

1. Panaitopol L., Bălucă M. , Manual de clasa a X -a, Editura Gil, 2001
2. Udriște c., Țevy I., Necșuleu G., Necșuleu I., Gușatu M., Crăciun M., Saulea T.,
Nicula V., matematică manual pentru clasa a X -a, Editura Fair Partners, 2005.
3. Andonie R., Gârbacea I., Algoritmi fundamentali, o perspectivă C++, editura
Libris, Cluj Napoca, 1995
4. Miloșescu M., Informatică intensiv C++, Manual pentru clasa a XI -a, Editura
didactică și pedagogică, R.A.,2013
5. Valeriu LUPU, Algo ritmi.Tehnici și limbaje de programare, Editura universității
Ștefan cel Mare Suceava.
6. Cerchez, Emanuela, Șerban, Marinel, Programarea în Limbajul C/C++ pentru
liceu, Ed. Polirom,Iași, 2005
7. Algoritmi și structuri de date, Note de curs ,Olidej.wikispa ces.com, , accesat
iunie 2017

60

ANEXE
Anexa 1 Rezolvarea problemei spectacolelor folosind tehnica de programare
Greedy
Problemă: Se dau n spectacole ce se pot sustine intr -o singura sala in intervalele
orare (A i, Bi) ∀ i = 1, n. Se cere sa se planifice un numar maxim de spectacole.
Exemplu:
date.in date.out
6
20 40
55 100
75 80
25 50
60 70
5 30 6 5 3
Tab. A.1.1 Exemplu de date pentru rezolvarea problemei spectacolelor prin tehnica
greedy

61
Solutie:
1) Citim n, (A i, Bi) ∀ i = 1, n. O i i.
2) Ordonam spectacolele crescator dupa B i si interschimbam.
3) Afisam spectacolele planificate:
k 1
afis O 1
∀ i = 2, n
daca A i Bk atunci
scrie O i
k i

Program C/C++ :
#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");
int a[100],b[100],o[100],n;
void cit()
{
int i;
fin>>n;
for(i=1;i<=n;i++)
{
fin>>a[i]>>b[i];
o[i]=i;
}

62
}
void inter(int &a, int &b)
{
int aux;
aux=a;
a=b;
b=aux;
}
void ord()
{
int i,j;
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++)
if(b[i]>b[j])
{
inter(a[i],a[j]);
inter(b[i],b[j]);
inter(o[i],o[j]);
}
}
void greedy()
{
int i,k;
ord();
k=1;
fout<<o[1]<<" ";
for(i=2;i<=n;i++)
if(b[k]<=a[i])

63
{
fout<<o[i]<<" ";
k=i;
}
}
int main()
{
cit();
greedy();
return 0;
}

ANEXA 2 .CALCULAREA CELUI MAI MARE DIVIZOR COMUN FOLOSI ND
TEHNICA DIVIDE ET IM PERA .
Problemă: Se da n numar natural si un vector X cu n componente numere naturale.
Se cere sa se afle CMMDC al acestor numere.
Exemplu:

Fig. A.2.1 Exemplu de date pentru calculul CMMDC prin tehnica divide et impera
Program C/C++:
#include<iostream>
using namespace std;
int x[100],n;
void cit() //vom folosi o functie pentru citire
{
cin>>n;

64
for(int i=1; i<=n; i++)
cin>>x[i];
}
int cmmdc(int p, int q) //vom folosi o functie pentru calcularea CMMDC a doua
numere
{
while(p!=q)
if(p>q)
p=p-q;
else
q=q-p;
return p;
}
int dei(int m1, int m2)
{
if(m1==m2)
return x[m1];
else
{
int p,q ;
p=dei(m1,(m1+m2)/2);
q=dei((m1+m2)/2+1,m2);
cmmdc(p,q);
}
}

int main()
{

65
cit();
cout<<dei(1,n);
return 0;
}