Proiect Divide et ImperaJugaurs Andrei, Negulescu Catalin,Burdea David si Gruita Lorena

Prelucrarea vectorilor cu metoda „Divide et Impera”: a. Determinarea sumei şi produsului elementelor vectorului #include<iostream.h> int v[20],n; int suma(int li,int ls) {int m, d1 ,d2; if(li!=ls) {m=(li+ls)/2; d1=suma(li,m); d2=suma(m+1,ls); return d1+d2; } else return v[li]; } void main() { cout<<"n="; cin>>n; for(int i=1;i<=n;i++) {cout<<"v["<<i<<"]=“; cin>>v[i];} cout<<"suma celor "<<n<<" elemente ale vectorului "<<suma(1,n); }

b. Determinarea elementului maxim / minim c. Determinarea cmmdc şi cmmmc al elementelor vectorului #include<iostream> using namespace std; int v[20], i, n, z, k; void deicitire (int s, int d) { int m; if(s==d) cin>>v[s]; else {m=(s+d)/2; deicitire(s, m); deicitire(m+1, d); }} void deimax(int s, int d, int &z) { int m, x1, x2; if(s==d) z=v[s]; else { m=(s+d)/2; deimax(s, m, x1); deimax(m+1, d, x2); if(x1>x2)z=x1; else z=x2; } } void deimin(int s, int d, int &k) { int m, x1, x2; if(s==d) k=v[s]; else { m=(s+d)/2; deimin(s, m, x1); deimin(m+1, d, x2); if(x1<x2) k=x1; else k=x2; } } int main() { cin>>n; deicitire(1, n); for(i=1; i<=n;i++) cout<<v[i]<<” “; deimax(1,n,z); deimin(1,n,k); cout<<endl<<”max=”<<z; cout<<endl<<”min=”<<k; return 0; }

2. Problema turnurilor din Hanoi Turnurile din Hanoi 2. Problema turnurilor din Hanoi Turnurile din Hanoi Se dau 3 tije

simbolizate prin a,b,c. Pe tija a se gasesc n discuri de diametre diferite, asezate in ordine descrescatoare a diametrelor. Se cere sa se mute de pe tija a pe b, utilizand ca tija intermediara tija c, toate cele n discuri, respectand urmatoarele reguli: -la fiecare pas se muta un singur disc ; -nu este permis sa se aseze un disc cu diametrul mai mare peste un disc cu diametrul mai mic. Rezolvare: Daca n=1 se face mutarea ab, adica se muta discul de pe tija a pe tija b. Daca n=2 se fac mutarile ac,ab,cb. Daca n>2 . Notam cu H(n,a,b,c) sirul mutarilor celor n discuri de pe tija a pe tija b , utilizand ca tija intermediara, tija c. Conform strategiei Divide et impera incercam sa descompunem problema in alte doua subprobleme de acelasi tip, urmand apoi combinarea solutiilor. Deci:mutarea celor n discuri de pe tija a pe tija b,utilizand ca tija intermediara tija c, este echivalenta cu: muatrea a n-1 discuri de pe tija a pe tija c , utilizand ca tija intermediara tija b; mutarea discului ramas de pe tija a pe tija b; mutarea a n-1 discuri de pe tija c pe tija b , utilizand ca tija intermediara tija a.

#include<iostream> char a,b,c ; int n; void h(int n,char a,char b, char c) { if(n==1) cout<<a<<b<<" "; else { h(n-1,a,c,b); cout<<a<<b<<" "; h(n-1,c,b,a); } } void main() { cout<<"n=“; cin>>n; h(n,'a','b','c'); }

3. Căutarea binară a unui element într-un vector

Cautarea binara se bazeaza pe tehnica de programare Divide et Impera. Elementul cautat este “verificat”cu mijlocul vectorului. Daca elementul este egal cu mijlocul,cautarea se termina. Insa daca nu sunt egale, se compara valoarea mijlocului cu cea a elementului de cautat. Daca elementul este mai mare se continua cautarea de la mijlocul listei pana la sfarsit, iar daca este mai mic se continua cautarea de la inceput pana la mijloc.

