COLEGIUL NAŢIONAL “ŞTEFAN CEL MARE” TG. NEAMŢ

DIVIDE ET IMPERA

LUCRARE PENTRU ATESTAREA COMPETENŢELOR PROFESIONALE

Profesor coordinator, Elev: Ripeanu Constantin Radu Dragoș-Neculai Clasa: a XII-a RD

2014

MEMORIU DE PREZENTARE

La dispoziţia celor care rezolvă probleme cu ajutorul calculatorului există mai multe metode. Dintre acestea cele mai des utilizate sunt:

- metoda Backtracking;- metoda Greedy;- programare Dinamica;- metoda Branch and Bound;- metoda Divide et impera;

Metoda Backtracking

Această tehnică se foloseşte la rezolvarea problemelor a căror soluţie se poate reprezenta sub forma unui vector S = x1, x2,...xn cu x1 din S1, x2 din S2, …, xn din Sn, iar mulţimile S1, S2, …, Sn, care pot coincide, sunt mulţimi finite bine ordonate. Pentru fiecare problemă concretă sunt precizate relaţiile dintre componentele vectorului care memorează soluţia, numite condiţii interne. Mulţimea S = S1 x … x Sn se numeşte spaţiul soluţiilor iar elementele produsului cartezian care satisfac şi condiţiile interne se numesc soluţii rezultat. Metoda evită generarea tuturor combinaţiilor completând pe rând componentele vectorului soluţie cu valori ce îndeplinesc condiţiile de continuare, scurtându-se astfel timpul de calcul. Vectorul x este privit ca o stivă, lui xk nu i se atribuie o valoare decât după ce x1, …, xk-1 au primit valori. La început xk este iniţializat la o valoare (cu ajutorul unei funcţii init) al cărei succesor este primul element din Sk. Cu ajutorul unei funcţii succesor xk ia valoarea primului element din Sk. După ce xk a primit o valoare, nu se trece direct la atribuirea unei valori lui xk+1 ci se verifică mai întâi anumite condiţii de continuare referitoare la x1, …, xk cu ajutorul unei funcţii valid de tip boolean. Dacă aceste condiţii sunt satisfăcute se verifică dacă s-a obţinut o soluţie caz în care se trece la afişarea acesteia.Neîndeplinirea condiţiilor de continuare exprimă faptul că oricum am alege xk+1, …, xn, nu vom ajunge la o soluţie. În acest caz se face o nouă alegere pentru xk sau, dacă Sk a fost epuizat, se micşorează k cu o unitate şi se încearca o nouă alegere pentru xk din restul elementelor lui Sk încă nealese folosind funcţia succesor. Ca urmare se trece la atribuirea unei valori lui xk+1 doar dacă sunt îndeplinite condiţiile

1

de continuare. Algoritmul se termină în momentul în care au fost luate în calcul toate elementele mulţimii S1.

Metoda Greedy

Algoritmii greedy (greedy = lacom) sunt în general simpli şi sunt folosiţi la probleme de optimizare, cum ar fi: să se găsească cea mai bună ordine de executare a unor lucrări pe calculator, să se găsească cel mai scurt drum într-un graf etc. În cele mai multe situaţii de acest fel avem: • mulţime de elemente (lucrări de executat, vârfuri ale grafului etc) • o funcţie care verifică dacă o anumită mulţime de candidaţi constituie o soluţie posibilă, nu neapărat optimă, a problemei • o funcţie care verifică dacă pentru o mulţime de candidaţi este posibil să o completăm astfel încât să obţinem o soluţie posibilă, nu neapărat optimă, a problemei • o funcţie de selecţie care alege la orice moment cel mai potrivit element, încă nefolosit • o funcţie soluţie care spune când s-a ajuns la soluţie. Pentru a rezolva problema o anumită problemă, un algoritm greedy construieşte soluţia pas cu pas. Iniţial, mulţimea candidaţilor selectaţi este vidă. La fiecare pas, încercăm să adăugăm acestei mulţimi cel mai potrivit element, conform funcţiei de selecţie. Dacă, după o astfel de adăugare, mulţimea de elemente obţinută nu mai poate duce la soluţie, se elimină ultimul element adăugat; acesta nu va mai fi niciodată considerat. Dacă, după adăugare, mulţimea de elemente selectate poate duce la soluţie, ultimul element adăugat va rămâne de acum încolo în ea. De fiecare dată când lărgim mulţimea elementelor selectate, verificăm dacă această mulţime nu constituie o soluţie posibilă a problemei noastre. Dacă algoritmul Greedy funcţionează corect, prima soluţie găsită va fi totodată o soluţie optimă a problemei. O întrebare firească este aceea dacă algoritmul Greedy duce totdeauna la soluţie optimă? Evident că nu Sunt situaţii când soluţia găsită nu este optimă. Mai mult, pentru cele mai multe din probleme nu se cunosc algoritmi Greedy de rezolvare. Spre deosebire de Backtracking, algoritmul Greedy nu permite atunci când s-a oservat că nu se poate ajunge la soluţie pentru o anumită secvenţă de elemente, revenirea înapoi, pe nivelele anterioare.Pentru problemele care nu duc la soluţia optimă este necesar să se caute soluţii, chiar dacă nu optime, dar cât mai apropiate de acestea.

