29 aprilie - Divide et Impera (temă 2 mai)

Suma elementelor unui tablou de nr intregi

#include<iostream>
using namespace std;
int x[100],n;

int DI(int st, int dr)
{int m,s1,s2;
if(st==dr)
    return x[st];
m=(st+dr)/2;
s1=DI(st,m);
s2=DI(m+1,dr);
return s1+s2;
}

int main()
{int i;
cin>>n;
for(i=0;i<n;i++)
    cin>>x[i];
cout<<DI(0,n-1);
return 0;
}

Elementul minim dintr-un tablou de numere întregi

#include<iostream>
using namespace std;
int x[100],n;
int DI(int st, int dr)
{int m,s1,s2;
if(st==dr)
    return x[st];
m=(st+dr)/2;
s1=DI(st,m);
s2=DI(m+1,dr);
if(s1<s2)return s1;
else return s2;   
}

int main()
{int i;
cin>>n;
for(i=0;i<n;i++)
    cin>>x[i];
cout<<DI(0,n-1);
return 0;
}

Cmmdc dintr-un tablou

#include<iostream>
using namespace std;
int x[100],n;
int cmmdc(int a, int b)
{
while(a!=b)
{    if(a>b)a=a-b;
    else b=b-a;
}
return a;
}

int DI(int st, int dr)
{int m,s1,s2;
if(st==dr)
    return x[st];
m=(st+dr)/2;
s1=DI(st,m);
s2=DI(m+1,dr);
return cmmdc(s1,s2);
}

int main()
{int i;
cin>>n;
for(i=0;i<n;i++)
    cin>>x[i];
cout<<DI(0,n-1);
}

Suma cifrelor tuturor elementelor din sir

#include<iostream>
using namespace std;
int x[100],n;

int suma(int a)
{int s=0;
while(a)
{    s=s+a%10;
a=a/10;}
return s;
}

int DI(int st, int dr)
{int m,s1,s2;
if(st==dr)
    return suma(x[st]);
m=(st+dr)/2;
s1=DI(st,m);
s2=DI(m+1,dr);
return s1+s2;
}

int main()
{int i;
cin>>n;
for(i=0;i<n;i++)
    cin>>x[i];
cout<<DI(0,n-1);
}

Numarul de elemente impare

#include<iostream>
using namespace std;
int x[100],n;

int DI(int st, int dr)
{int m,s1,s2;
if(st==dr)
    if(x[st]%2==1)
        return 1;
    else return 0;
m=(st+dr)/2;
s1=DI(st,m);
s2=DI(m+1,dr);
return s1+s2;
}

int main()
{int i;
cin>>n;
for(i=0;i<n;i++)
    cin>>x[i];
cout<<DI(0,n-1);
}

Numarul de elemente prime

#include<iostream>
using namespace std;
int x[100],n;

int prim(int a)
{int d,ok=1;
if(a==1)return 0;
for(d=2;d<=a/2;d++)
    if(a%d==0)
        ok=0;
return ok;
}

int DI(int st, int dr)
{int m,s1,s2;
if(st==dr) return prim(x[st]);
m=(st+dr)/2;
s1=DI(st,m);
s2=DI(m+1,dr);
return s1+s2;
}

int main()
{int i;
cin>>n;
for(i=0;i<n;i++)
    cin>>x[i];
cout<<DI(0,n-1);
}