Divide et impera

Divide et impera rezolvă o problemă împărțind-o în subprobleme mai mici de același tip, rezolvându-le și combinând rezultatele. Pentru maximul din $[4,9,2,7]$, împărțim în $[4,9]$ și $[2,7]$, aflăm maximele 9 și 7, apoi alegem 9. Trebuie definit cazul de oprire, de pildă un segment cu un singur element.

Divide et impera rezolvă o problemă în trei etape: împarte problema în subprobleme de același tip și mai mici, rezolvă fiecare subproblemă (de obicei recursiv, folosind aceeași metodă) și combină rezultatele parțiale pentru a obține rezultatul problemei inițiale. Recursivitatea se oprește la un caz de bază, de pildă un segment cu un singur element, la care răspunsul se cunoaște direct. Subproblemele sunt independente și nu trebuie să aibă aceeași mărime. Metoda este corectă dacă împărțirea reduce mărimea problemei la fiecare apel, iar combinarea păstrează corectitudinea. Dacă o problemă de mărime $n$ se împarte în două subprobleme de mărime $n/2$ și etapele de împărțire și combinare costă $O(1)$, numărul de apeluri este $2n-1$, deci timpul este $O(n)$; dacă combinarea costă $O(n)$, ca la sortarea prin interclasare, timpul este $O(n\log n)$.

Exemplul 1 — maximul unui tablou. Maximul unui segment este maximul dintre maximele celor două jumătăți ale lui.

#include <iostream>
using namespace std;
int maxim(int v[], int st, int dr) {
    if (st == dr) return v[st];
    int m = (st + dr) / 2;
    int a = maxim(v, st, m), b = maxim(v, m + 1, dr);
    return a > b ? a : b;
}
int main() {
    int v[] = {4, 9, 2, 7};
    cout << maxim(v, 0, 3);
    return 0;
}

Pentru $4,9,2,7$ segmentul se împarte în $[4,9]$ și $[2,7]$. Maximele lor sunt 9 și 7, iar combinarea alege 9. Programul afișează 9. Se fac 7 apeluri: unul pentru întregul tablou, două pentru jumătăți și patru pentru elementele singure. Pentru un tablou cu 8 elemente sunt 15 apeluri; în general $2n-1$, deci aceeași muncă ca la o singură parcurgere.

Exemplul 2 — puterea. Puterea $a^n$ se poate calcula prin divide et impera: $a^n=(a^{n/2}{)}^2$ pentru $n$ par și $a^n=a\cdot (a^{n/2}{)}^2$ pentru $n$ impar, cu $a^0=1$. Aici problema se reduce la o singură subproblemă de mărime $n/2$, iar combinarea înseamnă una sau două înmulțiri.

long long putere(long long a, int n) {
    if (n == 0) return 1;
    long long h = putere(a, n / 2);
    h = h * h;
    if (n % 2 == 1) h = h * a;
    return h;
}

Pentru $2^{10}$ apelurile sunt pentru exponenții 10, 5, 2, 1 și 0, iar rezultatul este 1024, cu 6 înmulțiri în loc de 9. Numărul de pași este proporțional cu ${\log }_{2}n$.

Schema generală. Problema este definită pe o secvență, de obicei între pozițiile st și dr ale unui vector. Funcția verifică întâi dacă secvența e destul de mică pentru a fi rezolvată direct. Dacă nu, o împarte la mijloc, m = (st + dr) / 2, se autoapelează pe st..m și pe m+1..dr și combină cele două rezultate.

subprogram DI(st, dr)
┌dacă secvența st..dr este suficient de mică atunci
│  returnează rezultatul calculat direct
│altfel
│  m ← [(st + dr) / 2]
│  r1 ← DI(st, m)
│  r2 ← DI(m + 1, dr)
│  returnează combinarea lui r1 cu r2
└■

Condițiile ca metoda să se potrivească. Subproblemele sunt de același tip cu problema inițială, ca să le rezolvi cu aceeași funcție. Ele sunt independente: nu au părți comune, deci nimic nu se calculează de două ori. Rezultatele se pot combina ușor: maximul a două numere, suma, interclasarea a doi vectori sortați. Există un caz simplu, rezolvat fără autoapel; fără el, recursivitatea nu se oprește.

