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

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

CUPRINS

INTRODUCERE ………………………….. ………………………….. ………………………….. …… 6
1. PROBLEME DE NUMĂRARE ………………………….. ………………………….. ……… 7
1.1 Definirea termenilor ………………………….. ………………………….. …………………… 7
1.2 Metode de rezolvare a problemelor de numărare ………………………….. …….. 7
2. TEHNICI DE PROGRAMARE ………………………….. ………………………….. ……. 10
2.1 Analiza algoritmilor ………………………….. ………………………….. …………………. 10
2.2 Metode de construire a algoritmilor ………………………….. ………………………. 12
3.METODA BACKTRACKING ………………………….. ………………………….. ………. 14
3.1 Descrierea metodei backtracking ………………………….. ………………………….. 14
3.2 Implementarea metodei backtracking ………………………….. …………………… 17
3.3 Probleme de numărare care pot fi rezolvate prin metoda backtracking 19
3.3.1Generarea permutări lor ………………………….. ………………………….. ………… 19
3.3.2 Generarea numerelor naturale ………………………….. ………………………….. 22
3.3.3 Generarea combinărilor ………………………….. ………………………….. ……….. 24
3.3.4 Problema damelor ………………………….. ………………………….. ……………….. 27
3.3.5 Problema determinării subșirului comun de lungime maximă ………….. 29
3.3.6 Generarea submulțimilor ………………………….. ………………………….. ……… 33
4. METODA PROGRAMĂRII DINAMICE ………………………….. ………………….. 36
4.1 Descrierea metodei programării dinamice ………………………….. …………….. 36
4.2 Implementarea metodei programării dinamice ………………………….. ……… 39
4.3 Probleme care pot fi rezolvate prin metoda programării dinamice …….. 39
4.3.1 Afișarea unei secvențe crescătoare de lungime maximă a unui vector . 39
4.3.2 Problema subșirului comun maximal ………………………….. ………………… 42

4
4.3.3 Problema sumei maxime într -un triunghi ………………………….. …………… 45
4.3.4 Problema subșirului crescător de lungime maximă. ………………………… 48
4.3.5 Problema rucsacului ………………………….. ………………………….. ……………. 51
4.3.6 Determinarea Numarului de secvențe pare de lungime maxima într-un
vector ………………………….. ………………………….. ………………………….. ……………… 54
CONCLUZII ………………………….. ………………………….. ………………………….. ……….. 58
BIBLIOGRAFIE ………………………….. ………………………….. ………………………….. …. 59
ANEXE ………………………….. ………………………….. ………………………….. ……………….. 60
Anexa 1Rezolvarea problemei spectacolelor folosind tehnica de programare
Greedy ………………………….. ………………………….. ………………………….. ……………… 60
Anexa 2 .Calcularea celui mai mare divizor comun folosind tehnica divide et
impera. ………………………….. ………………………….. ………………………….. ……………… 63

5
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 Exemplu 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
Tab. A.1.1 Exemplu de date pentru rezolvarea problemei spectacolelor prin
tehnica greedy

6
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 unei
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 backtrackink ș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 necesită foarte mult studiu, of eră î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 capitol este important în p rima 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 construier a algoritmilor. Capit olul 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 metodei în rezolvarea unor
probleme. Capitolul 4 tratează problematica implementării în C++ a unor probleme
utilizând metoda programării dinamice, descrierea metodei, construirea
algoritmului, implementare și aplicații ale metodei în rezolvarea unor probleme .

7
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 vedere al cantității de
informație cât mai ales din punc tul 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 caracterizare 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 c onstă î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 PROBLE MELOR DE NUMĂRARE

Există probleme de combinatorică simple a căror soluție vine de la sine, î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ăr are.

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

8
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 constr uiesc propoziții generale, P(n)
cu n ∈ N, care pot fi adevărate sau false. Principiul inducției matematice este
următorul: dacă o propoziție P(n) care depinde de numărul natural n, unde n ≥ m, m
fiind un număr natural fixat și dacă propoziția este adevărată pentru n=m și pentru
n=k,atunci rezultă că ea este devărată și pentru numărul natural n=k+1 deci, prin
inducție, propoziția P(n) este adevărată pentru oricare număr n ≥ m;
2. Metoda mulțimilor finite ordonate reprezintă o categorie aparte a
problemelor de numărare numite,în literatura de specialitate probleme de
combinatorică. Acest tip de probleme 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 ția 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 reprezintă 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 numes c permutări ale acestei mulțimi.
Notație : număr ul P(n) al tuturor permutărilor unei mulțimi A cu n elemente,
cu n ∈ N* este P n =1· 2 · ……. ·n;
4. Metoda a ranjamente lor – 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 fi xat, numărul aranjamentelor ( din A) de n elemente luate câte k este
= n(n -1)············(n -k+1) sau =
=
;

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.