2

Programarea dinamic ă

Programarea dinamica face parte dintr-o categorie de metode matematice numite metode de scufundare.O problemã de programare dinamicã contine subprobleme comune (care nu sunt independente) din a cãror rezolvare si combinare se obtine solutia unei (sub)probleme mai mari.Deci rezolvarea unei (sub)probleme se poate face doar dupã solutionarea (sub)problemelor, care alcãtuiesc problema respectivã.Spunem cã programarea dinamica actioneaza de jos in sus,prelucrând si combinând subcazuri mici,obtinând astfel solutia pentru subcazuri tot mai mari.Totodatã programarea dinamicã evitã rezolvarea de mai multor ori a aceleiasi subprobleme(rezolvându-se doar problemele independente ),prin memorarea rezultatelor partiale.

Orice algoritm de programare dinamicã poate fi descris prin urmãtorii pasi:1) Caracterizarea structurii unei solutii optime:se defineste un vector, o matrice , ..., în care fiecare componentã va contine o solutie optimã a unei subprobleme.

2) Definirea recursivã a valorii unei solutii optime .Totodatã se definește valoarea celei mai mici subprobleme (celor mai mici subprobleme). (Ex: c[i][0] = 1; c[i][1] = 1;)3) Calcularea de jos în sus a valorii unei soluții optime , tinând seama de definirea recursivã a acestei valori.4) Dacã pe lângã valoare se mai dorește afișarea soluției care a generat rezultatul optim , atunci se construiește de sus în jos soluția propriu-zisã.

Metoda Branch and Bound

Metoda Branch and Bound foloseste la rezolvarea problemelor la care domeniul în care se caută soluţia este foarte mare şi nu se cunoaşte un alt algoritm care să conducă mai rapid la rezultat. Problemele care pot fi abordate prin această metodă pot fi modelate într-un mod asemănator celui folosit la metoda Backtracking. Se pleacă de la o configuraţie iniţială şi se reţine şirul de operaţii prin care aceasta este transformată într-o configuraţie finală dacă aceasta este dată, în alte cazuri se cere configuraţia finală ştiind că trebuie să verifice anumite condiţii de optim.

3

Diferenţa dintre cele două metode constă în faptul că metoda Backtracking la fiecare etapă selectează un singur succesor după care se face verificarea condiţiilor de continuare, iar metoda Bramch and Bound generează la fiecare pas toate configuraţiile posibile (toţi succesorii) care rezultă din cea curentă şi le stochează într-o listă. Se alege apoi un element din listă după un criteriu ce depinde de problemă şi se reia procesul de expandare.

Alegerea optimă a unui element din această listă pentru expandare se face cu ajutorul unei funcţii f = g + h în care g este o funcţie care măsoară lungimea drumului parcurs de la configuraţia iniţială până la nodul curent iar h este o funcţie (euristică) care estimează efortul necesar pană se ajunge la soluţie şi este specifică fiecărei probleme. Alegerea funcţiei h este foarte importantă din punct de vedere a vitezei de execuţie a programului.

