Divide et Impera

Divide et Impera is a programming method based on a simple principle:

• the given problem is decomposed into two (or more) subproblems (of the same type as the initial problem, but of smaller size);
• each subproblem is solved independently;
• the results obtained for the subproblems are combined, obtaining the result of the initial problem.

The subproblems must be of the same type as the initial problem and will be solved using the same technique.

The subproblems into which the given problem is decomposed must be:

• of the same type as the given problem;
• of smaller size (easier);
• independent (they do not overlap, processing distinct data sets).

In the Divide et Impera technique, after successive divisions into subproblems, the situation arises where the current problem can no longer be divided into subproblems. Such a problem is called an elementary problem and is solved in another way – usually very simply.

Divide et Impera typically admits a recursive implementation – solving the problem consists of solving subproblems of the same type. A pseudocode algorithm that describes the method is:

Algorithm DivImp(P)
        If P is an elementary problem 
            R <- SolveDirectly(P)
        Else
            [P1, P2] <- Decompose(P)
            R1 <- DivImp(P1)
            R2 <- DivImp(P2)
            R <- Combine(R1, R2)
        EndIf
    EndAlgorithm

Example: GCD of elements in an array

Given an array V with n non-zero natural elements, indexed from 1 to n. Determine their greatest common divisor.

As in the previous problem, we transform it into one with sequences. We will determine the greatest common divisor of the elements in a sequence delimited by indices st and dr:

#include 
    using namespace std;
    
    int gcd(int v[100], int s, int d)
    { 
        if (s == d) return v[s];
        else
        { 
            int x, y;
            x = gcd(v, s, (s + d) / 2);
            y = gcd(v, (s + d) / 2 + 1, d);
    
            while (x != y)
                if (x > y) x = x - y;
                else y = y - x;
    
            return x;
        }
    }
    
    int main()
    {
        int v[100], n, i;
        cin >> n;
        for (i = 1; i <= n; i++)
            cin >> v[i];
        cout << gcd(v, 1, n);
        return 0;
    }