Sinteza Modulului 4 - Clasa X | Școala Româno-Britanică

Definițiile cheie

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, de dimensiuni mai mici; subproblemele se rezolvă recursiv (cazul de bază se rezolvă direct), iar rezultatele lor se combină pentru a obține soluția problemei inițiale.

Descompunere

mij = (st + dr) / 2 și două subintervale

Rezolvare

apeluri recursive; caz de bază st == dr (sau st > dr la căutări)

Combinare

adunare, comparație sau interclasare a rezultatelor

Metoda Greedy construiește soluția pas cu pas, alegând la fiecare pas optimul local, fără a reconsidera deciziile deja luate. Metoda dă soluția globală optimă doar dacă problema are substructură optimală; fiecare problemă are criteriul ei local (moneda cea mai mare, sfârșitul cel mai devreme, eficiența valoare / greutate).

Alte noțiuni esențiale: cazul de bază este condiția care oprește recursivitatea; inversiunea este o pereche (i, j) cu i < j și v[i] > v[j]; tabloul rotit este un tablou sortat tăiat într-un punct; eficiența unui obiect este raportul valoare / greutate; sistem canonic de monede este un sistem pentru care greedy dă numărul minim de monede.

Cum înțelegi metodele pe scurt: la D&I împarți problema în bucăți identice ca tip, rezolvi fiecare bucată separat și apoi combini (în cod, o funcție recursivă cu caz de bază); merge sort este exemplul cel mai clar — împarți vectorul în două, sortezi fiecare jumătate și îmbinzi două șiruri deja sortate, exact cum amesteci corect două pachete de cărți ordonate; la Greedy alegi la fiecare pas cea mai bună mutare locală și nu te mai întorci, ca atunci când plătești cu cea mai mare bancnotă care încape, pentru a folosi cât mai puține bancnote.

Algoritmii principali: Divide et impera

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

procedură mergeSort(st, dr): dacă st < dr atunci mij = (st + dr) / 2 mergeSort(st, mij) mergeSort(mij + 1, dr) interclaseaza(st, mij, dr) sfârșit dacă procedură interclaseaza(st, mij, dr): i = st, j = mij + 1, k = st cât timp i <= mij și j <= dr execută dacă v[i] < v[j] atunci temp[k++] = v[i++] altfel temp[k++] = v[j++] copiază restul din stânga și din dreapta în temp copiază temp[st..dr] în v[st..dr]

C++ - merge sort (algoritmul principal D&I)

#include <iostream>
using namespace std;

int v[100001], temp[100001];

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;
}

Algoritmii principali: Greedy

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

// Monede citește S monede = [100, 50, 10, 5, 2, 1] nr = 0 pentru i = 0, 5 execută cât timp S >= monede[i] execută S -= monede[i] nr++ sfârșit cât timp sfârșit pentru scrie nr // Spectacole sortează spectacolele crescător după sfârșit nr = 1, ultimul = sfârșit[1] pentru i = 2, n execută dacă început[i] >= ultimul atunci nr++ ultimul = sfârșit[i] sfârșit dacă sfârșit pentru scrie nr

C++ - restul minim cu monede și spectacolele

#include <iostream>
using namespace std;

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

C++ - numărul maxim de spectacole

#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;
}

Tabele recapitulative

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, 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

Criteriu	Recursiv (D&I)	Iterativ (Greedy)
Construcția soluției	funcția se apelează pe ea însăși, pe intervale mai mici	bucle repetă un pas, fără auto-apel
Oprirea	cazul de bază, rezolvat direct	condiția de oprire a buclei (rest 0, capacitate 0)
Memorie	stiva de apeluri, O(log n)	doar variabilele buclei, O(1)
Algoritmi tipici	sumă, maxim, merge sort, căutare binară, inversiuni	monede, spectacole, rucsac fracționar, platou

Algoritm	Complexitate de timp	Memorie suplimentară
Suma / maximul / minimul prin D&I	`O(n)`	`O(log n)` stivă
Merge sort	`O(n log n)`	`O(n)` vector auxiliar
Căutarea binară / tabloul rotit	`O(log n)`	`O(log n)` stivă
Numărarea inversiunilor	`O(n log n)`	`O(n)`
Restul cu monede	`O(1)` (6 valori fixe)	`O(1)`
Spectacolele (sortare prin selecție)	`O(n)`	`O(n)`
Rucsac fracționar (cu merge sort)	`O(n log n)`	`O(n)`
Platoul extins	foarte mic, divizări cu rest	`O(1)`

Reguli de aur și greșeli frecvente

Reguli de aur

Funcțiile recursive se definesc înainte de main(); tablourile sunt globale.
Cazul de bază al D&I: st == dr la sumă/maxim/numărare; st > dr la căutări.
La Greedy, identifică mai întâi criteriul local și verifică substructura optimală.
Valorile mari cer long long (inversiuni, sume, medii).
Compară eficiențele cu înmulțiri încrucișate, nu cu împărțiri reale.
La interclasare, copiază restul ambelor secvențe și readu în v.
Buclele greedy au condiții de oprire: rest 0, capacitate 0, interval gol.

Greșeli frecvente

Cazurile de bază amestecate între căutări și agregări.
Greedy aplicat fără verificarea substructurii optimale (contraexemplu: monede 1, 3, 4).
Spectacole sortate după început sau durată, în loc de sfârșit.
Comparație cu < în loc de <= la inversiuni (egalități numărate greșit).
if în loc de while la monede: se ia o singură monedă din fiecare valoare.
Interclasare fără copierea finală în v: vectorul „pierde" sortarea între niveluri.
Uitarea 1.0 la fracțiunile rucsacului: împărțire întreagă, rezultat greșit.

