Divide and conquer

A.K.A.

Divide et impera

Ce este “Divide and Conquer”?

• Divide and conquer ( Divide et impera ) este un important algoritm , in stiinta calculatorului, bazat pe recursie multi-ramificata.

• Cu ajutorul acestuia, problema este sectionata in doua sau mai multe subprobleme de acelasi tip (sau similare) pana cand problema devine destul de simpla pentru a putea fi rezolvata direct.

• In final, solutiile subproblemelor se combina pentru a da un rezultat problemei originale.

• Pe de alta parte, abilitatea de intelegere, cat si cea de implementare a unui algoritm de tipul Divide and conquer este una care cere timp pentru a putea fi perfectionata.

Aplicatii• #include<iostream>• int n,v[20],i,z,k;• using namespace std;• void divide(int s,int d,int &m)• {• m=(s+d)/2;• }• void combinas(int x1,int

x2,int &k)• {• k=x1+x2;• }• void deis(int s,int d,int &k)• {• int m,x1,x2;• if(s==d)• k=v[s];• else

{divide(s,d,m);deis(s,m,x1);deis(m+1,d,x2);combinas(x1,x2,k);}}int main(){cin>>n;for(i=1;i<=n;i++)cin>>v[i];deis(1,n,k);cout<<"\nsuma elementelor="<<k;return 0;}

Suma elementelor unui vector

Aplicatii• #include<iostream>• int n,v[20],i,z,k;• using namespace std;• void divide(int s,int d,int &m)• {• m=(s+d)/2;• }• void combinas(int x1,int

x2,int &k)• {• k=x1+x2;• }• void deis(int s,int d,int &k)• {• int m,x1,x2;• if(s==d)• k=v[s];• else

{divide(s,d,m);deis(s,m,x1);deis(m+1,d,x2);combinas(x1,x2,k);}}int main(){cin>>n;for(i=1;i<=n;i++)cin>>v[i];deis(1,n,k);cout<<"\nprodusul elementelor="<<k;return 0;}

k=x1*x2;

Determinarea elementului minim• #include<iostream>• int n,v[20],i,z,k;• using namespace std;• void divide(int s,int d,int &m)• {• m=(s+d)/2;• }• void combinamin(int x1,int x2,int &z)• {• if(x1<x2)• z=x1;• else• z=x2;• }• void deimin(int s,int d,int &z)• {• int x1,x2;• int m;

if(s==d)z=v[s];else{divide(s,d,m);deimin(s,m,x1);deimin(m+1,d,x2);combinamin(x1,x2,z);}}int main(){cin>>n;for(i=1;i<=n;i++)cin>>v[i];deimin(1,n,z);cout<<"minimul="<<z;}

Determinarea elementului maxim• #include<iostream>• int n,v[20],i,z,k;• using namespace std;• void divide(int s,int d,int &m)• {• m=(s+d)/2;• }• void combinamax(int x1,int x2,int &z)• {• if(x1<x2)• z=x2;• else• z=x1;• }

void deimax(int s,int d,int &z){int x1,x2;int m;if(s==d)z=v[s];else{divide(s,d,m);deimax(s,m,x1);deimax(m+1,d,x2);combinamax(x1,x2,z);}}int main(){cin>>n;for(i=1;i<=n;i++)cin>>v[i];deimax(1,n,z);cout<<"maximul="<<z;}

CMMDC• #include<iostream.h>• int cmmdc(int a[20], int li, int ls)• { if(li==ls) return a[li];• else• { int x,y;• x=cmmdc(a,li,(li+ls)/2);• y=cmmdc(a,(li+ls)/2+1,ls);• while(x!=y)• if(x>y) x=x-y;• else y=y-x;• return x; • } • }• void main()• {• int a[20],n,i;• cout<<"n=";cin>>n;• for(i=1;i<=n;i++) cin>>a[i];• cout<<"cmmdc este: "<<cmmdc(a,1,n);• }

Turnurile din Hanoi• #include<iostream>

• using namespace std;

• long double nr;

