Ideea Divide et Impera — împarte, rezolvă, combină

Cei trei pași: împarte, rezolvă, combină

Divide et Impera („împarte și stăpânește”) este o metodă de rezolvare care construiește răspunsul în trei pași, mereu aceiași:

1. ÎMPARTE — rupi problema în două (sau mai multe) subprobleme mai mici de același tip. Nu probleme diferite — aceeași problemă, doar pe o porțiune mai mică din date.
2. REZOLVĂ — rezolvi fiecare subproblemă recursiv, cu exact aceeași metodă. Pentru că au aceeași formă, se aplică din nou cei trei pași. Coborârea se oprește la cazul de bază: o instanță atât de mică (de obicei un singur element) încât răspunsul e direct, fără alt apel.
3. COMBINĂ — lipești răspunsurile subproblemelor într-un răspuns pentru problema mare.

De ce funcționează? Pentru că fiecare subproblemă e o versiune mai mică a aceleiași probleme. Dacă știi să rezolvi problema în general, știi automat să rezolvi și subproblema — e doar aceeași sarcină, cu mai puține date. Iar cum la fiecare pas datele se micșorează, ajungi garantat la cazul de bază, unde recursia se oprește.

Fiecare dintre cei trei pași are propria lui lecție în acest capitol (împărțirea problemei, rezolvarea subproblemelor, combinarea rezultatelor). Aici prinzi doar imaginea de ansamblu. Recursivitatea este motorul întregii metode — dacă nu o ai solidă, recapituleaz-o întâi din capitolul de recursivitate.

Exemplu pas cu pas: maximul din [3, 7, 2, 9]

Vrem cel mai mare element dintr-un șir. Cu Divide et Impera gândim așa:

• ÎMPARTE șirul la mijloc în două jumătăți: [3, 7] și [2, 9].
• REZOLVĂ maximul fiecărei jumătăți (recursiv, prin aceeași înjumătățire): max([3, 7]) = 7 și max([2, 9]) = 9.
• COMBINĂ: maximul întregului șir e cel mai mare dintre cele două rezultate: max(7, 9) = 9.

Desfășurat, jumătatea [3, 7] se rupe mai departe în [3] și [7] — fiecare cu un singur element, deci cazuri de bază: răspunsul e chiar elementul. Apoi rezultatele urcă înapoi și se combină: max(3, 7) = 7, max(2, 9) = 9, iar la final max(7, 9) = 9.

Implementare C++

Maximul prin Divide et Impera. Funcția primește capetele intervalului st și dr și se apelează pe jumătăți.

#include <iostream>
using namespace std;

int maximDI(int v[], int st, int dr) {
    if (st == dr) return v[st];          // caz de baza: un singur element
    int mid = st + (dr - st) / 2;        // mijloc fara overflow
    int maxStanga = maximDI(v, st, mid); // REZOLVA jumatatea stanga
    int maxDreapta = maximDI(v, mid + 1, dr); // REZOLVA jumatatea dreapta
    // COMBINA: cel mai mare dintre cele doua
    return maxStanga > maxDreapta ? maxStanga : maxDreapta;
}

int main() {
    int v[] = {3, 7, 2, 9};
    int n = 4;
    cout << maximDI(v, 0, n - 1) << "\n"; // 9
    return 0;
}

Observă cele trei părți în cod: împărțirea (mid), rezolvarea (cele două apeluri recursive) și combinarea (alegerea celui mai mare). Cazul de bază (st == dr) oprește coborârea.

Complexitate

Pentru maxim, fiecare element e atins exact o dată în drumul recursiei, deci munca totală e liniară.

Aici Divide et Impera nu bate o simplă buclă for (tot O(n)) — exemplul e ales ca să vezi clar tiparul. Forța metodei apare când combinarea e isteață: la căutarea binară pe șir sortat arunci o jumătate întreagă la fiecare pas și ajungi la O(log n), iar la sortările prin interclasare la O(n log n). Aceste cazuri clasice le studiezi separat.

Vizualizare

Urmărește cum se rupe șirul în jumătăți până la elemente singulare, apoi cum urcă înapoi rezultatele și se combină.

Recapitulare

• Divide et Impera rezolvă o problemă în trei pași: ÎMPARTE în subprobleme mai mici de același tip, REZOLVĂ-le recursiv, COMBINĂ rezultatele.
• Funcționează pentru că subproblemele sunt versiuni mai mici ale aceleiași probleme, deci se opresc sigur la cazul de bază; împarte mereu cu mid = st + (dr - st) / 2.
• Recursivitatea e motorul metodei; puterea reală apare când combinarea e isteață (căutare binară O(log n), interclasare O(n log n)) — cazuri studiate separat.