Question

Se consideră un șir cu n elemente, numere naturale. Folosind metoda Divide et Impera, determinați suma elementelor acestui șir.

Answer 1

Ideea ar fi să ai o funcție recursivă care primește ca parametrii un sir și un interval, și returnează suma elementelor din acel interval.

Îți scriu mai jos un program în C++. Baftă!


# include <iostream>

using namespace std;

int suma( int v[], int b, int e ) {
    if ( e - b == 0 )
        return v[b];
    else
        return suma( v, b, ( b + e ) / 2 ) + suma( v, ( b + e ) / 2 + 1, e );
}

int main() {
    int n, i;

    cin >> n;
    int v[n];

    for ( i = 0; i < n; i ++ )
        cin >> v[i];

    cout << suma( v, 0, n - 1 );

    return 0;
}