Școala Româno-Britanică
Modulul 4 Clasa a X-a | C++

Ora 1: Metoda Divide et impera - caracteristici

Ce vei învăța astăzi: Principiul metodei Divide et impera: descompunere, rezolvare și combinare

Rezultat practic: Recunoști cele trei etape ale metodei și scrii o funcție recursivă (o funcție care se apelează pe ea însăși, până ajunge la un caz simplu, rezolvabil direct) care calculează suma unui interval, ca prim pas în rezolvarea problemelor cu Divide et impera (Competența 1.3).

Competența 1.3 Săptămâna 18

Înainte de a începe

De ce contează? Cele trei etape pe care le înveți astăzi sunt schema comună a tuturor algoritmilor D&I din modul: merge sort, căutarea binară și maximul funcționează exact pe acest model.

Ce știi deja?

În clasa a IX-a ai scris funcții și ai văzut cum funcționează recursivitatea (factorial, Fibonacci). Poți spune care este condiția de oprire a unei astfel de funcții și ce se întâmplă dacă lipsește?

Ideea-cheie: O funcție D&I are mereu aceeași schemă: cazul de bază, împărțirea intervalului la jumătate, două apeluri recursive și combinarea rezultatelor.
SINTEZĂ TEORETICĂ ȘI EXEMPLE GHIDATE

Ce vei învăța astăzi?

