Divide et ImperaDe Cacior Mihai

Divide et impera provine din latina, inseamna divide si cucereste.Divide et impera se bazează pe principiul descompunerii problemei în două sau mai multe subprobleme, care se rezolvă, iar soluția pentru problema inițială se obține combinând soluțiile subproblemelor.

#include<iostream>using namespace std;int v[20];int suma(int a,int z){int m,d1,d2; if(a!=z) {m=(a+z)/2; d1=suma(a,m); d2=suma(m+1,z); return d1+d2;//pentru suma return d1*d2;//pentru produs } else return v[a];}

int main(){ int n; cout<<"n="; cin>>n; for(int i=1;i<=n;i++) { cout<<"v["<<i<<"]="; cin>>v[i]; } cout<<"suma este "<<suma(1,n);}

Suma/Produlus elementelor unui vector

Metoda presupune descompunerea vectorului v in subvectori si acestia sunt impartiti la randul lor pana cand fiecare vector are un element.

Elementele vectorilor sunt adunati sau inmultiti pe rand doi cate doi pana rezulta solutia finala.

#include<iostream>using namespace std;int v[20];int maxmin(int a, int z){ int x,y,m; m=(a+z)/2; if (a<z) //pentru maxim if(a>z) //pentru minim { x = maxmin(a,m); y = maxmin(m+1,z); if (x<y) return y; else return x; } else return v[a];}int main(){ int n; cout<<"n="; cin>>n; for(int i=1;i<=n;i++) { cout<<"v["<<i<<"]="; cin>>v[i]; } cout<<"max/min este "<<maxmin(1,n);}

Elementul maxim sau minim dintr-un vector

#include <iostream>using namespace std;int cmmdc(int a,int b){ int r; r=a%b; while(r!=0) { a=b; b=r; r=a%b; } return b;}int cmmmc(int a, int b){ return(a*b/cmmdc(a,b));}int main(){ int x,y; cout<<"x="; cin>>x; cout<<"y="; cin>>y; cout<<"C.m.m.d.c este "<<cmmdc(x,y)<<endl; cout<<"C.m.m.m.c este "<<cmmmc(x,y)<<endl;}

Cmmdc si cmmmc-ul a doua numere.

#include<iostream>using namespace std;char a,b,c;int n;int hanoi(int n,char a,char b, char c){ if(n==1) cout<<a<<b<<" "; else { hanoi(n-1,a,c,b); cout<<a<<b<<" "; hanoi(n-1,c,b,a); }}int main(){ cout<<"n=";cin>>n; hanoi(n,'a','b','c');}

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.

Rezolvare:• Daca n=1 se face mutarea a-b.• Daca n=2 se fac mutarile a-c,a-b,c-b.• Daca n>2 descompunem programul in

subprograme in care n<2 si rezolvam.

#include<iostream>using namespace std;int n,x,v[10],m;int caut(int s,int d){ if(s>d) return -99; else { m=(s+d)/2; if(x==v[m]) return m; if(x<v[m]) return caut(s,m-1); else return caut(m+1,d); }}int main(){ cout<<"n= ";cin>>n; cout<<"x= ";cin>>x; cout<<"dati "<<n<<" elemente (in ordine crescatoare)"<<endl; for(int i=1;i<=n;i++) cin>>v[i]; cout<<"elementul "<<x<<" a fost gasit pe pozitia: "<<caut(1,n); return 0;}

Cautarea binara intr-un vector

Se cauta un element dat intr-un vector cu elemente crescatoare. Cu metoda divide et impera vectorul este inpartit, elementul cautat este comparat cu mijlocul vectorului daca este mai mare se cauta in jumatarea vectorului de dupa mijloc, iar daca este mai mic se cauta in jumatatea dinaintea mijlocului.

Dac elementul nu este gasit se afiseaza -99.

#include<iostream>using namespace std;int a[100],n;int interclasare(int i,int m,int j){ int b[100]; 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];}int dei(int i,int j){ if (i<j) { int m=(i+j)/2; dei(i,m); dei(m+1,j); interclasare(i,m,j); }

int main(){ int i; cout<<"n="; cin>>n; for(int i=1;i<=n;i++) { cout<<"a["<<i<<"]="; cin>>a[i]; } dei(1,n); for(i=1;i<=n;i++) cout<<a[i]<<' '; return 0;}

Sortarea prin interclasare, Mergesort

Vectorul se desparte cu metoda divide et impera pana cand fiecare vector are un singur element. Acesti vectori sunt ordonati si compun solutia.

Metoda QuicksortSortare Rapida

Quicksort efectueaza sortarea bazandu-se pe o strategie divide et impera. Astfel, el imparte lista de sortat indoua subliste mai usor de sortat.Pasii algoritmului sunt:• Se alege un element al listei numit pivot• Se reordoneaza lista astfel incat toate

elementale mai mici dacat pivotul sa fie plasate inaintea pivotului si toate elementale mai mari sa fie dupa pivot.

• Se sorteaza recursiz sublista de elemente mai mici decat pivotul si sublista de elemente mai mari decat pivotul.