#include <iostream>   int main() {     int mij,n=7,i,x=10,v[7]={4,5,8,10,20,45,76},st,dr,g=0;     st=0;     dr=n-1;     mij=(st+dr)/2;     while  ( (st<dr) && (!g) )     {          if (v[mij]==x) {g=1;break;}          else if (v[mij]<x) st=mij+1;          else if (v[mij]>x) dr=mij-1;     }     if (g) cout<<x<<" se afla in vector pe pozitia "<<mij;     else cout<<x<<" nu se afla in vector";       return 0; }

4. Problema tăieturilor Se da o bucata dreptungiulara de tabla avand lungimea L si inaltimea h. Pe suprafata ei se

gasesc n gauri, de coordonate intregi, stiute, cu diametre neglijabile. Sa se decupeze o bucata de tabla de arie maxima, fara gauri, facand numai taieturi paralele cu laturile placii ( verticale sau orizontale ).

Coordonatele gaurilor sunt retinute in doi vectori vx[i] pentru abscisele gaurilor si vy[i] pentru ordonate ( acesti vectori nu sunt neaparat sortati, gaurile putand fi memorate in ordine cronologica, de exemplu ). Dreptunghiul initial si apoi dreptunghiurile care apar in procesul de taiere sunt memorate prin coordonatele coltului din stanga jos ( x, y ), prin lungime L si prin inaltime h ( fiecare dreptunghi se identifica printr-un set de 4 variabile : x, y, L, h, cu ajutorul carora se formeaza coordonatele celor 4 colturi ).

Pentru fiecare dreptunghi, incepand cu cel initial, cautam daca exista gaura ( existenta gaurii este semnalizata de variabila logica gasit ). Conditiile pentru ca o gaura sa se gaseasca intr-un dreptunghi dat de coordonate ( x, y, L, h ) sunt :

a)                      vx[i] > x b)                     vx[i] < x+L c)                     vy[i] > y d)                     vy[i] < y+h In situatia cand avem o gaura, vom face prin ea doua taieturi, una orizontala si alta verticala, ceea

ce face ca dreptunghiul curent sa se divida in alte patru, deci problema admite o descompunere in alte patru de acelasi tip ( conform strategiei " DIVIDE ET IMPERA " ). Aria maxima se memoreaza prin coordonatele dreptunghiului de arie maxima ( xM, yM, LM, hM ). Daca nu avem gaura in dreptunghiul curent, acesta ar putea fi solutia problemei, deci aria acestuia se compara cu aria maxima retinuta pana la momentul respectiv si daca este cazul, se va retine ca arie maxima.

In acest caz, daca facem o taietura orizontala prin gaura de coordonate ( vx[i] , vy[i] ), vom obtine doua dreptunghiuri si anume :

a)                      x, y, L, vy[i]-y  , dreptunghiul A+B b)                     x, vy[i], L, y+h-vy[i] , dreptunghiul C+D ,iar dupa o taietura verticala, dreptunghiurile

: c)                      x, y, vx[i]-x, h   , dreptunghiul A+C d)                     vx[i], y , x+L-vx[i], h    , dreptunghiul B+D

# include < iostream > int  L, h, i, n, xM, yM, LM, hM, vy[30] , vx[30] ; void taiere ( int x, int y, int L, int h, int & xM, int & yM, int & LM,                                                       int & hM ,int vx[30]   ,int vy[30] )   //**    /* am apelat functia taiere ptr. dreptunghiurile A,B,C,          respectiv D, asa cum apar ele in desenul de mai sus */        else   if ( L * h > LM * hM )           /*  daca nu avem gaura,                                       dreptunghiul curent poate fi cel                    cautat si trebuie vazut daca are arie maxima.                     Daca da, coordonatele sale sunt atribuite solutiei                    curente   */               }     /*      ** functia are urmatorii parametri : a)      x,y coordonatele coltului din stanga jos al dreptunghiului b)      L,h lungimea, respectiv inaltimea dreptunghiului c)       Parametrii variabili  xM, yM, LM, hM, prin care se identifica dreptunghiul de arie maxima d)      vx si vy, cei doi vectori care memoreaza coordonatele gaurilor  */ void main ( )    cout << " L= " ; cin >> L ;   // citim dimensiunile tablei cout << " h= " ; cin >> h ; taiere ( 0, 0, L, h, xM, yM, LM, hM, vx, vy ) ;   /* apelul functiei                                                           care rezolva problema */ cout << " dreptunghiul de arie maxima are coordonatele : "   <<endl ; cout << " x = " << xM << ',' << " y = " << yM << endl ; cout << " L = " << LM << ',' << " h = " << hM << endl ; cout << " de arie A = " << LM * hM << endl ;