Se lucrează cu două liste: lista open în care se reţin configuraţiile neexpandate încă şi lista close care le memorează pe cele expandate. Soluţia se construieşte folosind un arbore care se parcurge pe baza legăturii tată.

Metoda Divide et Impera

Metoda generală de programare cunoscută sub numele de “divide et impera” (“dezbină și stapâneşte”) constă în împărţirea repetată a unei probleme în subprobleme de acelaşi tip, dar de dimensiune mai mică, urmată de combinarea soluţiilor subproblemelor rezolvate pentru a obţine soluţia problemei iniţiale. Fiecare subproblemă se rezolvă direct dacă dimensiunea ei este suficient de mică, încât să poată fi rezolvată imediat cu un procedeu specific, altfel este împărţită din nou în subprobleme mai mici folosind acelaşi procedeu prin care a fost descompusă problema iniţială. Procedeul se reia până când, în urma descompunerilor repetate, se ajunge la probleme care admit rezolvare imediată. Algoritmul fiind de natură repetitivă şi deoarece subproblemele au aceiaşi formă cu cea a problemei iniţiale, metoda “Divide et impera” poate fi implementată elegant folosind o funcţie recursivă.

MEMORIU JUSTIFICATIV4

Se presupune că formularea divide et impera îi aparține regelui francez Ludovic al XI-lea (1461-1483). Unii istorici însă i-o atribuie și lui Iulius Cezar (100 î. Ch. – 44 î. Ch.). Ea ar trebui să însemne că adversarii trebuie împrăștiați și slăbiți prin lupte între ei, pentru a putea fi învinși și supuși.

Vom considera mai departe însă această formulare dintr-o perspectivă mult mai civilizată. Îndemnul trebuie să ne ajute la soluționarea unor problem prin împărțirea lor în subprobleme de dimensiune mai mica, rezolvarea lor și combinarea rezultatelor în scopul obținerii soluției pentru problema inițială. La rândul lor, subproblemele se pot împărți în problem asemănătoare de dimensiuni mai mici, care se rezolvă cu aceeași metodă. Această manevră se reia recursive, până când subproblemele obținute devin elementare și pot fi rezolvate direct.

Pașii rezolvării unei probleme folosind principiul Divide et Impera sunt:• Divide: împarte problema recursiv în subprobleme, până când au dimensiuni elementare • Impera: rezolvă subproblemele;

combină soluțiile subproblemelor pentru obținerea soluției problemei inițiale.

Forma generală a algoritmului:

ALGORITM_DivideEtImpera(P, n, S) If(n ≤ n0) Then directSolve(P, n, S) End_if Else Execute Divide(P, n) in (P1, n1), (P2, n2), …, (Pk, nk) DivideEtImpera(P1, n1, S1) DivideEtImpera(P2, n2, S2) ……………………………… DivideEtImpera(Pk, nk, Sk) Combină S1, S2, …, Sk pentru a obține S End_ElseEND_ALGORITM_DivideEtImpera(P, n, S)

5

IMPLEMENTARE C++

a) Maxim-ul dintr-un vector

Șirul dat se împarte în două subșiruri de lungimi aproximativ egale. Se determină minimul m1 din primul subșir, apoi minimul m2 din al doilea subșir, pentru ca în final să se determine minimul dintre m1 și m2. Pentru fiecare dintre șirurile rezultate se aplică același procedeu, atâta timp cât lungimea este cel puțin 2.

#include <iostream>using namespace std;

int div_MAX(int, int, int []);int div_MAX(int st, int dr, int v[]){

int mij, max1, max2;if(st == dr) return v[st];else{

mij = (st + dr) / 2;max1 = div_MAX(st, mij, v);max2 = div_MAX(mij+1, dr, v);if(max1 > max2) return max1;else return max2;

}}

int main(void){

int n, i;cout << "n = "; cin >> n;int *v = new int[n+1];for(i = 1; i <= n; ++i){

cout << "v[" << i << "] = ";cin >> v[i];

}cout << div_MAX(1, n, v) << endl;system("pause>null");return(EXIT_SUCCESS);

}

6

b) Căutare binară