9
5. Metoda c ombinări lor 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, astfel
î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. În funcție de algoritmii aleși se procedează
la descompune rea problemei de rezolvat în probleme mai mici , numite
subprobleme , se rezolvă subproblemele și apoi se combină soluțiile obținute pentru
a obține soluția finală .

10
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 parcurse în rezolvarea unei probleme 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 transcrierea metodei d e rezolvare
matematice într -un limbaj de programare ;

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

11
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
algoritmului. 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ă unitatea 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 l ogaritmic, ordin de complexitate O(logn ). Exemplu 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).

12

2.2 METODE DE CONSTRUIRE A ALGORIT MILOR

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 încadrează î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 problemelor 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 corespunzator 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

13

→ Construcția modelului matematic evidențiază și elimină aspecte ale
problemei care pot fi omise sau sunt formulate ambig uu.
→ 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 de model
matematic si pune la dispozitie procedeee prin care se poate construi si implementa
un model particular corespunzator unei probleme.
Cele mai cunoscute metode de proiect are a algoritmilor s unt urmatoarele:
 divide et impera pentru probleme care pot fi descompuse în
subprobleme asemănătoare cu problem a inițială, pot fi rezolvate prin
aceeași metodă și sunt independente unele de altele( exemplu de
rezolvare a unei probleme folosind metoda divide et impera anexa 2 );
 greedy se folosește pentru problemele în care se cer mulțimi
care îndeplinesc anumite condiții și oferă o singură soluție rezultat
(exemplu de rezolvare a unei probleme folosind metoda greedy –
anexa 1) ;
 programarea dinamica, metodă ce va fi tratată în capitolul IV;
 backtracking , definire și exemplu în capitolul III.

14

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 reprezent a 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 neste 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 determina 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 posibil e ș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

15
Metoda backt racking 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 x k i se atribuie o valoare numai dacă au fost atribuite deja valori lui x 1 ,… x k-1 .
Mai mult, odată o valo are 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 satisfăcute . Dacă nu sunt îndeplinite condițiil e de continuare se face
o altă alegere pentru x k sau dacă S k a fost epuizat atunci micșorăm pe k cu o unitate
încercând să facem o nouă alegere pentru x k etc. Posibilitatea micșorării lui k cu o
unitate dă numele metodei, ilustrând faptul că atunci când nu se mai poate avansa,
se urmărește înapoi secvența curentă din soluție. În cazul rezolvării problemelor
utilizând această metodă este foarte importantă relația între condițiile de continuare
și condițiil e interne care sunt în strânsă legătură . Alegerea unor condiții de
continuare optime au efect asupra eficienței algoritmului întrucât acestea pot crește
sau reduce reduce numărul de calcule.
Algoritmul metodei backtracking poaate fi generalizat pentru oric e
problemă care îndeplinește următoarele condiții:
1. Soluția problemei poate fi pusă sub forma unui vector X= {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. În această etapă se alege primul element al soluției S: x 1∈Ai;
PAS2. În această etapă sunt parcurse elementele mulțimii A i și nu se trece la
pasul următor decât după ce au fost parcurse toate. Cu alte cuvinte se execută
programul de câte ori este necesar în funcție de numărul de elemente ale mulțimii

7 Miloșescu M, Idem

16
A. 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ă:
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 alsoluț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 element a i în mulțimea A k+1, astfel încât x k+1 = ai,
să aparțină soluției problemei, atunci se at ribuie 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 nici 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 el ement 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 soluția problemei, adică dacă s -au găsit
toate elementele mulțimii S. Dacă s-a găsit soluți a 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.

17
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 str uctura de date de tip stivă:
 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-1se 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

18
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;
ƨ 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 diferit ordinul de
complexitate al algoritmului este:
Notăm:
mmin= min(card(A 1) x card (A 2) x …. x card(A n)

19
ș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)

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

Poate fi rezolvată prin m etoda backtracking orice problemă în care se cere
găsirea 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; e xemple:
c) probleme în plan, atunci 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 .

20
Exemplu:

