Divide et Impera

Metoda „Divide et Impera” este un procedeu recursiv în care o problemă este descompusă în subprobleme de același tip, rezolvate astfel mai ușor. Rezultatele obținute se combină pentru a forma răspunsul final.

Cu alte cuvinte, prin această metodă rezolvăm probleme mai mici și mai simple. Rezultatele subproblemelor se unesc și formează forma finală.

Subproblemele Divide et Impera trebuie:

să fie de același tip cu problema principală (cea care se descompune);
să fie mai ușoare, mai simple de rezolvat;
să nu se intercaleze cu celelalte subprobleme.

Divide et Impera nu are formă fixă; este important de înțeles procedeul de dividere a problemei inițiale. Însă, pentru o problemă ce implică un tablou unidimensional (vector) ne ghidăm după următorii pași:

Împărțim vectorul în două jumătăți;
Apelăm recursiv funcția pentru ambele părți;
Condiția de oprire apare la cea mai mică subproblemă posibilă.

Exemplu

Să se afișeze numărul de elemente cu proprietatea P din vector. P este un subprogram care returnează 1 pentru valorile bune.

int P(int n){
    // ...
}
int Numarare(int c1, int c2){
    if (c1 == c2) return P(v[c1]);
    int m = (c1 + c2) / 2;
    return Numarare(c1, m) + Numarare(m + 1, c2);
}

Cum analizăm algoritmul rezolvat cu Divide et Impera?

funcția primește doi parametri, reprezentând indecșii din vector la care ne aflăm (capetele);
condiția de oprire, if (c1 == c2), va opri apelurile recursive atunci când am ajuns la cea mai mică subproblemă posibilă (un singur element din vector). Atunci, returnăm rezultatul funcției de proprietate;
dacă între capete sunt mai multe elemente, aflăm indexul mijlocului în variabila int m;
dividerea se face returnând suma rezultatelor funcțiilor de la stânga și dreapta mijlocului.

Proprietatea P poate verifica orice, de la număr palindrom, sau prim, până la verificări pe cifre (suma cifrelor pară etc).

Căutarea binară recursivă

Găsim elemente de „Divide et Impera” inclusiv în algoritmul căutării binare.

int CautareB(int x, int c1, int c2){
    if (c1 > c2) return 0;
    int m = (c1 + c2) / 2;
    if (x == V[m]) return m;
    else if (x < V[m]) return CautareB(x, c1, m - 1);
    else return CautareB(x, m + 1, c2);
}

În acest algoritm, căutăm un element într-un șir ordonat. Condiția de oprire este chiar găsirea elementului în mijlocul dintre capete.
Dacă nu găsim elementul, îl căutăm în jumătatea corespunzătoare, în funcție de relația de ordine a elementului căutat cu elementul din mijloc (dacă este mai mic, căutăm în stânga, altfel în dreapta).