Căutarea binară se realizează după modelul căutării în dicționar a unui cuvânt dat. Pagina pe care trebuie să figureze cuvântul se determină printr-un proces de micșorare a spațiului de căutare, în funcție de literele cuvântului și de ordonarea alfabetică a cuvintelor din dicționar. Se determină mijlocul (aproximativ) m al șirului. Se verifică dacă x = a[m]. Dacă da, se afișează poziția, iar dacă nu, se verifică de care parte față de a[m] ar putea fi x și se continuă căutarea în mod similar acolo. Ceea ce este caracteristic acestui algoritm este faptul că problema se descompune în trei probleme: una (simplă) de verificare a egalității lui a[m] cu x și alte două care verifică prezența lui x în șirurile aflate înainte de poziția m, respectiv după poziția m. Se rezolvă prima problemă și dacă a[m] ≠ x, se continuă cu rezolvarea uneia dintre cele două probleme similare de căutare (nu se rezolvă ambele probleme, cum cere de obicei metoda divide et impera). Căutarea se termină cu insucces (element absent) atunci când șirul în care trebuie să căutăm este vid (s > d). Inițial s = 1 iar d = n.

#include <iostream>using namespace std;

int div_CautBin(int, int, int []);int div_CautBin(int x, int st, int dr, int v[]){

int mij;if(st > dr) return -1;else{

mij = (st + dr) / 2;if(v[mij] == x) return mij;else if(v[mij] > x) return div_CautBin(x, st, (mij-1), v);else return div_CautBin(x, (mij+1), dr, v);

}}

int main(void){

int n, x, i;cout << "n = "; cin >> n;cout << "x = "; cin >> x;int *v = new int[n+1];for(i = 1; i <= n; ++i){

cout << "v[" << i << "] = ";cin >> v[i];

}cout << div_CautBin(x, 1, n, v) << endl;system("pause>null");return(EXIT_SUCCESS);

}

7

c) Turnurile din Hanoi

Se presupune că unul dintre cele mai populare jocuri din toate timpurile, turnurile din Hanoi, a fost inventat în 1883 de către francezul Eduoard Lucas. Acesta este unul dintre exemplele standard pentru metoda Divide et Impera în literatura de specialitate.

Se dau 3 tije simbolizate prin a,b,c. Pe tija a se gãsesc discuri de diametre diferite, asezate în ordine descrescãtoare a diametrelor privite de jos în sus. Se cere sã se mute de pe tija a pe b, utilizând ca tija intermediarã tija c, respectând urmãtoarele reguli:

la fiecare pas se mutã un singur disc ; nu este permis sã se aseze un disc cu diametrul mai mare peste un disc cu

diametrul mai mic.

Rezolvare:

Dacã n=1 se face mutarea ab, adicã se mutã discul de pe tija a pe tija b.

Dacã n=2 se fac mutãrile ac,ab,cb.

În cazul în care n>2 problema se complicã. Notãm cu H(n,a,b,c) sirul mutãrilor celor n discuri de pe tija a pe tija b , utilizând ca tijã intermediarã, tija c.

Conform strategiei Divide et impera încercãm sã descompunem problema în alte douã subprobleme de acelasi tip, urmând apoi combinarea solutiilor. În acest sens, observãm cã mutarea celor n discuri de pe tija a pe tija b,utilizând ca tijã intermediarã tija c, este echivalentã cu:

muatrea a n-1 discuri de pe tija a pe tija c , utilizând ca tijã intermediarã tija b; mutarea discului rãmas pe tija b; mutarea a n-1 discuri de pe tija c pe tija b , utilizând ca tijã intermediarã tija a.

Parcurgerea celor trei etape permite definirea recursivã a sirului H(n,a,b,c) astfel:

H(n,a,b,c) = { a,b dacã n=1

H(n-1,a,c,b),ab,H(n-1,c,b,a), dacã n>1

8

Exemple:

Pentru n=2 avem:

H(2,a,b,c)=H(1,a,c,b),ab,H(1,c,b,a)=ac,ab,cb.

Pentru n=3 avem :

H(3,a,b,c)=H(2,a,c,b),ab,H(2,c,b,a)=H(1,a,b,c),ac,H(1,b,c,a),ab,H(1,c,a,b),cb,H(1,a,b,c)=ab,ac,bc,ab,ca,cb,ab.- .

#include <iostream>using namespace std;

int hanoi(int, char, char, char);int hanoi(int n, char a, char b, char c){

static int count(0);if(n == 1) cout << "(" << a << "," << c << ")" << endl;else{

hanoi(n-1, a, b, c);cout << "(" << a << "," << c << ")" << endl;hanoi(n-1, b, c, a);++count;

}return (count);

}

int main(void){

int n;cout << "n = "; cin >> n;cout << "Mutari: " << hanoi(n, 'A', 'B', 'C');system("pause>null");return(EXIT_SUCCESS);

}

9

d) Sortare rapidă ( QuickSort )

QuickSort este un algoritm de sortate, ce a fost prezentat pentru prima dată de către C.A.R. Hoare (n. 1934) în 1962. QuickSort este în medie foarte rapid atunci când trebuie sortate mulțimi mari de date. Algoritmul alege un element aleator, din secvența de sortat, care reprezintă pivotul (punct de deviație). Apoi, secvența de date se împarte în două zone: una în care elementele sunt mai mici sau egale cu pivotul și una în care elementele sunt mai mari (în cadrul zonelor respective, elementele nu sunt sortate). Apoi, fiecare zonă se împarte recursiv în două zone, pe baza unui pivot corespunzător, până când se ajunge la zone cu un element (problemă elementară). QuickSort este, în medie, cel mai rapid algoritm de sortare.

În implementarea noastră, alegem ca pivot primul element din secvența a[inf], a[inf+1], …, a[sup] și folosim variabilele contor i și j, cu care ne deplasăm spre dreapta, respectiv spre stânga în secvența dată. După împarțirea datelor în două zone (prima pivotul), vom plasa elementul pivot între ele și vom apela recursiv metoda QuickSort() pentru fiecare zonă. Condiția de terminare este ca dimensiunea secvenței să fie 1 (inf = sup).

#include <iostream>using namespace std;

void QuickSort(int [], int, int);void QuickSort(int v[], int inf, int sup){

int i = inf,j = sup,mij = v[(inf + sup) / 2],aux;

while(i <= j){

while(v[i] < mij) i++;while(v[j] > mij) j--;if(i <= j){

aux = v[j];v[j] = v[i];v[i] = aux;i++, j--;

}}if(inf < j) QuickSort(v, inf, j);if(sup > i) QuickSort(v, i, sup);

}

int main(void){

int n, i;cout << "n = "; cin >> n;

10

int *v = new int [n+1];for(i = 1; i <= n; ++i){

cout << "v[" << i << "] = ";cin >> v[i];

}QuickSort(v, 1, n);for(i = 1; i <= n; ++i) cout << v[i] << " ";system("pause>null");return(EXIT_SUCCESS);

}

e) Sortare prin interclasare ( MergeSort )

MergeSort este, ca și QuickSort, o metodă eficientă de sortare. Ea procedează astfel: vectorul dat se împarte în două părți, care vor fi ordonate recursiv și apoi interclasate, pentru a obține vectorul inițial sortat. Complexitatea procesului de interclasare este liniară, pentru că ambele secvențe sunt deja sortate. Complexitatea algoritmului este O(n log n), iar, în practică, timpul de execuție este în medie mai mare decât cel obținut cu metoda QuickSort.

#include <iostream>using namespace std;

int a[30], b[30];void interclasare(int, int, int);void interclasare(int s, int m, int d){

int i, j, k;if(a[m] > a[m+1]){

i = s; j = m + 1; k = i - 1;while ((i <= m) && (j <= d)){

++k;if(a[i] <= a[j]){

b[k] = a[i];++i;

}else{

b[k] = a[j];++j;

}}while(i <= m) b[++k] = a[i++];while(j <= d) b[++k] = a[j++];for(k = s; k <= d; ++k) a[k] = b[k];

}}

void sort(int, int);void sort(int s, int d)

11

{int m;if(d > (s+1)){

m = (s + d) / 2;if(s < m) sort(s, m);if((m+1) < d) sort(m+1, d);interclasare(s, m, d);

}else if(s < d)

if(a[s] > a[d] && a[s] != a[d])a[s] ^= a[d] ^= a[s] ^= a[d];

}