Fig. 3.3.1 Generarea permutărilor

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 .
Condi ții par țiale:
Dacă s-au generat elementele X1 … X k-1 adaug ăm elementul Xk∈ {1, 2, ..,
n} dac ă:
X[k]%2==k%2 și X[k] ≠ X[i] //elementul de pe poziția k din vectorul X
are aceeași paritate cu k și elementul de pe poziția k din vectorul X este diferit de
elementul de pe poziția i din vectorul X.
Program C++:
#include <iostream>
using namespace std;
int n,x[100];
void afis()
{

21
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 dac ă un element curent are paritate diferit ă
de pozi ția sa
return 0; //in caz afirmativ, solu ția nu este corect ă
int i;
for(i=1;i<k;i++) //parcurgem vectorul x p ână la componenta curent ă
if(x[k]==x[i]) //dac ă se mai g ăsește cel pu țin o component ă egală cu
cea curent ă soluția nu este corect ă
return 0;
return 1; //dac ă programul trece de cele 2 if -uri, solu ția este corect ă
}
void BT(int k)
{
int i;
if(k>n)
afis(); //daca k>n inseamn ă că avem o solu ție și trebuie s ăa o afi șăm
else //altfel înseamn ă că trebuie s ă mai ad ăugăm componente
for(i=1;i<=n;i++)
{
x[k]=i; // încărcăm vectorul x cu valori între 1 si n
if(cont(k))

22

BT(k+1); //dac ă este îndeplinit ă condi ția de existen ță, adaug ăm
înca o component ă
}
}

3.3.2 GENERAREA NUMERELOR NATURALE

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

Fig.3.3.2 Exemplu de date pentru generarea numerelor naturale
Solutie:
Generăm X=(X 1, X 2, …, X n) cu X i ∈ {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 X k ∈ {0, 1, 2, .., 9} daca:
k=1 si X k ≠ 0 și num ărul de cifre de 1 ≤ q.
Daca k=n atunci ad ăugăm X k dacă numarul de cifre de 1 = q.
Program C++:

23
#include <iostream>
using namespace std;
int n,q,x[100]; //declarăm numărul de cifre, numărul de cifre de 1 si vectorul
in care vom salva soluțiile
void afis()
{
int i;
for(i=1;i< =n;i++) //parcurgem vectorul x
cout<<x[i]<<" "; //afisăm componenta i
cout<<endl;
}
int cont(int k)
{
int nr,i;
if(k==1 && x[k]==0) //pentru că este un numar, prima cifră nu poate fi 0
return 0; //dac ă este 0, soluția nu est e corectă
nr=0;
for(i=1;i<=k;i++)
if(x[i]==1)
nr++; //afl ăm câți de 1 se afla in num ăr
if(nr>q)
return 0; //dac ă acest num ăr dep ășeste pe q, solu ția nu este corect ă
if(k==n && nr!=q)
return 0; //dac ă ne afl ăm la ultima component ă și num ărul de 1 este
diferit de q, solu ția nu este corect ă
return 1; //daca programul a trecut de toate if -urile avem o solu ție corect ă
}
void BT(int k)

24
{
int i;
if(k>n)
afis(); //daca k>n înseamn ă că avem o solu ție ți trebuie s ă o afișăm
else //altfel înseamn ă că trebuie sa mai ad ăugăm componente
for(i=0;i<=9;i++)
{
x[k]=i; //inc ărcăm vectorul x cu valori intre 0 si 9
if(cont(k))
BT(k+1); //dac ăa este îndeplinit ă condi ția de existen ță, adaug ăm
încă o component ă
}
}
int main()
{
cin>>n>>q; //citim pe n si pe q
BT(1); // începem sa încărcăm vectorul x de la componenta 1
return 0;
}

3.3.3 GENERAREA COMBINĂRILO R

Problema: Se citesc n și m două numere naturale care îndeplinesc condiția că
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} .

25
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 avem 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:

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;

26
}
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;
}
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);

27
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
atace. Două dame se atacă dacă se află pe aceeași linie, coloană sau diagonală. Se
cere să se afișeze toate solutiile si numa rul lor.
Solutie:
Generam X=(X 1, X 2, …, X n) cu X i ∈ {1, 2, .., n}.
Cond iții de continuare:
După 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|
Afișare:
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

28

Program C++:
#include <iostream>
#include <stdlib.h>
using namespace std;
int n,x[100],nrsol;
void afis()
{
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;
}

