Clasa X - Ora 4: Aplicații Divide et impera

SINTEZĂ TEORETICĂ ȘI EXEMPLE GHIDATE

Ce vei învăța astăzi?

După această lecție vei aplica aceeași schemă D&I (divizare, rezolvare, combinare) la trei probleme clasice și vei înțelege căutarea binară ca o aplicație a metodei.

Suma elementelor unui tablou prin D&I

Numărarea parelor pe interval

Căutarea binară ca D&I

Două probleme PbInfo rezolvate

Suma elementelor unui tablou

Pentru a însuma elementele unui tablou pe intervalul [st, dr], împărțim la jumătate, însumăm fiecare jumătate prin apel recursiv (apel al funcției de către ea însăși, pe un interval mai mic) și adunăm rezultatele. La cazul de bază (st == dr), suma este chiar v[st].

funcție suma(st, dr): dacă st == dr atunci returnează v[st] // cazul de bază: un singur element mij = (st + dr) / 2 returnează suma(st, mij) + suma(mij + 1, dr) // combinare prin adunare funcție nrPare(st, dr): dacă st == dr atunci dacă v[st] % 2 == 0 atunci returnează 1 altfel returnează 0 mij = (st + dr) / 2 returnează nrPare(st, mij) + nrPare(mij + 1, dr) // combinare prin adunare funcție cauta(st, dr, x): dacă st > dr atunci returnează 0 // elementul x nu există mij = (st + dr) / 2 dacă v[mij] == x atunci returnează mij // găsit pe poziția mij dacă v[mij] > x atunci returnează cauta(st, mij - 1, x) // restrângem la stânga altfel returnează cauta(mij + 1, dr, x) // restrângem la dreapta citește n, v[1..n] scrie suma(1, n), nrPare(1, n), cauta(1, n, x)

C++ - suma elementelor prin Divide et impera

#include <iostream>
using namespace std;

int v[1001];

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

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

Numărarea elementelor pare pe interval

La fel ca la sumă, dar la cazul de bază returnăm 1 dacă elementul este par și 0 altfel. La combinare adunăm numărătorile celor două jumătăți.

C++ - numărarea elementelor pare prin D&I

#include <iostream>
using namespace std;

int v[1001];

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

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

Observă: singura diferență față de sumă este cazul de bază: în loc să returnăm valoarea elementului, returnăm 1 sau 0 în funcție de paritate.

Căutarea binară, o aplicație D&I

Căutarea binară caută valoarea x într-un tablou sortat crescător. Comparăm x cu elementul din mijloc: dacă sunt egale, am găsit poziția; dacă x este mai mic, căutăm în jumătatea stângă; altfel, în cea dreaptă.

căutarea lui x = 7 în v = [1, 3, 5, 7, 9, 11]

cauta(1, 6, 7)

mij=3 v[3] = 5 < 7, căutăm în dreapta: cauta(4, 6, 7)

mij=5 v[5] = 9 > 7, căutăm în stânga: cauta(4, 4, 7)

mij=4 v[4] = 7 == 7, am găsit poziția 4

C++ - căutarea binară recursivă

#include <iostream>
using namespace std;

int v[1001];

int cauta(int st, int dr, int x) {
    if (st > dr) {
        return 0;
    }
    int mij = (st + dr) / 2;
    if (v[mij] == x) {
        return mij;
    }
    if (x < v[mij]) {
        return cauta(st, mij - 1, x);
    }
    return cauta(mij + 1, dr, x);
}

int main() {
    int n, x;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    cin >> x;
    int poz = cauta(1, n, x);
    if (poz == 0) {
        cout << "NU" << endl;
    } else {
        cout << poz << endl;
    }
    return 0;
}

Ce învățăm: cazul de bază st > dr înseamnă că x nu există; fiecare pas elimină o jumătate din interval, deci complexitatea este O(log n).

Exercițiu de completare

Completează enunțul despre căutarea binară:

Căutarea binară cere ca vectorul să fie ______. Comparăm x cu elementul din ______; dacă sunt ______, am găsit poziția; dacă x este mai mic, continuăm în ______.

Bancă de cuvinte:

sortat mijloc egale stânga

Exercițiu de completare: codul căutării

Completează descrierea funcției cauta:

