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

Ora 13: Recapitulare generală

Ce vei învăța astăzi: Să recunoști și să compari metoda Divide et impera și metoda Greedy, recapitulând toți algoritmii modulului: sumă, maxim, merge sort, căutare binară (căutare într-un tablou sortat care elimină jumătate din interval la fiecare pas), inversiuni, monede, spectacole, rucsac fracționar și platou

Rezultat practic: Rezolvi probleme de recapitulare de tip PbInfo (maxim prin D&I, rest cu monede) și construiești tabelul rezumativ D&I vs Greedy cu complexitățile tuturor algoritmilor (Competența 5.3).

Competența 5.3 Săptămâna 24

Înainte de a începe

De ce contează? Înainte de evaluarea finală, recapitularea transformă cunoștințele împrăștiate în scheme mentale — exact ce ai nevoie pentru un test de 100 de puncte.

Ce știi deja?

În 13 ore ai scris peste zece programe complete. Fără să te uiți în caiet, enumeră câte un algoritm pentru fiecare metodă și complexitatea lui.

Ideea-cheie: Toți algoritmii D&I au aceeași schemă (caz de bază, mijloc, apeluri, combinare), iar toate problemele greedy au același pasaj: optim local (cea mai bună alegere la pasul curent), fără reconsiderare.
SINTEZĂ TEORETICĂ ȘI EXEMPLE GHIDATE

Ce vei învăța astăzi?

După această lecție vei recapitula întreg modulul: toți algoritmii Divide et impera și Greedy, complexitățile lor și tabelul rezumativ care te ajută să alegi metoda potrivită la orice problemă de bacalaureat.

Recapitularea algoritmilor D&I
Recapitularea algoritmilor Greedy
Tabel rezumativ D&I vs Greedy
Recapitularea complexităților

Recapitulare: Divide et impera

Ideea: problema se descompune în subprobleme de același tip (probleme mai mici, de aceeași natură cu cea inițială), se rezolvă recursiv (cazul de bază rezolvat direct), apoi rezultatele se combină. Toate funcțiile au aceeași schemă: caz de bază, mij = (st + dr) / 2, apeluri recursive, combinare.

Problemă Caz de bază Combinare Complexitate
Suma intervalului st == dr → st adunare O(n)
Maximul / minimul st == dr → v[st] comparație O(n)
Merge sort un element, deja sortat interclasare O(n log n)
Căutarea binară st > dr → nu există restrângere la o jumătate O(log n)
Inversiunile un element, fără inversiuni interclasare + contor O(n log n)
Căutare în tablou rotit st > dr → 0 jumătate sortată + restrângere O(log n)

Reține: două convenții de caz de bază: st == dr pentru sumă, maxim, numărare; st > dr pentru căutări. Amestecarea lor este cea mai frecventă greșeală.

Recapitulare: metoda Greedy

Ideea: la fiecare pas alegem optimul local, fără a reconsidera deciziile. Corectitudinea se bazează pe substructura optimală; fiecare problemă are criteriul ei local, pe care trebuie să-l recunoști din enunț.

Problemă Criteriul greedy Etapele
Restul cu monede cea mai mare monedă care încape buclă + while pe rest
Spectacolele sortare după ora de sfârșit sortare + parcurgere
Rucsacul fracționar eficiență valoare / greutate sortare + umplere
Problema platoului cât mai multe pătrate pe fiecare direcție formula (L/l) * (W/l)
Platoul extins pătrat cu latura dimensiunii mai mici divizări cu rest repetate

Reține: sortarea este aproape întotdeauna pasul de pregătire al Greedy. Pentru n mare, alege merge sort; pentru n mic, sortarea prin selecție este suficientă și mai simplă.

Tabel rezumativ: D&I vs Greedy

Criteriu Divide et impera Greedy
Mod de lucru descompune în subprobleme, apoi combină construiește soluția pas cu pas
Decizii toate subproblemele sunt rezolvate alege optimul local, fără reconsiderare
Recursivitate esențială (caz de bază + divizare) de obicei iterativ
Exemple sumă, maxim, merge sort, căutare binară, inversiuni monede, spectacole, rucsac fracționar, platou
Garantarea optimului da, metoda este corectă prin construcție doar dacă substructura optimală există
Complexitate tipică O(log n), O(n), O(n log n) O(n), O(n log n) cu sortare