De ce e eficientă. La sortarea prin interclasare, vectorul se înjumătățește de aproximativ ${\log }_{2}n$ ori până ajunge la secvențe de un element, iar la fiecare nivel interclasările fac în total cel mult $n$ mutări. De aici ordinul $n{\log }_{2}n$, mult mai mic decât $n^2$, ordinul metodei bulelor: pentru un milion de valori, aproximativ 20 de milioane de operații față de un milion de milioane. La căutarea binară se continuă într-o singură jumătate, de aceea ajung aproximativ ${\log }_{2}n$ pași.

Când nu se potrivește. Dacă subproblemele se suprapun, metoda recalculează aceleași rezultate. Funcția recursivă pentru $F(n)=F(n-1)+F(n-2)$, din șirul lui Fibonacci, calculează $F(n-2)$ o dată direct și încă o dată în interiorul lui $F(n-1)$, iar numărul de apeluri crește exponențial. Aici se folosește un calcul iterativ sau programarea dinamică. Construirea figurilor autosimilare prin divide et impera (fractalii) este o lecție separată, iar interclasarea, folosită la sortare, are lecția ei.

Exemple suplimentare

Exemplul 3 — căutarea binară și sortarea. Căutarea binară este divide et impera cu o singură subproblemă: după compararea cu elementul din mijloc se continuă într-o singură jumătate, iar combinarea lipsește. Sortarea prin interclasare și sortarea rapidă împart tabloul în două segmente, sortează fiecare segment recursiv, iar în primul caz combinarea este interclasarea. Pentru fiecare problemă se identifică cele trei etape și cazul de bază.

Pentru a urmări un apel recursiv de acest tip, desenează arborele apelurilor: rădăcina este problema întreagă, iar frunzele sunt cazurile de bază. Numărul de frunze este numărul de elemente când fiecare segment se împarte în două, iar numărul total de apeluri este $2n-1$ dacă se continuă până la segmente de un element. Când subiectul cere numărul de apeluri, include apelul inițial.

Exemplul 4 — numărul de apeluri. Câte apeluri ale funcției maxim se execută pentru maxim(v, 0, 7), unde v are 8 elemente și funcția este cea din primul exemplu?

• a) 7
• b) 8
• c) 15
• d) 16

Răspunsul corect este c). Segmentul de 8 elemente se împarte în două segmente de câte 4, apoi fiecare în două de câte 2, apoi fiecare în două de câte un element. Apelurile pe niveluri sunt $1$, $2$, $4$ și $8$, în total $1+2+4+8=15=2\cdot 8-1$. Varianta b) numără doar frunzele, iar varianta a) numără doar apelurile care împart segmentul, nu și cele din cazul de bază.

Exemple rezolvate

Exemplul 1: maximul unui vector. Află maximul vectorului 4, 9, 2, 7, 5, 1, 8 prin divide et impera.

1. Secvența 1..7 se împarte în 1..4 (4, 9, 2, 7) și 5..7 (5, 1, 8).
2. Maximul primei jumătăți este 9, al celei de-a doua este 8.
3. Combinarea: maximul dintre 9 și 8 este 9.

#include <iostream>
using namespace std;

int v[] = {0, 4, 9, 2, 7, 5, 1, 8};   // pozitiile 1..7

int maxim(int st, int dr) {
    if (st == dr)
        return v[st];                  // cazul simplu: un element
    int m = (st + dr) / 2;
    int a = maxim(st, m);
    int b = maxim(m + 1, dr);
    if (a > b)
        return a;
    return b;
}

int main() {
    cout << maxim(1, 7) << "\n";
    return 0;
}

Programul afișează:

9

Exemplul 2: căutarea binară, recursiv. În vectorul sortat 4, 9, 13, 20, 26, 31, 45, 52, 60, 77 caută valoarea 45 și afișează poziția ei (numerotarea începe de la 1), sau 0 dacă nu există.