Dacă x este mai mic, căutăm în ______ intervalului, apelând cauta(st, mij - 1, x); altfel căutăm în ______, cu cauta(mij + 1, dr, x). Cazul de bază este st ______ dr, ceea ce înseamnă că x nu există.

Bancă de cuvinte:

stânga dreapta >

Test de înțelegere

Test rapid - aplicații D&I:

1. Căutarea binară are complexitatea:

O(log n) O(n) O(n)

2. Căutarea binară presupune ca tabloul să fie:

sortat crescător cu elemente distincte aleatorii gol

3. La numărarea parelor prin D&I, la combinare se face:

adunarea rezultatelor celor două jumătăți înmulțirea rezultatelor celor două jumătăți scăderea rezultatelor celor două jumătăți

Ai grijă la: cazul de bază al căutării binare este st > dr (interval gol), nu st == dr ca la sumă; amestecarea lor este greșeala care costă cel mai des puncte la Subiectul II.

Aprofundare

O schemă, trei probleme: suma, numărarea parelor și căutarea binară folosesc aceeași divizare la mij = (st + dr) / 2, dar diferă prin cazul de bază și prin combinare: adunare pentru sumă, adunare de valori 0/1 pentru numărare, și renunțarea la o jumătate pentru căutarea binară. Recunoașterea acestei scheme unice te ajută să scrii orice funcție D&I în câteva linii.

Căutarea binară: de ce este atât de rapidă? La fiecare pas, intervalul de căutare se înjumătățește, deci după k pași rămân n / 2ᵏ elemente. Căutarea se oprește când intervalul se golește, deci 2ᵏ = n, adică k = log₂(n). Complexitatea este O(log n): căutarea unui element între un milion de valori necesită doar aproximativ 20 de comparații, spre deosebire de căutarea secvențială, care poate ajunge la un milion.

Condiția esențială a căutării binare: vectorul trebuie să fie sortat crescător. Pe un vector nesortat, înjumătățirea nu are sens, pentru că elementul căutat poate fi în oricare jumătate. La BAC, această condiție este aproape întotdeauna dată explicit în enunț; verifică-o înainte de a scrie soluția.

Cazul „elementul nu există": la căutarea binară, cazul de bază este st > dr, adică intervalul s-a golit, caz în care funcția întoarce 0 (sau -1, după cerință). La sumă și la numărare, cazul de bază este st == dr; nu confunda cele două convenții.

Exemplu din viața reală: un telefon de tip vechi cu listă de contacte sortată alfabetic funcționează exact ca o căutare binară: deschizi lista la mijloc, compari litera căutată și restrângi căutarea la jumătatea potrivită. Un dicționar tipărit se folosește tot așa, și de aceea găsim un cuvânt în câteva secunde, deși dicționarul are zeci de mii de intrări.

APLICARE ȘI REZOLVARE DE PROBLEME

PbInfo - Căutare binară

Enunț:

Cerință: Se citește un tablou cu n elemente, sortat crescător, și o valoare x. Să se afișeze poziția primei apariții a lui x, sau mesajul NU dacă x nu apare.

Date de intrare:

Programul citește n, apoi cele n elemente ale tabloului, apoi valoarea x.

Date de ieșire:

Programul va afișa poziția lui x (numerotată de la 1) sau mesajul NU.

Restricții și precizări:

1 ≤ n ≤ 100000; elementele sunt distincte și sortate crescător; se cere căutare binară (Divide et impera).

Exemplu:

Intrare:

6
1 3 5 7 9 11
7

Ieșire:

Cum gândim soluția:

Definim cauta(st, dr, x): dacă st > dr, returnăm 0
Comparăm x cu v[mij] și ne restrângem la o jumătate
În main() interpretăm rezultatul 0 ca „NU"

Scrie soluția în C++:

Soluție corectă:

#include <iostream>
using namespace std;

int v[100001];

int cauta(int st, int dr, int x) {
    if (st > dr) {
        return 0;
    }
    int mij = (st + dr) / 2;
    if (v[mij] == x) {
        return mij;
    }
    if (x < v[mij]) {
        return cauta(st, mij - 1, x);
    }
    return cauta(mij + 1, dr, x);
}

int main() {
    int n, x;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    cin >> x;
    int poz = cauta(1, n, x);
    if (poz == 0) {
        cout << "NU" << endl;
    } else {
        cout << poz << endl;
    }
    return 0;
}

