1. Se citeste
un numar real x. Sa se calculeze radical de ordinul 3 din x folosind un
algoritm de tip Divide et impera.
#include<iostream>
using namespace
std;
double
r3(double x, double s, double d)
{
if(d-s<=0.0001) return d;
else
{ double m=(s+d)/2;
if(m*m*m<x) return r3(x,m,d);
else return r3(x,s,m);
}
}
int main()
{ double x;
cin>>x;
if(x>0) if(x<1) cout<<r3(x,0,1);
else
cout<<r3(x,0,x);
else if(x>-1) cout<<r3(x,-1,0);
else cout<<r3(x,x,0);
system("pause");
return 0;
}
2. Se citeste un vector cu n elemente numere naturale. Sa se
determine elementul minim din vector folosind Divide et impera.
#include<iostream>
using namespace
std;
int min(int
a[100],int s , int d)
{
if ( s == d ) return a[s];
else
{
int m = (s+d)/2;
int m1 = min(a,s,m);
int m2 = min(a,m+1,d);
if ( m1 < m2 ) return m1;
else return m2;
}
}
int main()
{
int a[100];
int n ;
cin>> n;
for (int i = 0 ; i < n ;i++)
cin>>a[i];
cout << min(a,1,n);
system("pause");
return 0;
}
3. Se citeste un vector cu n elemente numere naturale. Sa se
calculeze CMMDC al elementelor vectorului folosind Divide et impera.
#include<iostream>
using namespace
std;
int cmmdc(int
a[100], int s, int d)
{ if(s==d)
return a[s];
else
{ int x,y;
x=cmmdc(a,s,(s+d)/2);
y=cmmdc(a,(s+d)/2+1,d);
while(x!=y)
if(x>y) x=x-y;
else y=y-x;
return x;
}
}
int main()
{
int a[100],n,i;
cin>>n;
for(i=1;i<=n;i++) cin>>a[i];
cout<<cmmdc(a,1,n);
system("pause");
return 0;
}
4. Sa se calculeze folosind metoda divide et impera suma
elementelor unui vector.
#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);
}
5.Utilizand
metoda divide et impera, sa se sorteze prin interclasare un sir
#include<iostream.h>
int
a[20],n; void mergesort(int i,int m,int
j){int b[20],x=i,k=1,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);
mergesort(i,m,j);}
} void main()
{
cout<<"n=";
cin>>n;
for(int
i=1;i<=n;i++)
{cout<<"a["<<i<<"]=";
cin>>a[i];
}
divimp(1,n);
cout<<"vectorul
sortat este: "<<endl;
for(i=1;i<=n;i++)
cout<<a[i]<<' ';
}
6.Cautare
binara
Se citeste un
vector cu n componente numere intregi, unde nemerele se presupun ordonate
crescator si o valoare intreaga (nr). Sa se decida daca nr se gaseste sau nu
printre numerele citite, iar in caz afirmativ sa se tipareasca indicele
componentei care contine acea valoare .
O rezolvare in care nr se compara pe rand cu
cele n valori, este lipsita de valoare (nu exploateaza faptul ca cele n valori
sunt in secventa crescatoare). Algoritmul care va fi propus este mult mai
performant si face parte, asa cum am invatat, dintre algoritmii clasici.
Problema este de a decide daca valoarea
cautata se gaseste printre numerele de indice cuprins intre i si j (intial i=1,
j=n ). Pentru aceasta vom proceda astfel:daca nr coincide cu vloarea de indice
(i+j)/2 ( valoarea de la mijloc ) , se tipaeste indicele si se revine din apel
(problema a fost rezolvata).
Contrar, daca i<j (nu s-a cautat peste tot)
problema se descompune astfel:
daca numaul este mai mic decat valoarea
testata (din mijloc), inseamna ca avem sanse sa-l gasim intre componentele cu
indicele intre i si (i+j)/2-1 , caz in care reapelam functia cu acesti
parametri
daca numarul este mai mare decat valoarea
testata (din mijloc), inseamna ca avem sanse sa-l gasim intre componentele cu
indicele intre (i + j)/2+1 si j , caz in care reapelam functia cu acesti
parametri.
Problema nu se descompune in altele care se
rezolva, dupa care nu se compara solutia, ci se reduce la o subproblema. In
linii mari , acest rationament este de tip Divide et impera.
#include<iostream.h>
int v[100],n,nr;
void caut(int i, int j)
{ if (nr==v[(i+j)/2])
cout<<"gasit"<<'
'<<"indice"<<(i+j)/2;
else
if (i<j)
if (nr<v[(i+j)/2])
caut (i , (i+j)/2-1;
else caut ((i+j)/2+1,j);
};
main ( )
{ cout<<"n=";cin>>n;
for (int i=1;i<=n;i++)
{ cout<<"v["<<i<<"]=";cin>>v[i];}
cout<<"nr=";cin>>nr;
caut (1,n);
}
7. Maximul dintr-un vector
Se citeste un vector cu n componente, numere
naturale. Se cere sa se tipareasca valoare maxima.
Trebuie tiparita valoarea maxima dintre
numerele retinute in vector de la i la j(initial i= 1, j=n). Pentru aceasta
procedam astfel :daca i=j, valoare maxima va fi v[i] ;
contrar vom imparti vectorul in doi vectori
(primul vector va contine componentele de la i la (i+j) div 2, al doilea va
contine componentele de la ((i+j) div 2 +1 la j ) , rezolvam subproblemele
(aflam maximul pentru fiecare din ele) iar solutia problemei va fi data de
valoarea maxima dintre rezultatele celor doua subprobleme.
#include<iostream.h>
int v[10],n;
int max(int i ,int j)
{ int a,b;
if (i==j) return v[i] ;
else
{ a=max(i, (i+j)/2);
b=max((i+j)/2+1,j);
if (a>b) return a;
else return b;
}
}
main( )
{ cout<<"n=";cin>>n;
for (int i=1;i<=n;i++)
{cout<<"v["<<i<<"]=";cin>>v[i];
}
cout<<"max="<<max(1,n);
}]