1. Mijlocul secvenței 1..10 este poziția 5, cu valoarea $26<45$, deci cauți în 6..10.
2. Mijlocul secvenței 6..10 este poziția 8, cu valoarea $52>45$, deci cauți în 6..7.
3. Mijlocul secvenței 6..7 este poziția 6, cu valoarea $31<45$, deci cauți în 7..7.
4. Mijlocul secvenței 7..7 este poziția 7, cu valoarea 45: ai găsit-o.

#include <iostream>
using namespace std;

int v[] = {0, 4, 9, 13, 20, 26, 31, 45, 52, 60, 77};

int caut(int x, int st, int dr) {
    if (st > dr)
        return 0;                      // secventa vida: x nu exista
    int m = (st + dr) / 2;
    if (v[m] == x)
        return m;
    if (x < v[m])
        return caut(x, st, m - 1);
    return caut(x, m + 1, dr);
}

int main() {
    cout << caut(45, 1, 10) << " " << caut(46, 1, 10) << "\n";
    return 0;
}

Programul afișează poziția lui 45 și 0 pentru valoarea 46, care lipsește:

7 0

Varianta iterativă, cazurile limită și numărul de pași sunt în lecția despre căutarea binară.

Exemplul 3: sortarea prin interclasare. Sortează crescător vectorul 6, 1, 8, 3, 9, 2, 7, 5.

1. Se sortează separat jumătățile 6, 1, 8, 3 și 9, 2, 7, 5, fiecare prin același procedeu, până la secvențe de un element.
2. Rezultatele sunt 1, 3, 6, 8 și 2, 5, 7, 9.
3. Interclasarea lor compară de fiecare dată primele elemente rămase și îl copiază pe cel mai mic: 1, 2, 3, 5, 6, 7, 8, 9.

#include <iostream>
using namespace std;

int v[] = {6, 1, 8, 3, 9, 2, 7, 5}, aux[8];

void sorteaza(int st, int dr) {
    if (st >= dr)
        return;                        // cel mult un element: e deja sortat
    int m = (st + dr) / 2;
    sorteaza(st, m);
    sorteaza(m + 1, dr);
    int i = st, j = m + 1, k = st;     // interclasarea celor doua jumatati
    while (i <= m && j <= dr)
        if (v[i] <= v[j]) aux[k++] = v[i++];
        else aux[k++] = v[j++];
    while (i <= m) aux[k++] = v[i++];
    while (j <= dr) aux[k++] = v[j++];
    for (k = st; k <= dr; k++)
        v[k] = aux[k];
}

int main() {
    sorteaza(0, 7);
    for (int k = 0; k < 8; k++)
        cout << v[k] << " ";
    cout << "\n";
    return 0;
}

Programul afișează:

1 2 3 5 6 7 8 9

Condiția v[i] <= v[j] ia întâi elementul din stânga când valorile sunt egale, de aceea sortarea prin interclasare este stabilă. Cealaltă sortare bazată pe divide et impera este quicksort.

Exemplul 4: turnurile din Hanoi. Pe tija A sunt $n$ discuri, de la cel mai mare (jos) la cel mai mic (sus). Trebuie mutate pe tija C, câte un disc o dată, fără să pui vreodată un disc mai mare peste unul mai mic, folosind tija B ca ajutor.

1. Descompunerea: muți cele $n-1$ discuri de sus pe B (folosind C), muți discul cel mare pe C, apoi muți cele $n-1$ discuri de pe B pe C (folosind A).
2. Cazul simplu: un singur disc se mută direct.
3. Numărul de mutări: $M(1)=1$ și $M(n)=2\cdot M(n-1)+1$, deci $M(n)=2^n-1$. Pentru 3 discuri, 7 mutări.

#include <iostream>
using namespace std;

void hanoi(int n, char a, char b, char c) {   // muta n discuri de pe a pe c, prin b
    if (n == 1) {
        cout << a << "->" << c << " ";
        return;
    }
    hanoi(n - 1, a, c, b);
    cout << a << "->" << c << " ";
    hanoi(n - 1, b, a, c);
}

int main() {
    hanoi(3, 'A', 'B', 'C');
    cout << "\n";
    return 0;
}