Program recapitulativ: maximul prin D&I

funcție maxim(st, dr): dacă st == dr atunci returnează v[st] mij = (st + dr) / 2 a = maxim(st, mij) b = maxim(mij + 1, dr) dacă a > b atunci returnează a altfel returnează b citește n, v[1..n] scrie maxim(1, n)
C++ - maximul prin Divide et impera (recapitulare)
#include <iostream>
using namespace std;

int v[1001];

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

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

Ce învățăm: acest program reunește toate elementele D&I: tablou global, funcție înainte de main(), caz de bază, divizare, apeluri recursive reținute în variabile, combinare prin comparație.

Ai grijă la: tabelul complexităților: O(n log n) pentru merge sort și inversiuni, O(log n) pentru căutări, O(n) pentru sumă și maxim — amestecarea lor este greșeala nr. 1 la Subiectul I.

Aprofundare

Cum alegi metoda la examen: citește enunțul și caută indicii. „Funcție recursivă", „interval", „înjumătățire", „căutare într-un tablou sortat" indică D&I. „Număr minim de monede", „număr maxim de activități", „valoare maximă, fracționar", „alege cât mai multe" indică Greedy. Dacă ambele apar, problema este combinată, ca la ora 12.

Complexități care se cer la oral: suma și maximul prin D&I fac n - 1 operații (stiva are adâncimea log₂(n)); merge sort compară pe fiecare nivel n elemente, deci n log₂(n); căutarea binară elimină o jumătate la fiecare pas, deci log₂(n); monedele parcurg 6 valori fixe, deci O(1) față de n; spectacolele și rucsacul cu sortare prin selecție sunt O(n), cu merge sort O(n log n).

Legătura dintre lecțiile modulului: ora 1-4 au construit reflecția D&I (sumă, maxim, merge sort, căutare), ora 5-8 au construit reflecția Greedy (monede, spectacole, rucsac, platou), ora 9 a comparat metodele, iar ora 10-12 au adăugat aplicațiile avansate: inversiuni, tablou rotit, rucsac eficient, platou extins și probleme combinate. Toate împreună formează „arsenalul" de subiecte de bacalaureat pe acest modul.

Greseli de recapitulare, sistematizate: (1) cazuri de bază amestecate; (2) comparații cu < în loc de <= la inversiuni; (3) criterii greedy greșite (sortare după început, nu după sfârșit); (4) tipuri prea mici (int în loc de long long); (5) uitarea condițiilor de oprire din buclele greedy.

Exemplu din viața reală: un magazin online care gestionează livrările folosește căutarea binară pentru a găsi rapid o comandă într-o listă sortată (D&I), sortarea prin interclasare pentru listele de livrare (D&I) și algoritmul greedy pentru încărcarea mașinilor de curierat. În spatele fiecărui buton de „plasare a comenzii" stau exact metodele recapitulate astăzi.

Exercițiu de completare

Completează comparația celor două metode:

D&I ______ problema în subprobleme, pe când Greedy alege ______ local. D&I ______ rezultatele subproblemelor; Greedy nu ______ asupra deciziilor.

Bancă de cuvinte:
descompune optimul combină revine

Exercițiu de completare: complexitățile modulului

Completează cu complexitățile potrivite:

Merge sort are complexitatea ______. Căutarea binară are complexitatea ______. Maximul prin D&I are complexitatea ______. Restul cu monede parcurge un număr ______ de valori, deci timpul nu depinde de n.

Bancă de cuvinte:
O(n log n) O(log n) O(n) constant

Test de înțelegere

Test final - recapitulare generală:

1. Care dintre următorii algoritmi este o aplicație Divide et impera?

2. Care dintre următoarele este o aplicație Greedy?

3. Complexitatea căutării într-un tablou sortat și rotit este:

