Divide et Impera (metodă de programare C++)

Vedem că există multe probleme care se pot rezolva prin împărțirea lor în subprobleme mai mici și mai ușor de rezolvat (care la rândul lor se pot împărți în probleme și mai mici și tot așa, până când ajungem la probleme foarte ușoare care se pot rezolva pe loc). Iată un tip de cerință:

Se dă un șir de n numere naturale. Se cere calcularea sumei tuturor numerelor.

Putem să împărțim problema în a calcula suma primelor n / 2 valori, la care adunăm suma ultimelor n / 2 valori. După aceea, fiecare secvență o putem împărți la rândul ei în alte două secvențe mai mici, până când ajungem la secvențe de lungime 1, în care suma este chiar valoarea respectivă (mai jos găsim un exemplu vizual).

Aceste tipuri de probleme se pot rezolva folosind metoda Divide et Impera.

Ce este Divide et Impera?

Divide et Impera este o metodă de programare recursivă ce constă în principiul următor:

• descompunem problema curentă în două sau mai multe subprobleme (de același tip ca problema inițială, însă mai mici sau mai ușoare);
• fiecare subproblemă se rezolvă separat (se pot descompune la rândul lor în alte subprobleme și mai ușoare);
• se combină rezultatele fiecărei subprobleme, pentru a forma soluția problemei inițiale.

Trebuie menționat faptul că subproblemele:

• trebuie să fie de același tip ca problema inițială;
• trebuie să fie mai simple;
• trebuie să fie independente unele de altele, pentru a nu risca suprapunerea rezultatelor.

Atunci când ajungem la o (sub)problemă indivizibilă (fie că este foarte ușor de găsit răspunsul pe loc, sau că pur și simplu nu mai putem să dividem problema mai mult), atunci ne aflăm la o așa-numită problemă elementară, care se rezolvă într-un alt mod, de regulă brut.

Exemplu: suma numerelor unui vector folosind Divide et Impera

Să luăm exemplul de mai devreme: suma numerelor unui șir. Reformulăm un pic problema:

Se dă un șir de n numere naturale. Să se calculeze suma numerelor cu indicii între 1 și n.

Reformulând astfel problema, ne este mai ușor să găsim o rezolvare Divide et Impera.

Avem șirul inițial, pe care îl vom descompune în două jumătăți. Fiecare jumătate o vom descompune la rândul ei în alte două jumătăți și tot așa, până când ajungem să avem secvențe de lungime 1, unde pur și simplu returnăm elementul curent, întrucât nu mai putem să împărțim în secvențe mai mici.

Pentru problema curentă, după calcularea rezultatelor din subprobleme, le vom aduna în acest caz pentru a forma rezultatul problemei curente (întrucât trebuie să calculăm suma numerelor).

Să vedem un exemplu vizual:

Pentru a calcula suma elementelor din vectorul (22, 2, 15, 44, 41, 7, 29, 49, 31, 24), îl împărțim în două secvențe (prima și a doua jumătate), pe care le despărțim la rândul lor în alte două secvențe și așa mai departe, până când ajungem la secvențe de numere individuale, pe care le procesăm direct.

Observație: Nu trebuie neapărat să împărțim în două subprobleme. Am putea să împărțim șirul în 3, 4, …, însă din punct de vedere al eficienței nu suntem mai avantajați cu mult, iar împărțirea în mai multe subprobleme devine impractică la un moment dat.

Totuși, există situații când este mai util să împărțim în mai mult de două subprobleme. Spre exemplu, într-o matrice căruia vrem să îi aflăm suma elementelor, poate fi practic să împărțim în 4 zone.

Structura unui program de tip Divide et Impera

Un program de tip Divide et Impera este recursiv. Astfel, de regulă, avem următoarea structură:

┌ rezolvă(pb)
│  ┌ dacă pb este problemă elementară
│  │   raspuns = rezolvareDirectă(pb)
│  ├ altfel
│  │   subPb1, subPb2 ← descompune(pb)
│  │   raspuns1 ← rezolvă(subPb1)
│  │   raspuns2 ← rezolvă(subPb2)
│  │   raspuns ← combinăRezulate(raspuns1, raspuns2)
│  └■
│  returnează raspuns
└■

Suma elementelor unui vector folosind Divide et Impera în C++

Rezolvăm problema propusă la începutul lecției. Vom folosi doi indici, st și dr, care marchează secvența curentă a problemei. Problema în sine se rezolvă apelând funcția cu indicii st = 1 și dr = n, iar de aici împărțim recursiv problema în jumătăți, luând la final suma fiecărei jumătăți.

Problema elementară apare atunci când st = dr, adică atunci când avem un singur element. În acest caz, returnăm pur și simplu elementul de pe poziția dată.

#include <iostream>

using namespace std;

int sumaDivImp(int a[], int st, int dr) {
    //Explicații: infoas.ro
    if(st == dr) { //Problemă elementară
        return a[st];
    }
    int mij = (st + dr) / 2;

    int suma1 = sumaDivImp(a, st, mij); //Subproblema 1
    int suma2 = sumaDivImp(a, mij + 1, dr); //Subproblema 2
    return suma1 + suma2; //Rezolvarea problemei
}

int main()
{
    //Declarăm și citim șirul în ordinea: lungimea șirului, elementele șirului
    int a[100], n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    cout << "Suma numerelor sirului este " << sumaDivImp(a, 1, n);
    return 0;
}

Maximul unui vector folosind Divide et Impera în C++

Similar ca mai devreme, putem să calculăm maximul (sau minimul) dintre elementele unui vector. De menționat este faptul că, spre deosebire de suma elementelor, pentru a calcula maximul nu este nicio problemă dacă se suprapun anumite subprobleme (în afară de faptul că ar încetini programul), pentru că maximul rămâne tot același chiar dacă verificăm de mai multe ori același element.

#include <iostream>

using namespace std;

int maxDivImp(int a[], int st, int dr) {
    //Explicații: infoas.ro
    if(st == dr) { //Problemă elementară
        return a[st];
    }
    int mij = (st + dr) / 2;

    int max1 = maxDivImp(a, st, mij); //Subproblema 1
    int max2 = maxDivImp(a, mij + 1, dr); //Subproblema 2
    if(max1 > max2) return max1;
    return max2;
}

int main()
{
    //Declarăm și citim șirul în ordinea: lungimea șirului, elementele șirului
    int a[100], n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    cout << "Maximul numerelor sirului este " << maxDivImp(a, 1, n);
    return 0;
}

Probleme propuse

Probleme diverse cu Divide et Impera

#	Problemă	Dificultate
703.	Toate egale Divide et Impera	Medie (4 )
704.	Cmmdc sir Divide et Impera	Medie (4 )
694.	Suma sirului Divide et Impera	Ușoară (2 )
701.	Maximul sirului Divide et Impera	Ușoară (2 )
699.	Numarare palindrom Divide et Impera	Medie (4 )
Vrei mai multe probleme? Pe această pagină găsești întreaga listă de probleme propuse.

Probleme de sortare folosind Divide et Impera

#	Problemă	Dificultate
771.	La furat de corcoduse	Grea (8 )

Bibliografie sau alte resurse

• Recursivitate
• Divide et impera și probleme diverse cu recursivitate (Sync.ro)
• Divide et Impera (PbInfo)
• Divide et Impera (informatică) (Wikipedia)