Ce învățăm: fiecare apel recursiv elimină jumătate din interval, deci algoritmul este foarte eficient chiar și pentru n mare.

PbInfo - Numărul de elemente pare

Enunț:

Cerință: Se citește un număr natural n și apoi n numere întregi. Să se afișeze câte dintre ele sunt pare, folosind o funcție recursivă de tip Divide et impera.

Date de intrare:

Programul citește n, apoi cele n numere.

Date de ieșire:

Programul va afișa numărul de elemente pare din tablou.

Restricții și precizări:

1 ≤ n ≤ 1000; elementele pot fi negative; un număr este par dacă restul împărțirii la 2 este 0.

Exemplu:

Intrare:

6
4 7 2 9 6 1

Ieșire:

Cum gândim soluția:

La cazul de bază returnăm 1 dacă v[st] % 2 == 0, altfel 0
Împărțim la jumătate și adunăm rezultatele celor două jumătăți
Afișăm nrPare(1, n)

Scrie soluția în C++:

Soluție corectă:

#include <iostream>
using namespace std;

int v[1001];

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

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

Ce învățăm: aceeași schemă D&I rezolvă probleme diferite; schimbăm doar ceea ce se întâmplă la cazul de bază și la combinare.

EXERCIȚII PRACTICE

Exercițiul Practic: căutări și numărători D&I

Sarcini de lucru

Rezolvă sarcinile de mai jos pentru a aplica metoda D&I în situații noi

Sarcina 1: Prima apariție a valorii x

Cerință: Un tablou sortat poate conține valori repetate. Scrie funcția prima(st, dr, x) care returnează poziția primei apariții a lui x (sau 0 dacă nu apare), folosind căutarea binară. În main() afișează rezultatul.

Scrie programul C++ aici:

Soluție pentru Sarcina 1:

#include <iostream>
using namespace std;

int v[1001];

int prima(int st, int dr, int x) {
    if (st > dr) {
        return 0;
    }
    int mij = (st + dr) / 2;
    if (v[mij] == x) {
        int p = prima(st, mij - 1, x);
        if (p != 0) {
            return p;
        }
        return mij;
    }
    if (x < v[mij]) {
        return prima(st, mij - 1, x);
    }
    return prima(mij + 1, dr, x);
}

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

Verifică: pentru v = 1 2 2 2 3 și x = 2, rezultatul este 2 (prima apariție). După găsirea lui x în mijloc, mai căutăm în stânga pentru a verifica dacă există o apariție mai din față.

Sarcina 2: Suma și numărul de impare

Cerință: Scrie un program C++ complet care citește n și n numere, apoi afișează pe două linii: suma elementelor și numărul de elemente impare, ambele calculate cu funcții recursive de tip Divide et impera.

Scrie programul C++ aici:

Soluție pentru Sarcina 2:

#include <iostream>
using namespace std;

int v[1001];

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

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

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

Verifică: pentru n = 5 și valorile 2 3 4 5 6, suma este 20, iar numărul de impare (3 și 5) este 2.

SCRIE PE CAIET

Scrie pe caiet - Aplicații Divide et impera

Titlul lecției

Ora 4: Aplicații Divide et impera

Definiția lecției

În această lecție, aceeași schemă D&I (caz de bază, mijloc, apeluri recursive, combinare) se aplică la trei probleme. Suma elementelor unui tablou întoarce v[st] la cazul de bază și combină cu adunarea; numărarea parelor întoarce 1 sau 0 la cazul de bază, după testul v[st] % 2 == 0, și combină tot cu adunarea. Căutarea binară diferă: lucrează doar pe tablouri sortate, întoarce 0 la cazul de bază st > dr (elementul nu există) și, la fiecare pas, restrânge intervalul la o singură jumătate, de unde complexitatea O(log n). Tabloul este global, iar funcțiile sunt definite înainte de main(). Aceste trei funcții sunt modelele după care se scriu cele mai frecvente probleme de Bacalaureat pe metoda Divide et impera.

Definiții esențiale