Cum folosești breviarul la recapitulare: acoperă codurile și rescrie-le din memorie; apoi verifică-te cu tabelele de complexități. Dacă un program nu îți iese din memorie, recitește lecția respectivă (ora 1-14) și rescrie-l de trei ori: o dată urmărind, de două ori din memorie.

Ce trebuie să știi pentru test

Lista de verificare, înainte de evaluare

Definiția D&I și cele trei etape: descompunere, rezolvare, combinare.
Definiția Greedy: optim local, fără reconsiderarea deciziilor, substructură optimală.
Cazurile de bază: st == dr la sumă, maxim, numărare; st > dr la căutări.
Complexitățile: merge sort și inversiuni O(n log n), căutare binară O(log n), sumă și maxim O(n), monede O(1), spectacole și rucsac O(n log n) cu sortare.
Interclasarea: vector auxiliar și copierea finală înapoi în v.
Criteriile greedy: moneda cea mai mare, sortare după sfârșit, eficiența valoare / greutate.
Compararea eficiențelor cu înmulțiri încrucișate (v1 * g2), nu cu împărțiri reale.
Funcții definite înainte de main(), tablouri globale.
long long la sume mari și la numărarea inversiunilor.
Testarea programului pe exemplul din enunț, pas cu pas.

Coduri C++ de rezervă pentru Subiectul II

Pe lângă merge sort și monede, reține aceste programe „de rezervă": căutarea binară, suma și maximul prin D&I, și rucsacul fracționar. Le rescrii din memorie la evaluare, apoi le adaptezi la enunț.

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;
    cout << cauta(1, n, x) << endl;
    return 0;
}

C++ - suma și maximul prin D&I

#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 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;
}

C++ - rucsacul fracționar (sortare după eficiență)

#include <iostream>
using namespace std;

int val[1001], gr[1001];

int main() {
    int n, G;
    cin >> n >> G;
    for (int i = 1; i <= n; i++) {
        cin >> val[i] >> gr[i];
    }
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (1LL * val[i] * gr[j] < 1LL * val[j] * gr[i]) {
                int aux = val[i]; val[i] = val[j]; val[j] = aux;
                aux = gr[i]; gr[i] = gr[j]; gr[j] = aux;
            }
        }
    }
    double total = 0;
    for (int i = 1; i <= n && G > 0; i++) {
        if (gr[i] <= G) {
            total += val[i];
            G -= gr[i];
        } else {
            total += 1.0 * val[i] * G / gr[i];
            G = 0;
        }
    }
    cout << total << endl;
    return 0;
}

De reținut: la rucsacul fracționar comparăm eficiențele cu 1LL * val * gr ca să evităm împărțirile reale, iar fracțiunea finală se calculează cu 1.0 * val * G / gr.

Exerciții de recapitulare cu rezolvare

Exercițiu 1 (teorie). De ce complexitatea căutării binare este O(log n), deși și ea folosește D&I?

Rezolvare: la căutarea binară se rezolvă o singură jumătate, nu amândouă; la fiecare pas intervalul se înjumătățește, deci după log₂(n) pași rămâne un singur element.

Exercițiu 2 (greedy). Folosind monedele 100, 50, 10, 5, 2, 1, află numărul minim de monede pentru suma 88.

Rezolvare: 88 − 50 = 38; 38 − 10 = 28; 28 − 10 = 18; 18 − 10 = 8; 8 − 5 = 3; 3 − 2 = 1; 1 − 1 = 0. Monedele folosite: 50, 10, 10, 10, 5, 2, 1 — în total 7 monede.

Exercițiu 3 (mini-provocare). Câte inversiuni are vectorul 3 1 2? Enumeră-le.

Rezolvare: perechile cu i < j și v[i] > v[j] sunt (3, 1) și (3, 2); perechea (1, 2) nu este inversiune, pentru că 1 < 2. Vectorul are 2 inversiuni.

Exercițiu 4 (cod). Scrie, în stil BAC, funcția recursivă care determină maximul elementelor dintre st și dr.

Rezolvare: cazul de bază st == dr returnează v[st]; altfel divizăm la mijloc, reținem maximele celor două jumătăți în variabile și returnăm valoarea mai mare, exact ca în codul din secțiunea „Coduri C++ de rezervă".

Greșeli frecvente la test

Greșeli care costă puncte la Subiectul I

Confundarea complexităților: merge sort cu O(n), căutare binară cu O(n log n).
Amestecarea cazurilor de bază între agregate și căutări.
Afirmația că Greedy reconsideră deciziile sau că merge sort este o metodă Greedy.
Afirmația că Greedy dă optimul global la orice problemă, fără substructură optimală.

Greșeli care costă puncte la Subiectul II

Program care nu compilează: funcții definite după main(), lipsa #include.
if în loc de while la problema monedelor.
Spectacole sortate după început sau durată, nu după sfârșit.
Interclasare fără copierea înapoi în v.
Comparație greșită la inversiuni: egalitățile numărate sau sensul < în loc de >.
Fracțiuni calculate cu împărțire întreagă, fără 1.0.
Uitarea long long la sume mari și la numărul de inversiuni.

Sinteza Modulului 4: Divide et impera și Greedy

Cum folosești această sinteză?