Divide et impera în C++: maximul unui vector

Divide et impera rezolvă o problemă împărțind-o în subprobleme mai mici, rezolvându-le și combinând rezultatele. Cele trei etape trebuie să fie vizibile în explicație și în program. Nu orice funcție recursivă împarte problema în două și nu orice împărțire în jumătăți produce timp logaritmic.

Ai nevoie de recursivitate și parcurgerea vectorilor. Vom calcula maximul unui tablou nevid. Exemplul este ales pentru a urmări ușor combinarea; pentru această cerință, o parcurgere simplă rămâne o soluție mai directă.

Ce reprezintă un apel

Funcția maximInterval(a, stanga, dreapta) întoarce maximul elementelor dintre cei doi indici, cu ambele capete incluse. Precondiția este 0 <= stanga <= dreapta < n. Primul apel primește intervalul [0, n - 1].

Când stanga == dreapta, intervalul conține exact un element, iar maximul este chiar acel element. Acesta este cazul de bază. Nu folosim zero ca rezultat implicit, fiindcă toate valorile pot fi negative. De asemenea, nu apelăm această funcție pentru un interval gol.

Pentru cel puțin două elemente calculăm mijloc = stanga + (dreapta - stanga) / 2. Împărțim în [stanga, mijloc] și [mijloc + 1, dreapta]. Cele două intervale acoperă exact datele inițiale, fără goluri și fără elemente comune.

Împărțim intervalul, rezolvăm ambele jumătăți și alegem maximul rezultatelor.

De ce apelurile se opresc

Dacă intervalul are cel puțin două elemente, mijlocul este strict mai mic decât capătul drept. Fiecare jumătate conține mai puține elemente decât intervalul inițial și rămâne nevidă. Lungimile scad până când fiecare apel ajunge la un singur element.

Capătul mijloc + 1 este esențial pentru jumătatea dreaptă. Dacă am folosi din nou mijloc, un interval de două elemente ar putea reapărea neschimbat într-un apel. Înainte să scrii recursia, verifică manual împărțirea pentru lungimile 1, 2 și 3.

Varianta cu tablou clasic

Programul citește n, cu 1 <= n <= 1000, apoi n întregi între -1000000000 și 1000000000. Afișează maximul. Funcția primește tabloul numai pentru citire, prin const int a[]; apelantul păstrează responsabilitatea pentru limitele indicilor.

#include <iostream>
int maximInterval(const int a[], int stanga, int dreapta) {
    if (stanga == dreapta) {
        return a[stanga];
    }
    int mijloc = stanga + (dreapta - stanga) / 2;
    int primul = maximInterval(a, stanga, mijloc);
    int alDoilea = maximInterval(a, mijloc + 1, dreapta);
    if (primul > alDoilea) {
        return primul;
    }
    return alDoilea;
}
int main() {
    int n = 0;
    std::cin >> n;
    int a[1000]{};
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    std::cout << maximInterval(a, 0, n - 1) << '\n';
    return 0;
}

Pentru 7 2 9 4, apelurile pentru jumătăți întorc 7 și 9. Apelul inițial le compară și întoarce 9. Pentru -8 -2 -5, rezultatul este -2: aceeași regulă funcționează fără tratare separată a semnului.

Varianta cu std::vector

Algoritmul folosește aceiași indici și aceleași intervale. Transmitem containerul prin referință constantă, astfel încât apelurile nu copiază întregul vector și nu modifică elementele. Nu construim vectori noi pentru jumătăți; trimitem doar limitele lor.

#include <iostream>
#include <vector>
int maximInterval(const std::vector<int>& a, int stanga, int dreapta) {
    if (stanga == dreapta) {
        return a[stanga];
    }
    int mijloc = stanga + (dreapta - stanga) / 2;
    int primul = maximInterval(a, stanga, mijloc);
    int alDoilea = maximInterval(a, mijloc + 1, dreapta);
    if (primul > alDoilea) {
        return primul;
    }
    return alDoilea;
}
int main() {
    int n = 0;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    std::cout << maximInterval(a, 0, n - 1) << '\n';
    return 0;
}

Corectitudine și cost

Pentru un singur element, răspunsul este corect prin definiție. Presupunând că cele două apeluri întorc maximele corecte ale jumătăților, cel mai mare dintre rezultate este maximul întregului interval. Orice element aparține uneia dintre jumătăți, deci nu poate depăși maximul ales la combinare.

Arborele apelurilor are n frunze, câte una pentru fiecare element. Fiecare apel care nu este frunză face două apeluri și o comparație între rezultate. Sunt n - 1 asemenea combinări, deci timpul total este O(n), nu O(log n). Împărțirea echilibrată reduce adâncimea, dar ambele jumătăți trebuie vizitate.

Adâncimea stivei este O(log n) pentru n > 1. Apelurile pentru cele două jumătăți se execută pe rând; stiva nu păstrează întregul arbore simultan. Tabloul clasic rezervă capacitatea de 1000 de elemente, iar std::vector păstrează n elemente. Spațiul suplimentar al recursiei este separat de stocarea datelor.

O parcurgere iterativă calculează același maxim în O(n) timp și O(1) spațiu suplimentar. Divide et impera este util aici ca model de descompunere, nu ca optimizare a maximului. În alte probleme, precum sortarea prin interclasare, modul de combinare are un rol mai complex și trebuie analizat separat.

Exersează

1. Cum se împarte intervalul inclusiv [0, 2]?
2. Câte comparații între rezultate sunt necesare pentru patru elemente?
3. De ce nu acceptăm n = 0 în acest program?
4. Cum adaptezi funcția pentru minim?

Răspunsuri: [0, 1] și [2, 2]; trei; primul apel nu ar avea un interval nevid, încălcând precondiția; păstrezi împărțirea și alegi rezultatul mai mic. Pentru sumă, combinarea ar aduna rezultatele, necesitând și un tip suficient de mare.

Revino la cuprinsul capitolului sau continuă cu grafuri și arbori.