int main(void){

int n, i;cout << "n = "; cin >> n;for(i = 1; i <= n; ++i){

cout << "a[" << i << "] = ";cin >> a[i];

}sort(1, n);for(i = 1; i <= n; ++i) cout << a[i] << " ";system("pause>null");return(EXIT_SUCCESS);

}

f) Cel mai mare divizor comun a N numere

Se dau n numere naturale. Se cere să se calculeze cel mai mare divizor comun al acestora utiliând metoda divide et impera.

Programul de mai jos utilizează o funcție cmmdc care calculează cmmdc a două numere naturale cu ajutorul căreia implementăm stategia metodei divide et impera.

#include <iostream>using namespace std;int cmmdc(int a, int b){

int r;while(b){

r = a % b; a = b; b = r;}return (a);

}

int Divide_et_Impera(int v[], int st, int dr){

if(st == dr) return v[st];

else

12

{int mij = (st + dr) / 2;int d1 = Divide_et_Impera(v, st, mij);int d2 = Divide_et_Impera(v, (mij+1), dr);return cmmdc(d1, d2);

}}

int main(void){

int n, i, *v;cout << "n = "; cin >> n;v = new int[n+1];for(i = 1; i <= n; ++i){

cout << "v[" << i << "] = ";cin >> v[i];

}cout << "CMMDC = " << Divide_et_Impera(v, 1, n);system("pause>null");return 0;

}

g) Căutarea unei valori date într-un vector neordonat

Se dă un vector neordonat vect[100] şi o valoare n, introduse de la tastatură. Elaboraţi un program care să caute şi să afişeze dacă valoarea introdusă se află în vectorul dat.

#include <cstdio>#include <conio.h>

void cautare(int,int,int,int[],int&);typedef int vect[100];vect x;

int main(void){ int n,i,j,a,k,poz[100]; printf("n="); if(scanf("%d",&n)!=1) printf("Eroare date!"); else { for(i=1;i<=n;i++) {

printf("x(%d)=",i);if(scanf("%d",&x[i])!=1){

printf("Eroare date!");goto xx;

} } printf("Vectorul x:"); for(i=1;i<=n;i++) printf("%d ", x[i]); printf("\n"); printf("Valoarea cautata:"); if(scanf("%d",&a)!=1) printf("Eroare date!");

13

else {

k=0;cautare(1,n,a,poz,k);if(k>0){

printf("Elementul a fost gasit pe pozitiile ");for(i = 1; i <= k; i++)

printf("%d ", poz[i]);}else printf("Element negasit!");

} }

xx:getch();return 0;

}

void cautare(int i, int j, int a,int poz[], int &k){ int p = 0, q; if(i == j) {

if(a==x[i]){

k++;poz[k]=i;

} } else {

cautare(i,(i+j)/2,a,poz,k);if(p <= (i+j)/2){

for(q=p;q<=(i+j)/2;q++){

if(a==x[q]){

k++;poz[k]=q;k--;

}}cautare((i+j)/2+1,j,a,poz,k);for(p=(i+j)/2+1;p<=j;p++){

if(a==x[p]){

k++;poz[k--] = p;

}}

} }}

14

BIBLIOGRAFIE

1. Bogdan Pătruţ – Aplicaţii în C / C++; Editura Teora, Bucureşti 1998;

2. Borland C++. Version 4.5 – Programmers Guide, Borland International, 1995;

3. Tudor Sorin – Bazele programării în C++ -manual pentru clasa a IX-a; Editura L&S InfoMat, Bucureşti, 1998;

4. Mihai Mocanu, Gheorghe Marian, Costin Bădică, Carmen Bădică 333 probleme de programare; Editura Teora, Bucureşti, 1993;

5. Mihai Mocanu, Gheorghe Marian, Costin Bădică, Carmen Bădică, 333

probleme de programare, Editura Teora, Bucureşti, 1993;

15

CUPRINS

1. Memoriu de prezentare.................................................................... 1

2. Memoriu justificativ........................................................................ 5

3. Implementare C++........................................................................... 6

4. Bibliografie..................................................................................... 15

16