29
void BT(int k)
{
if(k>n)
{
afis();
nrsol++;
}
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 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.

30
Exemplu:
date.in date.out
7
8 2 5 9 4 2 7
6
1 3 2 7 9 4 2 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()
{

31
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();
}
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))

32
if(k-1>max)
{
max=k -1;
for(i=1;i<=max;i++)
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;
}

33

3.3.6 GENERAREA SUBMULȚIMILOR

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;

34
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:
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 su ma este mai mare ca n/2, atunci solutia nu este
corecta;

35
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;
}
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 fi nală, optimă.
Inițiatorul metodei, profesorul și cercetătorul Richard Bellman, a publicat în
1957 o carte cu titlul “Dynamic programming”, în care a enunțat principiul
optimalității:
O strategie are proprietatea că oricare ar fi starea inițială și decizia inițială,
deciziile rămase trebuie să constituie o strategie optimă 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 abordă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 pri melor două.

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

37
Programarea dinamică este o metodă de elaborare a algoritmilor, 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).
Terme nul a fost introdus în 1940 de către matematicianul american Richard
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 sol uțiile optime ale subproblemelor sale.
Când se poate folosi
prin rezolvarea aceleiași probleme P, dar cu datele deintrare d, unde d < D
decizii dec1 , dec2 , …

-probleme suprapuse care pot fi
utlizate de mai multe ori
-problemelor pentru reutilizări viitoare
Caracteristici
ă soluția optimă întotdeauna

Principiul optimalității

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

Problem ele 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).

38
2. substructura optimală – problema poate fi descompusă în subprobleme similare
cu problema inițială ce respectă principiul optimalității, iar soluțiile optimeale
subproblemelor determină soluția optimă a problemei inițiale (în acest caz s -ar
puteaaplica ș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 m ari 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 xi al soluției;
→ fiecare etapă de determinare a unui element 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;
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 c onstruiește soluția optimă din informațiile opținute prin calcularea
valorii soluției optime.

39
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 CARE POT FI REZOLVAT E 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:
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:

40
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
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(); //in chidem fisierul de intrare
}
void PD()
{

41
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
{
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();

42
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 Alegeunde 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;
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;

43
void cit()
{
int i;
fin>>n; //citim n
for(i=1;i< =n;i++)
fin>>x[i]; //citim componenta i a vectorului x
fin>>m; citim m
for(i=1;i<=m;i++)
fin>>y[i]; //citim componenta i a vectorului y
fin.close();
}
void PD()
{
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(x[i]==y[j]) //verificăm dacă există componente eg ale
{
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

44
{
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);
}
int main()
{
cit();
PD();
afis(n,m);
fout.close();
return 0;
}

45

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
situa tia:
1 2
ssss sau ssss

Se cere sa se determine un lant cu suma elementelor maxima.
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:

46
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 mai 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++:
#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++)

47
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++)
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
{

48
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 ULUI CRESCĂTOR DE LUNGIME MAXIMĂ .

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:
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;

49
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:
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];

50
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++)
if(l[j]>Max && x[i]<x[j])
{
Max=l[j];
poz=j;
}
l[i]=Max+1;
p[i]=poz;
}
}
void afis()
{

51
while(poz)
{
fout<<x[poz]<<" ";
poz=p[poz];
}
}
int main()
{
cit();
PD();
afis();
fout.close();
return 0;
}
4.3.5 PROBLEMA RUCSACULUI

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.

52
Avem ca date de intrare:
– n, numarul total de obiecte ;
– g, greutatea maxima a obiectelor din rucsac ;
– Xi, greutatea obiectului i ;
– Yi, profitul 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 :
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)

53
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
}
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)

54
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;
}

4.3.6 DETERMINAREA NUMARUL UI DE SECVEN ȚE PARE DE LUNGIME
MAXIMA ÎNTR-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.

55
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
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");

56
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 fisi erul 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
l[i]=l[i -1]+1; //in caz afirmativ, sec venta 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 variabila nrsol vom salva numarul de solutii

57
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 l or (în termeni de grafuri,
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 me morie
suplimentară.

59
BIBLIOGRAFIE

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

60
ANEXE
Anexa 1Rezolvarea 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
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

61

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;
}
}
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++)

62
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])
{
fout<<o[i]<<" ";
k=i;
}
}
int main()
{
cit();
greedy();
return 0;
}

63
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;
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

64
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()
{
cit();
cout<<dei(1,n);
return 0;
}