• int hanoi(int n, int a,int b, int c)• {if ( n )• {hanoi(n-1,a,c,b);• cout<<a<<"->"<<b<<endl;• nr++;• hanoi(n-1,c,b,a);}• }

• int main ()• {int n;• cout<<"n= ";cin>>n;• //n este numarul de piese;• hanoi(n,1,2,3);• cout<<"numarul total de mutari a fost "<<nr;• }

MergeSort• #include <iostream>• using namespace std;• int v[1000],n;• int citire()• {int i;• cin>>n;• for(i=1;i<=n;i++)• cin>>v[i];• }• int afis()• {int i;• for(i=1;i<=n;i++)• cout<<v[i]<<" ";• cin>>i;• }• int ordo(int p,int u)• {int aux;• if(v[p]>v[u])• {aux=v[p];• v[p]=v[u];• v[u]=aux;• }• }• int interclas(int p,int u,int m)• {int i,j,a[1000],k=0;• i=p;• j=m+1;

for(i=1;i<=k;i++) v[p+i-1]=a[i];}int divide(int p,int u){int m;if(u-p<=1) ordo(p,u);else {m=(p+u)/2; divide(p,m); divide(m+1,u); interclas(p,u,m); }}int main (){citire(); divide(1,n); afis();}

while(i<=m && j<=u) if(v[i]<v[j]) {k++; a[k]=v[i]; i++; } else {k++; a[k]=v[j]; j++; }if(i<=m) for(j=i;j<=m;j++) {k++; a[k]=v[j]; }else for(i=j;i<=u;i++) {k++; a[k]=v[i]; }

QuickSort• #include <iostream>• using namespace std;

• int v[100],n,k;• int poz(int li,int ls,int &k,int v[100])• { int i=li,j=ls,c,i1=0,j1=-1;• while(i<j)• { if(v[i]>v[j])• { c=v[j]; v[j]=v[i]; v[i]=c;• c=i1; i1=-j1; j1=c;• }• i=i+i1; j=j+j1;• }• k=i;• }• int quick(int li,int ls)• { if(li<ls)• { poz(li,ls,k,v);• quick(li,k-1);• quick(k+1,ls);• }• }• int main()• { int i;• cin>>n;• for(i=1;i<=n;i++)• cin>>v[i];• quick(1,n);• for(i=1;i<=n;i++)• cout<<v[i]<<" ";• }

Problema taieturilor• #include<iostream>• using namespace std;

• struct punct {• int x,y;• };

• int X, Y;• punct v[20];• int n;• int S;• int xs, ys, xd, yd,i;

• void taiere(int x1, int y1, int x2, int y2) {• //x1,y1; x2,y2 - coordonatele coltului stanga-jos,dreapta-sus;• int g=0, poz;• for(int i=1; i<=n && !g; i++)• //ma opresc cand dau peste o perforatie in interiorul suprafetei • if(v[i].x>x1 && v[i].x<x2 && v[i].y>y1 && v[i].y<y2) {• g=1;• poz=i;• }• if (g==1) {• taiere(x1, v[poz].y, x2, y2); // deasupra• taiere(x1, y1, x2, v[poz].y); // dedesubt• taiere(x1, y1, v[poz].x, y2); // stanga• taiere(v[poz].x, y1, x2, y2); // dreapta• }• else if ((x2-x1)*(y2-y1)>S) {• xs=x1;• ys=y1;• xd=x2;• yd=y2;• S=(x2-x1)*(y2-y1);• }• }

•

OUCH!int main() { cout<<"Numarul de gauri= "; cin>>n; for(i=1; i<=n; i++) { cout<<endl; cin>>v[i].x;cin>>v[i].y; } cin>>X>>Y; taiere(0, 0, X, Y); cout<<endl<<"Cea mai mare suprafata neperforata are coordonatele ("<<xs<<","<<ys<<");("<<xd<<","<<yd<<")"<<endl; cout<<"Are suprafata "<<S;

}

AU!

Un proiect realizat de:

Predescu Robert

Vecerdea Andrei

Ebinca Cristian

Diaconescu Mircea

If(bo$$)Allow();

Else Reject();Allow();Reject();