După această lecție vei înțelege principiul metodei Divide et impera („împarte și stăpânește") și vei putea să descompui o problemă, să rezolvi subproblemele și să le combini rezultatele, folosind C++.

Ce înseamnă „divide et impera"
Cele trei etape: descompunere, rezolvare, combinare
Cazul de bază al recursivității
Suma unui interval în C++, stil BAC

Ce este metoda Divide et impera?

Definiție: Divide et impera este o metodă de programare în care o problemă este descompusă în două sau mai multe subprobleme de același tip, dar de dimensiuni mai mici (subprobleme = probleme mai mici, de aceeași natură cu problema inițială). Subproblemele se rezolvă (eventual tot prin descompunere), iar rezultatele lor se combină pentru a obține soluția problemei inițiale.

Descompunere

Împărțim problema în subprobleme independente, de același tip

Rezolvare

Rezolvăm subproblemele; cele suficient de mici se rezolvă direct

Combinare

Combinăm rezultatele subproblemelor în soluția finală

Analogie: împărțirea unei foi la jumătăți

Trebuie să numeri paginile dintr-un teanc de 64 de foi. În loc să numeri una câte una, împărți teancul în două jumătăți (32 și 32). Fiecare jumătate se împarte din nou la jumătăți (16 și 16), și tot așa, până când rămân teancuri de o singură foaie, care se numără imediat. Apoi aduni numărătoarele, două câte două, până obții totalul.

  • Descompunere: teancul se împarte la jumătăți până la o foaie
  • Rezolvare: o singură foaie se numără direct
  • Combinare: adunăm numerele din jumătăți

Când aplicăm metoda?

Metoda se aplică atunci când o problemă poate fi împărțită în subprobleme independente (care nu depind una de alta), iar subproblemele ajung, prin împărțiri repetate, la cazuri triviale (atât de simple încât se rezolvă imediat), rezolvabile direct.

Exemplu: suma numerelor de la 1 la 8

Descompunem suma 1+2+3+4+5+6+7+8 în sume mai mici:

Descompunerea în subprobleme
suma(1, 8) = suma(1, 4) + suma(5, 8)

suma(1, 4)  = suma(1, 2) + suma(3, 4)
suma(5, 8)  = suma(5, 6) + suma(7, 8)

suma(1, 2)  = suma(1, 1) + suma(2, 2) = 1 + 2 = 3
suma(3, 4)  = 3 + 4 = 7
suma(5, 6)  = 5 + 6 = 11
suma(7, 8)  = 7 + 8 = 15

suma(1, 8) = 3 + 7 + 11 + 15 = 36

Observă: cazul de bază apare când intervalul are un singur element (st == dr). Fiecare apel recursiv împarte intervalul în două jumătăți egale.

Etapă Ce se întâmplă În funcția suma
Descompunere Împărțim intervalul în două jumătăți mij = (st + dr) / 2
Rezolvare Rezolvăm fiecare jumătate prin apel recursiv suma(st, mij) și suma(mij+1, dr)
Combinare Adunăm rezultatele celor două jumătăți return suma(st, mij) + suma(mij+1, dr)
Caz de bază Interval de un element, rezolvat direct if (st == dr) return st;

Primul program: suma unui interval

Scriem o funcție recursivă suma(st, dr) care returnează suma tuturor numerelor întregi dintre st și dr. În C++, stil BAC, funcția se definește înainte de main().

algoritm Suma_DI citește n scrie suma(1, n) sfârșit algoritm funcție suma(st, dr): dacă st == dr atunci returnează st // cazul de bază: un singur element altfel mij = (st + dr) / 2 // descompunere s1 = suma(st, mij) // rezolvare: jumătatea stângă s2 = suma(mij + 1, dr) // rezolvare: jumătatea dreaptă returnează s1 + s2 // combinare sfârșit dacă sfârșit funcție
C++ - suma de la 1 la n prin Divide et impera
#include <iostream>
using namespace std;

int suma(int st, int dr) {
    if (st == dr) {
        return st;
    }
    int mij = (st + dr) / 2;
    return suma(st, mij) + suma(mij + 1, dr);
}

int main() {
    int n;
    cin >> n;
    cout << suma(1, n) << endl;
    return 0;
}

Ce învățăm: if (st == dr) este cazul de bază care oprește recursivitatea; mij este punctul de divizare; suma finală se obține prin combinarea sumelor celor două jumătăți.

Exercițiu de completare

Completează enunțul despre metoda Divide et impera cu cuvintele potrivite:

Divide et impera înseamnă a ______ o problemă în ______ de același tip, de dimensiuni mai mici. Subproblemele se ______ independent, iar rezultatele se ______ pentru a obține soluția ______.

Bancă de cuvinte:
descompune subprobleme rezolvă combină finală

Exercițiu de completare: codul sursă

Completează descrierea funcției suma:

În funcția suma: cazul de bază este st == ______; mijlocul se calculează cu mij = (st + dr) / ______; apelul pentru jumătatea stângă este suma(st, ______); combinarea rezultatelor se face cu operatorul ______.

Bancă de cuvinte:
dr 2 mij +

Test de înțelegere

Test rapid - Divide et impera:

1. Metoda Divide et impera descompune o problemă în:

2. Cazul de bază al funcției suma(st, dr) este:

3. Recursivitatea se oprește atunci când:

Ai grijă la: fără un caz de bază corect (st == dr), funcția se apelează la nesfârșit și programul se prăbușește cu eroare de stivă; la Bacalaureat intervalele sunt valide, dar cazul de bază trebuie scris exact.

Aprofundare

Cazuri particulare și capcane: ce se întâmplă dacă apelăm funcția suma(st, dr) cu un interval gol, adică st > dr? Fără o verificare suplimentară, recursivitatea ar continua la infinit și ar produce depășirea stivei (stack overflow). În practică, la Bacalaureat intervalele sunt mereu valide (st ≤ dr), dar e bine să știi că o soluție robustă tratează și acest caz, întorcând 0 pentru o sumă goală.

De ce împărțim exact la jumătate? Formula mij = (st + dr) / 2 asigură o adâncime de recursie egală cu log₂(n). La fiecare nivel, numărul de apeluri se dublează, dar dimensiunea intervalului se înjumătățește, deci totalul operațiilor rămâne liniar: complexitatea de timp este O(n), iar cea de memorie (stiva de apeluri) este O(log n).

Comparație cu formula directă: suma 1 + 2 + ... + n se poate calcula și cu formula n * (n + 1) / 2, în timp constant. Metoda Divide et impera nu este necesară aici, dar este perfectă pentru a înțelege mecanismul recursiv; aceeași schemă de descompunere-rezolvare-combinare se folosește apoi pentru probleme unde nu există formulă directă, cum sunt maximul, merge sort sau căutarea binară.

Limite numerice: pentru valori mari ale lui n, suma poate depăși limita tipului int. În astfel de probleme se folosește long long (ca în ora1, problema „Suma pe interval"). Recursivitatea nu schimbă valoarea rezultatului, ci doar ordinea în care se adună termenii.

Exemplu din viața reală: gândiți-vă la un magazin care trebuie să verifice câte produse dintr-un raft de 1000 de produse sunt expirate. În loc să parcurgă raftul pe rând, un angajat împarte raftul în două, doi angajați împart din nou în două, și tot așa până fiecare verifică un singur produs; apoi adună rezultatele. Este exact schema Divide et impera, iar beneficiul real apare când subproblemele se rezolvă în paralel sau când un singur element se verifică instantaneu.

APLICARE ȘI REZOLVARE DE PROBLEME

PbInfo - Suma (Divide et impera)

Enunț:

Cerință: Se citește un număr natural n. Să se afișeze suma 1 + 2 + ... + n, calculată cu metoda Divide et impera.

Date de intrare:

Programul citește de la tastatură numărul n.

Date de ieșire:

Programul va afișa pe ecran suma 1 + 2 + ... + n.

Restricții și precizări:

1 ≤ n ≤ 100000; suma se calculează obligatoriu printr-o funcție recursivă de tip Divide et impera, cu intervalul [st, dr].

Exemplu:

Intrare:

8

Ieșire:

36
Cum gândim soluția:
  1. Definim funcția suma(st, dr): dacă st == dr, returnăm st
  2. Calculăm mijlocul: mij = (st + dr) / 2
  3. Returnăm suma(st, mij) + suma(mij + 1, dr)
  4. În main() citim n și afișăm suma(1, n)
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;

int suma(int st, int dr) {
    if (st == dr) {
        return st;
    }
    int mij = (st + dr) / 2;
    return suma(st, mij) + suma(mij + 1, dr);
}

int main() {
    int n;
    cin >> n;
    cout << suma(1, n) << endl;
    return 0;
}

Ce învățăm: acest program conține toate cele trei etape ale metodei: descompunerea la jumătate, rezolvarea recursivă și combinarea prin adunare.

PbInfo - Suma pe interval

Enunț:

Cerință: Se citesc două numere naturale a și b (a ≤ b). Să se afișeze suma tuturor numerelor din intervalul [a, b], calculată cu metoda Divide et impera.

Date de intrare:

Programul citește de la tastatură numerele a și b, separate printr-un spațiu.

Date de ieșire:

Programul va afișa pe ecran suma numerelor din intervalul [a, b].

Restricții și precizări:

1 ≤ a ≤ b ≤ 100000; rezultatul poate depăși valoarea 2000000000, deci se folosește long long.

Exemplu:

Intrare:

3 7

Ieșire:

25
Cum gândim soluția:
  1. Definim funcția suma(st, dr) cu tipul de rezultat long long
  2. Cazul de bază: st == dr, returnăm st
  3. Împărțim la mij = (st + dr) / 2 și combinăm cu plus
  4. Citim a și b, apoi afișăm suma(a, b)
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;

long long suma(int st, int dr) {
    if (st == dr) {
        return st;
    }
    int mij = (st + dr) / 2;
    return suma(st, mij) + suma(mij + 1, dr);
}

int main() {
    int a, b;
    cin >> a >> b;
    cout << suma(a, b) << endl;
    return 0;
}

Ce învățăm: funcția se definește înainte de main(), iar tipul long long evită depășirea valorilor pentru intervale mari.

EXERCIȚII PRACTICE

Exercițiul Practic: Primele funcții Divide et impera

Sarcini de lucru

Completează următoarele sarcini pentru a-ți consolida cunoștințele despre metoda Divide et impera

Sarcina 1: Produsul numerelor de la 1 la n

Cerință: Scrie un program C++ care citește n și afișează produsul 1 · 2 · ... · n, folosind o funcție recursivă produs(st, dr) după modelul metodei Divide et impera. Folosește long long pentru rezultat.

Soluție pentru Sarcina 1:
#include <iostream>
using namespace std;

long long produs(int st, int dr) {
    if (st == dr) {
        return st;
    }
    int mij = (st + dr) / 2;
    return produs(st, mij) * produs(mij + 1, dr);
}

int main() {
    int n;
    cin >> n;
    cout << produs(1, n) << endl;
    return 0;
}

Verifică: pentru n = 5, produsul este 1 · 2 · 3 · 4 · 5 = 120. Cazul de bază rămâne st == dr, iar combinarea se face cu înmulțire.

Sarcina 2: Numărarea numerelor negative

Cerință: Se citesc n numere întregi într-un tablou global v. Scrie o funcție recursivă nrNegative(st, dr) care returnează câte numere negative se află pe intervalul [st, dr], folosind metoda Divide et impera. În main() afișează rezultatul pentru întregul tablou.

Soluție pentru Sarcina 2:
#include <iostream>
using namespace std;

int v[1001];

int nrNegative(int st, int dr) {
    if (st == dr) {
        if (v[st] < 0) {
            return 1;
        } else {
            return 0;
        }
    }
    int mij = (st + dr) / 2;
    return nrNegative(st, mij) + nrNegative(mij + 1, dr);
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    cout << nrNegative(1, n) << endl;
    return 0;
}

Verifică: pentru n = 5 și valorile -2 4 -6 8 -1, rezultatul este 3. La cazul de bază, fiecare element „votează" 1 dacă este negativ și 0 altfel; combinarea este o simplă adunare.

SCRIE PE CAIET

Scrie pe caiet - Metoda Divide et impera

Titlul lecției

  • Ora 1: Metoda Divide et impera - caracteristici

Definiția lecției

Divide et impera („împarte și stăpânește") este o metodă de programare care rezolvă o problemă în trei etape: descompunerea în subprobleme de același tip, dar de dimensiuni mai mici, rezolvarea fiecărei subprobleme (direct, la cazul de bază, sau prin apeluri recursive) și combinarea rezultatelor în soluția finală. Metoda se aplică atunci când subproblemele sunt independente și ajung, prin împărțiri repetate, la cazuri simple, rezolvabile direct. Exemplul central al lecției este calculul sumei unui interval [st, dr] printr-o funcție recursivă, cu mijlocul mij = (st + dr) / 2. La Bacalaureat, funcția se definește înainte de main(), iar cazul de bază (st == dr) oprește recursivitatea. Aceeași schemă de descompunere-rezolvare-combinare se folosește apoi pentru maxim, merge sort și căutarea binară.

Definiții esențiale

  • Divide et impera („împarte și stăpânește") este o metodă de programare în care o problemă se descompune în subprobleme de același tip, dar de dimensiuni mai mici, care se rezolvă independent, iar rezultatele lor se combină pentru a obține soluția problemei inițiale.
  • Descompunere: împărțirea problemei la jumătate (mij = (st + dr) / 2).
  • Rezolvare: apeluri recursive pentru fiecare jumătate; cazul de bază (st == dr) se rezolvă direct.
  • Combinare: reunirea rezultatelor subproblemelor în soluția finală.
  • Caz de bază: condiția care oprește recursivitatea, de regulă un interval cu un singur element.

Algoritmul cheie - pseudocod (Suma unui interval)

  • funcție suma(st, dr): dacă st == dr returnează st; altfel mij = (st + dr) / 2 și returnează suma(st, mij) + suma(mij + 1, dr).
  • În main(): citește n și scrie suma(1, n).

Algoritmul cheie - cod C++

  • Funcția se definește înainte de main().
  • Structura: int suma(int st, int dr) { if (st == dr) return st; int mij = (st + dr) / 2; return suma(st, mij) + suma(mij + 1, dr); }

Greșeli comune de evitat

  • Omiterea cazului de bază st == dr duce la recursivitate infinită.
  • Împărțirea greșită a intervalului (de exemplu suma(st, mij - 1)) pierde elementul din mijloc.
  • Folosirea lui int pentru rezultate care pot depăși 2 miliarde; la nevoie se folosește long long.
  • Apelarea funcției înainte de definiție produce eroare de compilare; definește întâi funcția.

Sfaturi practice și trucuri

  • Verifică întotdeauna cazul de bază înainte de a scrie partea recursivă.
  • Pentru a depana, scrie manual pașii pentru un interval mic, de exemplu suma(1, 4).
  • Formula mij = (st + dr) / 2 funcționează pentru orice interval; jumătatea dreaptă începe întotdeauna de la mij + 1.
  • Recunoaște schema: dacă o problemă „se înjumătățește" și are un caz trivial, atunci se pretează la Divide et impera.

Exemplu practic

O echipă numără cărțile dintr-o bibliotecă cu 16 rafturi, fiecare cu un anumit număr de cărți. În loc să numere raft cu raft, împarte rafturile în două grupe de 8, apoi fiecare grupă în două de 4, și tot așa, până când fiecare membru numără un singur raft; la final, rezultatele se adună două câte două. Același mecanism este implementat de funcția de mai jos pentru suma unui interval de numere:

C++ - suma unui interval prin Divide et impera
int suma(int st, int dr) {
    if (st == dr) {
        return st;
    }
    int mij = (st + dr) / 2;
    return suma(st, mij) + suma(mij + 1, dr);
}