APLICARE ȘI REZOLVARE DE PROBLEME

PbInfo - Maximul prin D&I (recapitulare)

Enunț:

Cerință: Se citește n și apoi n numere întregi. Să se afișeze valoarea maximă, determinată cu 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 valoarea maximă.

Restricții și precizări:

1 ≤ n ≤ 1000; elementele sunt numere întregi.

Exemplu:

Intrare:

6
4 9 2 7 5 8

Ieșire:

9
Cum gândim soluția:
  1. Definim maxim(st, dr): caz de bază st == dr
  2. Împărțim la mijloc și returnăm maximul celor două jumătăți
  3. Afișăm maxim(1, n)
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;

int v[1001];

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

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

Ce învățăm: maximul prin D&I rezolvă problema în O(n) comparații, cu aceeași schemă: divizare, apeluri recursive, comparație la combinare.

PbInfo - Restul cu monede (recapitulare)

Enunț:

Cerință: Se dă suma S. Să se afișeze numărul minim de monede cu care poate fi plătită suma S, folosind monede de valori 100, 50, 10, 5, 2, 1 (metoda Greedy).

Date de intrare:

Programul citește de la tastatură numărul natural S.

Date de ieșire:

Programul va afișa numărul minim de monede.

Restricții și precizări:

1 ≤ S ≤ 100000; se folosește metoda Greedy.

Exemplu:

Intrare:

88

Ieșire:

7
Cum gândim soluția:
  1. Definim tabloul monede descrescător
  2. Pentru fiecare monedă, cât timp încape, o scădem și numărăm
  3. Afișăm numărul total
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int monede[] = {100, 50, 10, 5, 2, 1};
    int nr = 0;
    for (int i = 0; i < 6; i++) {
        while (n >= monede[i]) {
            n -= monede[i];
            nr++;
        }
    }
    cout << nr << endl;
    return 0;
}

Ce învățăm: 88 = 50 + 10 + 10 + 10 + 5 + 2 + 1, deci 7 monede. Alegerea greedy a monedei celei mai mari dă numărul minim pentru sistemul canonic.

EXERCIȚII PRACTICE

Exercițiul Practic: recapitulare generală a modulului

Sarcini de lucru

Rezolvă sarcinile de mai jos pentru a încheia recapitularea modulului 4

Sarcina 1: Merge sort (recapitulare)

Cerință: Scrie programul complet de sortare prin interclasare (merge sort), crescător, pentru un vector cu n elemente.

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

int v[1001], temp[1001];

void interclaseaza(int st, int mij, int dr) {
    int i = st, j = mij + 1, k = st;
    while (i <= mij && j <= dr) {
        if (v[i] < v[j]) {
            temp[k++] = v[i++];
        } else {
            temp[k++] = v[j++];
        }
    }
    while (i <= mij) {
        temp[k++] = v[i++];
    }
    while (j <= dr) {
        temp[k++] = v[j++];
    }
    for (int p = st; p <= dr; p++) {
        v[p] = temp[p];
    }
}

void mergeSort(int st, int dr) {
    if (st < dr) {
        int mij = (st + dr) / 2;
        mergeSort(st, mij);
        mergeSort(mij + 1, dr);
        interclaseaza(st, mij, dr);
    }
}

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

Verifică: pentru v = 5 2 8 1 9 3, rezultatul este 1 2 3 5 8 9. Funcțiile sunt definite înainte de main(), iar temp este vector auxiliar.

Sarcina 2: Spectacolele (recapitulare)

Cerință: Scrie programul complet pentru problema Spectacole: citește n spectacole (început, sfârșit) și afișează numărul maxim de spectacole compatibile, folosind metoda Greedy.

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

int inceput[101], sfarsit[101];

void sorteaza(int n) {
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (sfarsit[i] > sfarsit[j]) {
                int aux = sfarsit[i];
                sfarsit[i] = sfarsit[j];
                sfarsit[j] = aux;
                aux = inceput[i];
                inceput[i] = inceput[j];
                inceput[j] = aux;
            }
        }
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> inceput[i] >> sfarsit[i];
    }
    sorteaza(n);
    int nr = 1;
    int ultimul = sfarsit[1];
    for (int i = 2; i <= n; i++) {
        if (inceput[i] >= ultimul) {
            nr++;
            ultimul = sfarsit[i];
        }
    }
    cout << nr << endl;
    return 0;
}

