Metoda Divide et Impera C++ — Ghid Complet

Ce este Divide et Impera?

Divide et impera este o paradigmă algoritmică ce rezolvă o problemă prin:

1. •Divide — împarte problema în subprobleme mai mici
2. •Impera (Cucerire) — rezolvă recursiv subproblemele
3. •Combina — combină soluțiile subproblemelor

Complexitate tipică: O(n log n)

Algoritmi Clasici Divide et Impera

1. MergeSort — Sortare prin Interclasare

Copiază
1void merge(int arr[], int st, int mij, int dr) {
2    int n1 = mij - st + 1, n2 = dr - mij;
3    vector<int> L(n1), R(n2);
4    
5    for (int i = 0; i < n1; i++) L[i] = arr[st + i];
6    for (int j = 0; j < n2; j++) R[j] = arr[mij + 1 + j];
7    
8    int i = 0, j = 0, k = st;
9    while (i < n1 && j < n2) {
10        if (L[i] <= R[j]) arr[k++] = L[i++];
11        else arr[k++] = R[j++];
12    }
13    while (i < n1) arr[k++] = L[i++];
14    while (j < n2) arr[k++] = R[j++];
15}
16
17void mergeSort(int arr[], int st, int dr) {
18    if (st < dr) {
19        int mij = st + (dr - st) / 2;
20        mergeSort(arr, st, mij);
21        mergeSort(arr, mij + 1, dr);
22        merge(arr, st, mij, dr);
23    }
24}

Complexitate: O(n log n) timp, O(n) spațiu

2. QuickSort

Copiază
1int partition(int arr[], int st, int dr) {
2    int pivot = arr[dr], i = st - 1;
3    for (int j = st; j < dr; j++) {
4        if (arr[j] <= pivot) {
5            i++;
6            swap(arr[i], arr[j]);
7        }
8    }
9    swap(arr[i+1], arr[dr]);
10    return i + 1;
11}
12
13void quickSort(int arr[], int st, int dr) {
14    if (st < dr) {
15        int pi = partition(arr, st, dr);
16        quickSort(arr, st, pi - 1);
17        quickSort(arr, pi + 1, dr);
18    }
19}

Complexitate: O(n log n) mediu, O(n²) worst case

3. Căutare Binară

Copiază
1int binarySearch(int arr[], int n, int target) {
2    int st = 0, dr = n - 1;
3    while (st <= dr) {
4        int mij = st + (dr - st) / 2;
5        if (arr[mij] == target) return mij;
6        if (arr[mij] < target) st = mij + 1;
7        else dr = mij - 1;
8    }
9    return -1;
10}

4. Turnurile Hanoi

Copiază
1void hanoi(int n, char src, char dest, char aux) {
2    if (n == 1) {
3        cout << "Muta discul 1 de pe " << src << " pe " << dest << "\n";
4        return;
5    }
6    hanoi(n-1, src, aux, dest);
7    cout << "Muta discul " << n << " de pe " << src << " pe " << dest << "\n";
8    hanoi(n-1, aux, dest, src);
9}
10// Apel: hanoi(n, 'A', 'C', 'B');

Aplicații la BAC Informatică

La BAC informatică, divide et impera apare în:

• •Sortarea eficientă a vectorilor (MergeSort, QuickSort)
• •Căutare în vectori sorți (Binary Search)
• •Turnurile Hanoi (recursivitate pură)
• •Puterea unui număr (exponentiere rapidă)

Copiază
1// Exponentiere rapidă — O(log n)
2long long putere(long long baza, int exp) {
3    if (exp == 0) return 1;
4    if (exp % 2 == 0) {
5        long long half = putere(baza, exp / 2);
6        return half * half;
7    }
8    return baza * putere(baza, exp - 1);
9}

Comparație MergeSort vs QuickSort