5. Sortarea prin interclasare – algoritmul MergeSort Aceasta metoda de ordonare are la baza interclasarea a doi vectori: fiind

dati doi vectori ordonati se obtine un al treilea vector ordonat care va contine elementele din cei doi vectori.

  In cazul sortarii prin interclasare vectorii care se interclaseaza sunt doua

secvente ordonate din acelasi vector   Sortarea prin interclasare utilizeaza metoda Divide et Impera:   -se imparte vectorul in secvente din ce in ce mai mici., astfel incat fiecare

secventa sa fie ordonata la un moment dat si interclasata cu o alta secventa din vector corespunzatoare.

-practic interclasarea va incepe cand se ajunge la o secventa formata din doua elemente. Aceasta odata ordonata se va interclasa cu o alta corespunzatoare. Cele doua secvente vor alcatui in subsir ordonat din vector mai mare care la randul lui se va interclasa cu subsirul corespunzator samd.

 

Fie vectorul: 8 7 9 3 6 4 17 16 Se imparte in doua secvente: 8 7 9 3 6 4 17 16 In continuare pt prima secvente se procedeaza la fel: 8 7 9 3 Dupa o noua impartire se obtine: 8 7 Se incepe interclasarea. Se considera ca avem doi vectori de lungime 1 care se

interclaseaza: 8 7 Rezulta: 7 8

int a[1000],n;   void interclas(int i,int m,int j) {int b[1000]; int x=i; int k=1; int y=m+1; while(x<=m && y<=j)      if (a[x]<a[y])            b[k++]=a[x++];      else            b[k++]=a[y++];    while (x<=m)         b[k++]=a[x++];  while (y<=j)         b[k++]=a[y++];    int t=i;  for (k=1;k<=(j-i)+1;k++)         a[t++]=b[k]; }   void divimp(int i,int j) {if (i<j)     {int m=(i+j)/2;      divimp(i,m);      divimp(m+1,j);      interclas(i,m,j);} }     void main() {clrscr(); cout<<"n="; cin>>n; for(int i=1;i<=n;i++)         {cout<<"a["<<i<<"]=";          cin>>a[i];         } divimp(1,n); for(i=1;i<=n;i++)    cout<<a[i]<<' '; getch(); }

6. Sortarea rapidă - algoritmul QuickSort Quicksort efectuează sortarea bazându-se pe o strategie

divide et impera. Astfel, el împarte lista de sortat în două subliste mai ușor de sortat. Pașii algoritmului sunt:

Se alege un element al listei, denumit pivot Se reordonează lista astfel încât toate elementele mai mici

decât pivotul să fie plasate înaintea pivotului și toate elementele mai mari să fie după pivot. După această partiționare, pivotul se află în poziția sa finală.

Se sortează recursiv sublista de elemente mai mici decât pivotul și sublista de elemente mai mari decât pivotul.

O listă de dimensiune 0 sau 1 este considerată sortată.

void QUICKSORT(int inf,int sup) { int x,i,j,t; i=inf ; j=sup; x=A[(i+j)/2]; do{ while ((i<sup)&&(A[i]<x)) i++; while ((j>inf)&&(A[j]>x)) j--; if (i<=j) { t=A[i]; A[i]=A[j]; A[j]=t; i++; j--; } } while (i<=j); if (inf<j) QUICKSORT(inf,j); if (i<sup) QUICKSORT(i,sup); }

7. Desenarea fractalilor: Curba lui Koch pentru un segment, triunghi, pătrat Curba lui Koch este o figură geometrică ce se construieşte

aplicând în mod repetat un acelaşi procedeu de desenare. Iniţial se porneşte cu un segment de dreaptă şi pe segmentul respectiv se ridică un triunghi echilateral

Figura 1:Curba lui Koch după o iteraţie.

Pe urmă se repetă procedeul pentru fiecare din cele patru segmente de dreaptă: se ridică un triughi echilateral pe fiecare segment. Rezultatul se poate vedea în figura 2.

Apoi se repetă acelaşi procedeu, pentru fiecare segment din figura obţinută. Rezultatul este redat în figura 3.

După repetarea de 7 ori a procedeului se obţine o figură de genul celei redate în figura 4.

Proiect realizat de Jugaurs Andrei, Negulescu Catalin,Burdea David si

Gruita Lorena