1. Principiul Divide et Impera

Avem o carte de telefon cu peste 1000 pagini, ordonată alfabetic. Căutăm numele Popescu.

În loc să răsfoiești pagină cu pagină (metodă liniară, lentă), ce-ar fi să înjumătățești problema la fiecare pas?

Pasul 1: Deschizi cartea exact la jumătate (pagina 500). Găsești numele Minescu.

Unde cauți pe Popescu mai departe?

Pasul 2: Ai aruncat prima jumătate! Acum ai rămas cu paginile 501-1000. Deschizi iar la jumătate (pagina 750). Găsești numele Stan.

Unde cauți pe Popescu acum?

Pasul 3: Fantastic. Mai ai paginile 501-749. Deschizi din nou la mijloc (pagina 625). Găsești numele Petrescu.

Cum procedezi?

Ai înțeles perfect!

Din doar 3 mișcări ai redus problema de la 1000 de pagini la doar 124. Aceasta este esența metodei Divide et Impera: împarți problema la mijloc, decizi ce jumătate păstrezi, și repeți (recursivitate). Injumătățirile se opresc când ai ajuns la problema banală (ai ajuns la pagina care conține numele căutat)

2. Logica Recursivă pe Vectori

Când aplicăm această logică pe un vector v, definim un interval prin indicii st (stânga) și dr (dreapta). Apasă pe cardurile de mai jos pentru a înțelege cum descompunem matematic diverse probleme:

Suma Elementelor

Combinație: Suma = Suma(Jum_St) + Suma(Jum_Dr)

Explicație: Tăiem vectorul la jumătate până ajungem la intervale de 1 element. Suma unui singur element este el însuși. Urcând înapoi pe stivă, adunăm rezultatele din stânga și dreapta.

Minimul / Maximul

Combinație: Max = max(Max_St, Max_Dr)

Explicație: Găsim cel mai mare număr din prima jumătate și din a doua. La final (pe ramura de return), doar comparăm maximul pe jumătatea stânga cu maximul pe jumătatea dreaptă cu o structură if(a > b).

CMMDC Vector

Combinație: Cmmdc = euclid(Cmmdc_St, Cmmdc_Dr)

Explicație: Ne folosim de funcția clasică Euclid. La cazul de bază, cmmdc-ul este chiar `v[st]`. La combinare, aplicăm algoritmul lui Euclid între cele două rezultate obținute recursiv.

Contorizarea

Combinație: Total = Contor_St + Contor_Dr

Explicație: Dacă vrem să aflăm câte numere sunt pare, la nivelul de bază verificăm: e par? returnăm 1, altfel 0. Adunăm apoi "1"-urile obținute de pe ambele ramuri.

Căutarea Binară

Combinație: Nu se combină direct.

Explicație: Este un DEI "degenerat" pe un vector ordonat. La fiecare pas tăiem vectorul la jumătate, dar apelăm recursiv doar o singură jumătate (cea în care știm sigur că s-ar afla elementul), aruncând-o pe cealaltă.

Toate respectă o regulă

Combinație: Valid = Valid_St && Valid_Dr

Explicație: (Ex: "Toate sunt pozitive?"). Cazul de bază returnează 1 (Adevărat) sau 0 (Fals). Combinarea se face prin ȘI logic (&&). O singură valoare de 0 strică tot rezultatul.

3. Scheletul C++

Orice problemă rezolvată prin DEI respectă structura de mai jos. Urmărește indentarea și separarea pașilor logici.

int divideEtImpera(int st, int dr) {
    if (st == dr) {
        // 1. CAZ DE BAZĂ: Intervalul are lungimea 1
        return v[st];
    } else {
        // 2. DIVIDE: Calculăm mijlocul
        int mij = (st + dr) / 2;
        
        // 3. STĂPÂNEȘTE: Apeluri recursive pe subprobleme
        int rez1 = divideEtImpera(st, mij);
        int rez2 = divideEtImpera(mij + 1, dr);
        
        // 4. COMBINĂ: Aplicăm logica problemei
        return rez1 + rez2; // Exemplu pentru suma elementelor
    }
}

4. Exerciții Ghidate

Completează căsuțele libere respectând sintaxa C++.

A. Căutarea Binară

Se dă un vector ordonat crescător. Caută valoarea x.

int cautaBin(int st, int dr, int x) {
    if (st > dr) return -1; // Caz de bază de ieșire (nu s-a găsit)
    int m = (st + dr) / 2;
    if (v[m] == x) return m;
    
    if (x < v[m]) {
        // Căutăm doar în stânga
        return cautaBin(st, , x);
    } else {
        // Căutăm doar în dreapta
        return cautaBin(, dr, x);
    }
}

B. Maximul dintr-un vector

int maxim(int st, int dr) {
    if (st == dr) {
        return v[];
    } else {
        int m = (st + dr) / 2;
        int m1 = maxim(st, m);
        int m2 = maxim(, dr);
        
        if (m1 > m2) {
            return ;
        } else {
            return m2;
        }
    }
}

C. CMMDC al vectorului

int cmmdcV(int st, int dr) {
    if (st == dr) {
        return ;
    } else {
        int m = (st + dr) / 2;
        int a = cmmdcV(st, );
        int b = cmmdcV(m + 1, dr);
        return euclid(, );
    }
}

