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 între1
șin
.
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
Setul de probleme 231 nu a fost găsit.
Probleme de sortare folosind Divide et Impera
Setul de probleme 232 nu a fost găsit.
Bibliografie sau alte resurse
DS
Autorul acestei lecții
Dominic Satnoianu
Această lecție a fost redactată de către Dominic Satnoianu.
© 2021 – 2025 Aspire Education Labs SRL. Toate drepturile rezervate.
Așa cum este specificat și în termeni și condiții, conținutul acestei pagini este protejat de legea drepturilor de autor și este interzisă copierea sau modificarea acestuia fără acordul scris al autorilor.
Încălcarea drepturilor de autor este o infracțiune și se pedepsește conform legii.
Cuprinsul lecției
Ce este Divide et Impera?Exemplu: suma numerelor unui vector folosind Divide et ImperaStructura unui program de tip Divide et ImperaSuma elementelor unui vector folosind Divide et Impera în C++Maximul unui vector folosind Divide et Impera în C++Probleme propuseProbleme diverse cu Divide et ImperaProbleme de sortare folosind Divide et ImperaBibliografie sau alte resurseCreează-ți un cont InfoAs și primești…
- Acces la sute de lecții de calitate, cu animații și exerciții
- Acces la peste 800 de probleme de informatică
- Indicații și rezolvări pentru fiecare problemă
- Totul 100% gratuit!
Comentarii 0