Ce vei învăța astăzi?
După această lecție vei recapitula toate noțiunile modulului, vei compara cele două metode și vei rezolva probleme de test de tip Bacalaureat.
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ă.
| Problemă | Caz de bază | Combinare |
|---|---|---|
| Suma intervalului | st == dr returnăm st |
adunare |
| Maximul / minimul | st == dr returnăm v[st] |
comparație |
| Merge sort | un element, deja sortat | interclasare |
| Căutarea binară | st > dr (x nu există) |
restrângere la o jumătate |
Reține: complexitatea merge sort este O(n log n), iar a căutării binare O(log n).
Recapitulare: metoda Greedy
Ideea: la fiecare pas alegem optimul local, fără a reconsidera deciziile. Dacă problema are substructură optimală, alegerea locală duce la soluția globală optimă.
| Problemă | Criteriul greedy |
|---|---|
| Restul cu monede | cea mai mare monedă care încape |
| Spectacolele | sortare după ora de sfârșit |
| Rucsacul fracționar | eficiență valoare / greutate, descrescător |
| Problema platoului | umplerea pe fiecare direcție |
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ă | monede, spectacole, rucsac fracționar |
| Garantarea optimului | da, metoda este corectă prin construcție | doar dacă substructura optimală există |
Program recapitulativ: maximul prin D&I
#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;
}
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:
Exercițiu de completare: încadrarea problemelor
Completează cu metoda potrivită pentru fiecare algoritm:
Merge sort este o aplicație ______; restul cu monede este o aplicație ______; căutarea binară este o aplicație ______; problema spectacolelor este o aplicație ______.
Bancă de cuvinte:
Test de înțelegere
Test final - recapitulare:
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 sortării prin interclasare este:
st == dr la sume și maxime, st > dr la căutări; la test aceste detalii sunt exact punctele pierdute de mulți elevi.Aprofundare
Cum alegi metoda potrivită la o problemă de bacalaureat? Întreabă-te mai întâi dacă problema se „înjumătățește" natural și are un caz trivial: atunci este aproape sigur Divide et impera (maxim, sumă, merge sort, căutare binară). Dacă problema cere o alegere secvențială a optimului local, fără întoarcere (monede, spectacole, rucsac fracționar), este Greedy. Dacă niciuna nu se potrivește clar, problema poate cere o abordare combinată, cum vei vedea la lecțiile următoare.
Semne care trădează Greedy în enunț: expresii precum „număr minim de monede", „număr maxim de spectacole compatibile", „valoare maximă, obiectele putând fi fracționate" indică aproape întotdeauna Greedy. Semne pentru D&I: „funcție recursivă", „împărțiți intervalul în două", „căutare într-un tablou sortat". Recunoașterea acestor indicii câștigă timp prețios la examen.
Complexități de reținut pentru proba orală: suma și maximul prin D&I rulează în O(n) cu stivă O(log n); merge sort în O(n log n); căutarea binară în O(log n); monedele și spectacolele în O(n) sau O(n) (după sortare); rucsacul fracționar în O(n) cu sortare prin selecție. Un tabel cu aceste valori în caiet te ajută la recapitulare rapidă.
Greșeala clasică de recapitulare: amestecarea convențiilor. La D&I, cazul de bază este st == dr (sau st > dr la căutare); la Greedy nu există caz de bază, ci condiții de oprire (rest 0, capacitate 0, ultimul spectacol atins). Nu transporta automat convențiile unei metode în cealaltă.
Exemplu din viața reală: un arhitect care proiectează o clădire împarte planul în module (D&I), dar alege materialele pas cu pas după cel mai bun raport preț-calitate (Greedy). Cele două metode nu se exclud; ele rezolvă tipuri diferite de subprobleme, iar programele mari le combină natural.
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:
- Definim
maxim(st, dr): caz de bazăst == dr - Împărțim la mijloc și returnăm maximul celor două jumătăți
- 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:
- Definim tabloul
monededescrescător - Pentru fiecare monedă, cât timp încape, o scădem și numărăm
- 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.
Exercițiul Practic: recapitulare finală
Sarcini de lucru
Rezolvă sarcinile de mai jos pentru a încheia recapitularea modulului
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 - Recapitulare: D&I și Greedy
Titlul lecției
- Ora 9: Recapitulare și test
Definiția lecției
Lecția recapitulează cele două metode ale modulului și pregătește testul. Divide et impera descompune problema în subprobleme de același tip, le rezolvă recursiv și combină rezultatele; algoritmii săi sunt suma, maximul, minimul, merge sort și căutarea binară. Greedy construiește soluția pas cu pas, alegând optimul local fără reconsiderare; problemele sale sunt monedele, spectacolele, rucsacul fracționar și platoul. La alegerea metodei contează recunoașterea tipului de problemă: dacă se înjumătățește un interval, este D&I; dacă se alege pas cu pas cea mai bună variantă, este Greedy. Se rețin și complexitățile: D&I de regulă O(n) sau O(log n), merge sort O(n log n), Greedy de regulă O(n) sau O(n log n) cu sortare. Tabelul rezumativ D&I vs Greedy este materialul de repetat înaintea testului.
Definiții esențiale
- Divide et impera: descompunere în subprobleme de același tip → rezolvare recursivă (caz de bază rezolvat direct) → combinare. Exemple: sumă, maxim, merge sort, căutare binară.
- Greedy: construirea soluției pas cu pas, alegând optimul local, fără reconsiderare. Exemple: monede, spectacole, rucsac fracționar, platou.
- Substructură optimală: condiția care garantează că alegerile locale greedy conduc la optimul global.
- Complexități cheie: D&I liniar sau logaritmic (după problemă), merge sort
O(n log n); Greedy de regulăO(n)sauO(n log n)cu sortare.
Algoritmul cheie - pseudocod
- Schema D&I:
dacă st == dr → caz de bază; altfelmij, apeluri recursive, combinare. - Schema Greedy: sortare după criteriul local (dacă e cazul), apoi o buclă de alegeri cu condiții de oprire (rest 0, capacitate 0, interval gol).
Algoritmul cheie - cod C++
maxim(st, dr): caz de bazăv[st], divizare, compararea rezultatelorașib.mergeSort+interclaseazacu vector auxiliartemp.- Monede: buclă peste tabloul descrescător cu
while (n >= monede[i]). - Spectacole: sortare după
sfarsit, numărare cuinceput[i] >= ultimul. - Rucsac fracționar: sortare după eficiență și fracțiune cu
1.0.
Greșeli comune de evitat
- Aplicarea Greedy la probleme fără substructură optimală (exemplu: monede 1, 3, 4).
- Confundarea cazului de bază D&I (
st == dr) cu cel al căutării binare (st > dr). - Reconsiderarea deciziilor în Greedy sau re-parcurgerea subproblemelor în D&I.
- Uitarea condiției de oprire din buclele greedy (restul 0, capacitatea 0).
Sfaturi practice și trucuri
- Fă un tabel de sinteză cu cele patru algoritmi principali și criteriile lor; ține-l la îndemână la recapitulare.
- Pentru fiecare problemă de antrenament, numește întâi metoda și justificarea, apoi scrie codul.
- Testează mereu cazurile limită: vector cu un element, n = 1, rest 0, capacitate mai mare decât suma greutăților.
- La examen, recitirea enunțului și încadrarea metodei înainte de codare îți garantează punctajul la algoritmică.
Exemplu practic
Înaintea testului, un elev rezolvă o problemă de antrenament: găsește numărul maxim dintr-un tablou de n note, alegând metoda D&I. Răspunsul este dat de funcția recursivă de mai jos, cu tabloul global v; pentru exemplul v = [4, 9, 2, 7], rezultatul este 9:
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;
}