Verifică: pentru spectacolele (1,3), (2,5), (4,6), (6,8), rezultatul este 3. Sortarea după sfârșit este criteriul greedy care maximizează numărul de spectacole.

SCRIE PE CAIET

Scrie pe caiet - Recapitulare generală a modulului 4

Titlul lecției

  • Ora 13: Recapitulare generală

Definiția lecției

Lecția recapitulă întregul modul 4 înaintea evaluării finale. Toți algoritmii Divide et impera (sumă, maxim, minim, merge sort, căutare binară, inversiuni, tablou rotit) respectă aceeași schemă: caz de bază, mijloc, apeluri recursive, combinare. Toate problemele Greedy (monede, spectacole, rucsac fracționar, platou clasic și extins) aleg pas cu pas optimul local, fără reconsiderare. Tabelul rezumativ D&I vs Greedy reunește fiecare algoritm cu cazul său de bază, criteriul de combinare sau de alegere și complexitatea. La recapitulare se exersează și recunoașterea metodei potrivite pentru o problemă dată, exact decizia cerută la Bacalaureat. Materialul de studiu este întreg modulul: schemele, programele și greșelile comune din lecțiile 1-12.

Definiții esențiale

  • Divide et impera: descompunere, rezolvare recursivă, combinare; exemple: sumă, maxim, merge sort, căutare binară, inversiuni, tablou rotit.
  • Greedy: alegerea optimului local, fără reconsiderare; exemple: monede, spectacole, rucsac fracționar, platou (clasic și extins).
  • Substructură optimală: proprietatea care garantează corectitudinea Greedy.
  • Problemă combinată: D&I pregătește sau verifică datele, Greedy ia deciziile.

Algoritmul cheie - pseudocod

  • Schema D&I: dacă st == dr → caz de bază; altfel mij, apeluri recursive, combinare (adunare, comparație, interclasare).
  • Schema Greedy: sortare după criteriul local, apoi buclă de alegeri cu condiții de oprire.

Algoritmul cheie - cod C++

  • maxim(st, dr): caz de bază v[st], divizare, compararea lui a și b.
  • mergeSort + interclaseaza cu temp.
  • Monede: while (n >= monede[i]) pe tablou descrescător.
  • Spectacole: sortare după sfarsit, numărare cu inceput[i] >= ultimul.

Greșeli comune de evitat

  • Cazurile de bază amestecate: st == dr la sumă/maxim, st > dr la căutări.
  • Greedy fără substructură optimală verificată (exemplu: monede 1, 3, 4).
  • Tipuri prea mici: long long pentru inversiuni și sume mari.
  • Uitarea condițiilor de oprire (g == 0, rest 0) în buclele greedy.

Sfaturi practice și trucuri

  • Ține un tabel de sinteză cu toți algoritmii modulului, criteriile și complexitățile lor.
  • Pentru fiecare problemă de antrenament, numește întâi metoda și justificarea, apoi scrie codul.
  • Testează cazurile limită: vector cu un element, n = 1, rest 0, capacitate mai mare decât suma greutăților.
  • Înainte de evaluare, reia de la ora 1 și scrie din memorie fiecare program principal.

Exemplu practic

Un elev se pregătește pentru test repetând fiecare program din memorie: pentru maximul prin D&I scrie funcția de mai jos, apoi o rulează mental pe un vector mic, de exemplu v = [4, 9, 2, 7], unde rezultatul este 9:

C++ - maximul unui tablou prin Divide et impera
int maxim(int st, int dr) {
    if (st == dr) {
        return v[st];
    }
    int mij = (st + dr) / 2;
    int a = maxim(st, mij);
    int b = maxim(mij + 1, dr);
    if (a > b) {
        return a;
    }
    return b;
}