Se consideră un șir cu n elemente, numere naturale. Folosind metoda Divide et Impera, determinați suma elementelor acestui șir.
Date de intrare
Programul citește de la tastatură numărul n, iar apoi cele n elemente ale șirului.
Date de ieșire
Programul va afișa pe ecran numărul S, reprezentând suma cerută.
Restricții și precizări
1 ≤ n ≤ 1000
elementele șirului vor fi mai mici decât 1.000.000
se recomandă folosirea metodei Divide et Impera
Exemplu
Intrare
6
4 1 8 4 3 5
Ieșire
25
SOLUTIE
using namespace std;
int sum(int v[],int st,int dr)
{
if(st==dr)
{
return v[st];
}
else
{
int m=(st+dr)/2;
int s1=sum(v,st,m);
int s2=sum(v,m+1,dr);
return s1+s2;
}
}
int main()
{
int v[1005],st=0,dr,n;
cin>>n;
dr=n-1;
for(int i=st;i<=dr;i++) { cin>>v[i];
}
cout<<sum(v,st,dr);
return 0;
}