Programul afișează cele 7 mutări:

A->C A->B C->B A->C B->A B->C A->C

Exemplul 5: nivel de examen, numărul de apeluri. Funcția de mai jos numără elementele pare din secvența v[st..dr]. Câte apeluri ale funcției se fac, în total, la apelul pare(1, 8), și ce valoare se returnează pentru vectorul 4, 9, 2, 7, 5, 1, 8, 6?

#include <iostream>
using namespace std;

int v[] = {0, 4, 9, 2, 7, 5, 1, 8, 6}, apeluri = 0;

int pare(int st, int dr) {
    apeluri++;
    if (st == dr)
        return v[st] % 2 == 0;
    int m = (st + dr) / 2;
    return pare(st, m) + pare(m + 1, dr);
}

int main() {
    int r = pare(1, 8);
    cout << r << " " << apeluri << "\n";
    return 0;
}

1. Fiecare apel pe o secvență cu cel puțin două elemente face exact două autoapeluri, iar secvențele de un element nu mai fac niciunul.
2. Se ajunge la cele 8 secvențe de un element (8 apeluri); deasupra lor sunt 4 apeluri pe secvențe de câte două elemente, 2 pe secvențe de câte patru și apelul inițial: $8+4+2+1=15$. În general, pentru $n$ elemente se fac $2n-1$ apeluri.
3. Elementele pare sunt 4, 2, 8 și 6, deci funcția returnează 4.

Programul afișează:

4 15

Unde apare la examen

La Bacalaureatul la informatică, matematică-informatică, programa de examen nu numește metoda divide et impera; numește însă recursivitatea (subprograme recursive), căutarea binară și interclasarea (anexa 2 la OMECTS 4800/2010). Itemii cu o funcție recursivă care se autoapelează pe două jumătăți ale unei secvențe, ca în exemplul 5, se rezolvă cu raționamentul din această lecție.

Pe programa școlară veche, „Metoda de programare Divide et Impera” este la clasa a XI-a, cu exemple de aplicații ca sortarea rapidă, sortarea prin interclasare și căutarea binară (OMECI 5099/2009). Pe programa nouă, aplicată la clasa a X-a din 2027–2028, metoda trece în clasa a X-a, alături de metoda greedy (OMEC 4370/2026).

Greșeli frecvente

• Greșit: subproblemele trebuie să aibă exact aceeași mărime.
  Corect: ele trebuie să fie mai mici decât problema inițială, nu neapărat egale între ele.
• Greșit: divide et impera nu are nevoie de caz de oprire.
  Corect: fără un caz de bază recursivitatea nu se oprește.
• Greșit: după rezolvarea subproblemelor, rezultatul final este gata.
  Corect: de obicei trebuie combinate rezultatele parțiale.
• Greșit: subproblemele trebuie să fie mereu egale ca lungime.
  Corect: subproblemele nu trebuie să fie egale; la împărțirea în jumătăți, lungimile diferă cu cel mult un element.
• Greșit: cazul cu un element se împarte din nou.
  Corect: este cazul de bază; fără if (st == dr) (sau st >= dr), funcția se autoapelează la nesfârșit și programul se oprește cu eroare când se umple stiva.
• Greșit: simpla folosire a recursiei face algoritmul mai rapid.
  Corect: complexitatea se analizează pentru pașii reali; dacă cele două autoapeluri lucrează pe părți comune, metoda pierde eficiența (vezi șirul lui Fibonacci).
• Greșit: jumătățile pot fi st..m-1 și m..dr.
  Corect: cu m = (st + dr) / 2, jumătățile corecte sunt st..m și m+1..dr; varianta greșită poate ajunge, pentru două elemente, la un autoapel pe aceeași secvență.
• Greșit: după ce cele două jumătăți sunt sortate, vectorul e sortat.
  Corect: cele două jumătăți sortate nu formează singure un vector sortat; abia interclasarea le unește.
• Greșit: căutarea binară merge și pe un vector nesortat.
  Corect: metoda aruncă o jumătate presupunând că vectorul e ordonat; pe un vector nesortat poate rata valoarea căutată.

Înainte și după

Întrebări frecvente