Suma elementelor pe interval: caz de bază st == dr returnează v[st]; combinarea se face cu operatorul +.
Numărarea parelor: la cazul de bază se returnează 1 dacă elementul este par, altfel 0; combinarea este tot adunarea.
Căutarea binară: aplicație D&I pe tablou sortat crescător; la fiecare pas se renunță la o jumătate a intervalului, complexitate O(log n).
Caz de bază specific căutării: st > dr (interval gol) înseamnă că elementul nu există.

Algoritmul cheie - pseudocod

Schema comună: caz de bază → mij = (st + dr) / 2 → apeluri recursive → combinare.
Suma și numărarea combină cu +; căutarea binară alege o singură jumătate: cauta(st, mij - 1, x) sau cauta(mij + 1, dr, x).

Algoritmul cheie - cod C++

int suma(int st, int dr): if (st == dr) return v[st]; apoi return suma(st, mij) + suma(mij + 1, dr);
int nrPare(int st, int dr): caz de bază cu testul v[st] % 2 == 0.
int cauta(int st, int dr, int x): if (st > dr) return 0; testează v[mij] și restrânge recursiv la jumătatea potrivită.
Tabloul v este global, iar funcțiile sunt definite înainte de main().

Greșeli comune de evitat

Căutarea binară pe un vector nesortat nu funcționează; verifică dacă enunțul garantează sortarea.
Folosirea lui st == dr ca caz de bază la căutarea binară lasă elementul din mijloc neexaminat; trebuie st > dr.
La sumă, uitarea că cazul de bază întoarce v[st], nu st.
Modificarea accidentală a vectorului în timpul recursivității (de exemplu suprascrierea în altă funcție).

Sfaturi practice și trucuri

Memorează diferența dintre cele două cazuri de bază: st == dr (sumă, numărare) și st > dr (căutare).
Pentru căutare, testează și cazul „x mai mic decât toate" și „x mai mare decât toate": ambele trebuie să întoarcă 0.
Scrie funcțiile întâi pe hârtie, în pseudocod, apoi transpunerea în C++ devine mecanică.
La proba orală, justifică complexitatea căutării binare cu înjumătățirea repetată a intervalului.

Exemplu practic

Un catalog cu notele unei clase, sortat crescător, este căutat pentru a afla dacă un elev a primit nota 9. În loc să parcurgem toate notele, comparăm valoarea căutată cu elementul din mijloc și renunțăm la jumătate din listă la fiecare pas, exact ca în funcția de mai jos (cu tabloul global v, sortat crescător):

C++ - căutarea binară recursivă

int cauta(int st, int dr, int x) {
    if (st > dr) {
        return 0;
    }
    int mij = (st + dr) / 2;
    if (v[mij] == x) {
        return mij;
    }
    if (v[mij] > x) {
        return cauta(st, mij - 1, x);
    }
    return cauta(mij + 1, dr, x);
}

Ora 4: Aplicații Divide et impera

Înainte de a începe

Ce știi deja?

Ce vei învăța astăzi?

Suma elementelor unui tablou

Numărarea elementelor pare pe interval

Căutarea binară, o aplicație D&I

căutarea lui x = 7 în v = [1, 3, 5, 7, 9, 11]

Exercițiu de completare

Completează enunțul despre căutarea binară:

Bancă de cuvinte:

Exercițiu de completare: codul căutării

Completează descrierea funcției cauta:

Bancă de cuvinte:

Test de înțelegere

Test rapid - aplicații D&I:

Aprofundare

PbInfo - Căutare binară

Enunț:

Date de intrare:

Date de ieșire:

Restricții și precizări:

Exemplu:

Cum gândim soluția:

Scrie soluția în C++:

Soluție corectă:

PbInfo - Numărul de elemente pare

Enunț:

Date de intrare:

Date de ieșire:

Restricții și precizări:

Exemplu:

Cum gândim soluția:

Scrie soluția în C++:

Soluție corectă:

Exercițiul Practic: căutări și numărători D&I

Sarcini de lucru

Sarcina 1: Prima apariție a valorii x

Soluție pentru Sarcina 1:

Sarcina 2: Suma și numărul de impare

Soluție pentru Sarcina 2:

Scrie pe caiet - Aplicații Divide et impera

Titlul lecției

Definiția lecției

Definiții esențiale

Algoritmul cheie - pseudocod

Algoritmul cheie - cod C++

Greșeli comune de evitat

Sfaturi practice și trucuri

Exemplu practic