D. Contorizarea numerelor pozitive

int nrPozitive(int st, int dr) {
    if (st == dr) {
        if (v[st] > 0) return ;
        else return ;
    } else {
        int m = (st + dr) / 2;
        return nrPozitive(st, m)  nrPozitive(m + 1, dr);
    }
}

E. Suma numerelor prime

Se consideră definită funcția estePrim(nr) care returnează 1 dacă e prim, 0 altfel.

int sumaPrime(int st, int dr) {
    if (st == dr) {
        if (estePrim(v[st]) == 1) return ;
        else return ;
    } else {
        int m = (st + dr) / 2;
        return sumaPrime(st, m) + sumaPrime(, dr);
    }
}

5. Turnurile din Hanoi

Aplicația cea mai interesantă a DEI: mută un disc mare vizând mai întâi mutarea celor `n-1` discuri mai mici pe tija intermediară.

Discuri:

6. Autoevaluare: Scrie logica

Scrie expresiile C++ necesare direct în cod. Urmărește logica cerințelor din fiecare enunț.

1. Câte numere sunt strict mai mari decât X?

int maiMariX(int st, int dr, int x) {
    if (st == dr) {
        ;
    } else {
        int m = (st + dr) / 2;
        return maiMariX(st, m, x) + maiMariX(m + 1, dr, x);
    }
}

2. Există vreun element negativ în vector? (Returnează 1 sau 0)

int existaNegativ(int st, int dr) {
    if (st == dr) {
        if (v[st] < 0) return 1;
        else return 0;
    } else {
        int m = (st + dr) / 2;
        int a = existaNegativ(st, m);
        int b = existaNegativ(m + 1, dr);
        // Combinăm: trebuie doar SAU logic
        return ;
    }
}

3. Suma tuturor elementelor din vector

int sumaVector(int st, int dr) {
    if (st == dr) {
        return ;
    } else {
        int m = (st + dr) / 2;
        return ;
    }
}

4. Toate elementele sunt impare? (Verificare universală)

int toateImpare(int st, int dr) {
    if (st == dr) {
        if (v[st] % 2 != 0) return 1;
        else return 0;
    } else {
        int m = (st + dr) / 2;
        int a = toateImpare(st, m);
        int b = toateImpare(m + 1, dr);
        // Combinăm prin ȘI logic
        return ;
    }
}

5. Reamintește-ți Căutarea Binară

int cautaBin_Eval(int st, int dr, int x) {
    if (st > dr) return -1;
    int m = (st + dr) / 2;
    if (v[m] == x) return m;
    else if (x < v[m]) 
        return cautaBin_Eval(st, , x);
    else
        return cautaBin_Eval(, dr, x);
}

7. Evaluare Finală

Alege răspunsul corect analizând secvențele de cod. Apasă "Calculează Nota" la final pentru feedback pe fiecare întrebare.

1. Pentru calculul sumei elementelor IMPARE, ce trebuie să returneze cazul de bază dacă numărul curent este PAR?

if (st == dr) {
    if (v[st] % 2 != 0) return v[st];
    else  _______;
}

A) return v[st]; B) return 0; C) return 1;

2. Ce se va întâmpla dacă uităm instrucțiunea if (st == dr) la o problemă recursivă DEI?

A) Funcția intră într-o recursivitate infinită (Stack Overflow). B) Va returna mereu 0.

3. Dorim să verificăm dacă TOATE numerele dintr-un vector sunt pozitive. Ce operator introducem?

A) || (SAU logic) B) && (ȘI logic)

4. Analizează secvența. Ce problemă rezolvă funcția?

if (st == dr) return v[st];
else {
    int m = (st + dr) / 2;
    int x = calc(st, m);
    int y = calc(m + 1, dr);
    return x * y;
}

A) Suma elementelor din vector B) Produsul elementelor din vector

5. Care este expresia corectă pentru a determina poziția de mijloc a intervalului curent?

A) int m = (st + dr) / 2; B) int m = st + dr / 2;

6. La căutarea binară, dacă elementul căutat nu există, ce condiție declanșează returnarea lui -1?

A) st == dr B) st > dr

7. Vrem să contorizăm numerele care sunt pătrate perfecte. Dacă v[st] este pătrat perfect, ce returnează cazul de bază?

A) return v[st]; B) return 1;

8. De ce sunt incorecte următoarele apeluri recursive în faza Divide et Impera?

int stanga = rezolva(st, m);
int dreapta = rezolva(m, dr);

A) Intervalele se suprapun (elementul m e procesat de două ori). B) Este obligatoriu să folosim variabile cu litere mari.

9. Aflăm MINIMUL dintr-un vector. Completează faza de combinare:

int min1 = minim(st, mij);
int min2 = minim(mij + 1, dr);
if (min1 < min2) return _______;
else return min2;

A) min1 B) min2

10. La CMMDC-ul unui vector, de ce cazul de bază if (st == dr) returnează v[st]?

A) Pentru că CMMDC-ul unui singur număr este chiar acel număr. B) Pentru a număra câte numere prime sunt în total.

Tehnica de Programare "Divide et Impera"