Ce vei învăța astăzi?
După această lecție vei cunoaște structura exactă a evaluării finale, vei înțelege cum se punctează fiecare cerință și vei rezolva probleme model de căutare binară și interclasare, exact ca la test.
Structura evaluării finale a modulului
Definiție: Evaluarea finală verifică toate competențele modulului 3: matricea și prelucrările ei, căutarea binară, interclasarea și fuzionarea. Lucrarea are două subiecte: teorie (30 de puncte) și rezolvare de probleme (70 de puncte), conform baremului anunțat la începutul modulului.
| Subiect | Conținut | Punctaj | Ce se verifică |
|---|---|---|---|
| Subiectul I - Teorie | 5 întrebări: definiții, condiții de aplicare (situațiile în care un algoritm poate fi folosit corect), complexități | 30p (6p fiecare) | cunoștințe de bază, terminologie |
| Subiectul II - Problema 1 | matrice: parcurgere, diagonale, prelucrări | 35p | citire, parcurgere, prelucrare corectă |
| Subiectul II - Problema 2 | căutare binară sau interclasare pe liste sortate | 35p | algoritm corect, eficiență, cazuri limită (datele extreme, de exemplu n = 1 sau o valoare care nu există) |
Observă: la Subiectul II, jumătate din punctaj se acordă pentru ideea algoritmului și pentru corectitudinea logică, nu doar pentru sintaxa C++. Chiar dacă un program nu compilează perfect, pașii corecti aduc puncte.
Baremul de corectare - cum se acordă punctele
Pentru fiecare problemă de la Subiectul II, punctajul se împarte astfel: citirea corectă a datelor, structura algoritmică (bucle, condiții, inițializări), prelucrarea cerută și afișarea rezultatului în formatul exact din enunț. Greșelile mici de sintaxă se penalizează puțin, dar greșelile de logică (condiție inversată, inițializare greșită) taie puncte substanțiale.
Analogia: pregătirea pentru un examen de șah
Un jucător de șah nu învață mutările pe de rost, ci planurile: deschiderea (citirea datelor), mijlocul de joc (prelucrarea) și finalul (afișarea). La fel, la evaluare nu contează doar să știi codul, ci să recunoști tipul problemei și să alegi algoritmul potrivit: matrice pentru tabele, căutare binară pentru listă sortată cu căutare, interclasare pentru două liste sortate.
Exemplu de punctaj pentru o problemă de interclasare:
- Citirea celor două șiruri sortate - 5 puncte
- Inițializarea corectă a indicilor (
i = 1,j = 1,k = 0) - 5 puncte - Bucla principală cu alegerea minimului - 10 puncte
- Copierea elementelor rămase (cele două bucle while) - 10 puncte
- Afișarea rezultatului în formatul cerut - 5 puncte
Total: 35 de puncte, exact structura unei probleme de la Subiectul II.
Probleme model pentru evaluare
Cele două probleme model de mai jos au exact nivelul evaluării finale: una de căutare binară și una de interclasare. Rezolvă-le independent, apoi compară cu soluțiile complet comentate pe pași logici.
#include <iostream>
using namespace std;
int main() {
int n, a[100005], x, i, st, dr, mij, poz = 0;
cin >> n;
// pasul 1: citim tabloul sortat crescător
for (i = 1; i <= n; i++)
cin >> a[i];
cin >> x;
// pasul 2: căutarea binară a lui x
st = 1;
dr = n;
while (st <= dr) {
mij = (st + dr) / 2;
if (a[mij] == x) {
poz = mij;
break;
} else if (a[mij] < x) {
st = mij + 1;
} else {
dr = mij - 1;
}
}
// pasul 3: afișăm poziția găsită sau -1
if (poz == 0)
cout << -1;
else
cout << poz;
return 0;
}
#include <iostream>
using namespace std;
int main() {
int n, m, a[100005], b[100005], c[200005], i, j, k;
cin >> n;
// pasul 1: citim prima listă sortată
for (i = 1; i <= n; i++)
cin >> a[i];
cin >> m;
// pasul 2: citim a doua listă sortată
for (j = 1; j <= m; j++)
cin >> b[j];
// pasul 3: interclasăm, alegând mereu elementul mai mic
i = 1;
j = 1;
k = 0;
while (i <= n && j <= m) {
k++;
if (a[i] <= b[j]) {
c[k] = a[i];
i++;
} else {
c[k] = b[j];
j++;
}
}
// pasul 4: copiem elementele rămase
while (i <= n) {
k++;
c[k] = a[i];
i++;
}
while (j <= m) {
k++;
c[k] = b[j];
j++;
}
// pasul 5: afișăm lista rezultat, sortată
for (i = 1; i <= k; i++)
cout << c[i] << " ";
return 0;
}
Observă: ambele programe au aceeași „anatomie" (structura de bază, comună tuturor programelor): citire, algoritm, afișare. La evaluare, scrie întâi structura completă pe hârtie (inclusiv #include și using namespace std;), apoi completezi pașii.
Exercițiu de completare
Completează enunțul cu cuvintele potrivite:
Evaluarea finală are două subiecte: teorie cu ______ și rezolvare de probleme cu ______ de puncte. Căutarea binară are complexitatea ______.
Bancă de cuvinte:
Exercițiu de completare 2
Completează afirmațiile despre barem:
La interclasare, indicii se inițializează cu ______. După ce o listă se epuizează, copiem elementele ______ din cealaltă. La căutarea binară, condiția buclei este ______.
Bancă de cuvinte:
Test de înțelegere
Test rapid - evaluarea finală:
1. La Subiectul II, punctajul unei probleme de interclasare se acordă în principal pentru:
2. Dacă nu respectăm condiția st <= dr la căutarea binară:
3. La interclasare, după epuizarea unei liste:
Aprofundare
Cum te pregătești eficient pentru evaluarea finală? Rezolvă cel puțin o problemă din fiecare tip: matrice simplă, diagonale, maxim cu poziție, căutare binară clasică, prima și ultima apariție, interclasare, fuzionare. Pentru fiecare, scrie complexitatea și condiția de aplicare în dreptul algoritmului - exact ce se cere la subiectele de teorie și la justificările de la probleme.
Tehnica „testului alb" - simularea pe hârtie: înainte de evaluare, ia un exemplu mic (de exemplu, liste cu 3-4 elemente) și rulează algoritmul cu creionul, urmărind valorile lui i, j, k, st, dr, mij. Această tehnică descoperă majoritatea greșelilor de logică înainte de a scrie codul, iar profesorii o recomandă pentru orice problemă nouă.
Greșelile care costă cel mai mult puncte la evaluare:
- Inițializarea greșită a sumelor și contoarelor (suma cu 1, contorul cu 1 în loc de 0).
- Confuzia între interclasare și fuzionare: enunțul spune „distincte"? atunci fuzionare.
- Uitarea afișării cu spații și a
endl-urilor cerute de formatul de ieșire. - Declararea tablourilor fără loc în plus pentru indexarea de la 1.
După ce termini o problemă, verifică cele trei cazuri de aur: datele minime (n = 1), datele maxime (restricțiile din enunț) și un caz în care rezultatul este „absent" (valoare care nu există, listă fără elemente mai mici decât x). Un program care funcționează pe aceste trei cazuri are toate șansele să ia punctaj maxim.
PbInfo - Model evaluare: căutarea ultimei apariții
Enunț:
Cerință: Se dă un tablou cu n numere naturale, sortat crescător, și o valoare x. Să se afișeze poziția ultimei apariții a lui x în tablou sau -1 dacă valoarea nu există.
Date de intrare:
Programul citește de la tastatură numărul n, apoi cele n valori sortate, apoi valoarea x.
Date de ieșire:
Programul va afișa poziția ultimei apariții a lui x (numerotată de la 1) sau -1.
Restricții și precizări:
1 <= n <= 100000, valorile sunt numere naturale sortate crescător.
Exemplu:
Intrare:
7 2 4 6 6 6 8 10 6
Ieșire:
5
Cum gândim soluția:
- Căutăm ultima poziție cu
a[poz] <= x - Când găsim un element egal cu
x, continuăm spre dreapta (st = mij + 1) - Verificăm dacă pe poziția reținută există chiar
x - Afișăm poziția sau
-1
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
int main() {
int n, a[100005], x, i, st, dr, mij, poz = 0;
cin >> n;
for (i = 1; i <= n; i++)
cin >> a[i];
cin >> x;
st = 1;
dr = n;
while (st <= dr) {
mij = (st + dr) / 2;
if (a[mij] <= x) {
poz = mij;
st = mij + 1;
} else {
dr = mij - 1;
}
}
if (poz != 0 && a[poz] == x)
cout << poz;
else
cout << -1;
return 0;
}
Ce învățăm: pentru ultima apariție folosim condiția <= și continuăm spre dreapta cu st = mij + 1 - imaginea în oglindă a primei apariții.
PbInfo - Model evaluare: interclasare cu numărare
Enunț:
Cerință: Se dau două șiruri de numere naturale, fiecare sortat crescător. Să se afișeze câte elemente are interclasarea celor două șiruri fără a păstra dublurile (numărul de valori distincte).
Date de intrare:
Programul citește de la tastatură numărul n, apoi cele n valori ale primului șir, numărul m, apoi cele m valori ale celui de-al doilea șir.
Date de ieșire:
Programul va afișa un singur număr: câte valori distincte apar în reuniunea celor două șiruri.
Restricții și precizări:
1 <= n, m <= 100000, valorile sunt numere naturale.
Exemplu:
Intrare:
4 1 2 2 5 3 2 3 4
Ieșire:
5
Cum gândim soluția:
- Fuzionăm cele două șiruri, numărând doar valorile distincte
- Când
a[i] == b[j], numărăm o dată și avansăm ambii indici - Când valorile diferă, numărăm valoarea mai mică
- Copiem restul din șirul neepuizat, numărând fiecare valoare
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
int main() {
int n, m, a[100005], b[100005], i, j, k = 0;
cin >> n;
for (i = 1; i <= n; i++)
cin >> a[i];
cin >> m;
for (j = 1; j <= m; j++)
cin >> b[j];
i = 1;
j = 1;
while (i <= n && j <= m) {
if (a[i] == b[j]) {
k++;
i++;
j++;
} else if (a[i] < b[j]) {
k++;
i++;
} else {
k++;
j++;
}
}
while (i <= n) {
k++;
i++;
}
while (j <= m) {
k++;
j++;
}
cout << k;
return 0;
}
Ce învățăm: numărăm valorile distincte fără a construi tabloul rezultat - fiecare „copiere" din fuzionare devine un simplu k++, economisind memorie.
Exercițiul Practic: Antrenament pentru evaluarea finală
Sarcini de lucru
Rezolvă cele două sarcini de antrenament, în condiții de evaluare
Sarcina 1: Suma elementelor sub diagonala principală
Cerință: Scrie un program C++ care citește o matrice pătrată cu n linii și coloane și afișează suma elementelor situate sub diagonala principală (i > j).
Soluție pentru Sarcina 1:
#include <iostream>
using namespace std;
int main() {
int n, a[101][101], i, j, s = 0;
cin >> n;
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
cin >> a[i][j];
for (i = 1; i <= n; i++)
for (j = 1; j < i; j++)
s = s + a[i][j];
cout << s;
return 0;
}
Verifică: sub diagonală, coloana j este mai mică decât linia i; parcurgem direct j de la 1 la i - 1, fără if.
Sarcina 2: Câte elemente din a sunt mai mari decât x
Cerință: Scrie un program C++ care citește un tablou sortat crescător cu n elemente și o valoare x, apoi afișează câte elemente sunt strict mai mari decât x, folosind căutarea binară.
Soluție pentru Sarcina 2:
#include <iostream>
using namespace std;
int main() {
int n, a[100005], x, i, st, dr, mij, poz;
cin >> n;
for (i = 1; i <= n; i++)
cin >> a[i];
cin >> x;
st = 1;
dr = n;
poz = n + 1;
while (st <= dr) {
mij = (st + dr) / 2;
if (a[mij] > x) {
poz = mij;
dr = mij - 1;
} else {
st = mij + 1;
}
}
cout << n - poz + 1;
return 0;
}
Verifică: prima poziție cu valoare > x marchează începutul zonei căutate; numărul de elemente mai mari este n - poz + 1.
Scrie pe caiet - De reținut
Titlul lecției
Ora 12: Evaluare finală a modulului
Definiția lecției
Evaluarea finală verifică toate competențele modulului 3 și are două subiecte: Subiectul I de teorie, cu 5 întrebări despre definiții, condiții de aplicare și complexități (30 de puncte), și Subiectul II, cu două probleme de rezolvat în C++ (70 de puncte), una de matrice și una de căutare binară sau interclasare. Punctajul problemelor se acordă pe pași logici: citirea datelor, inițializările, structura algoritmică, copierea restului și afișarea rezultatului. Greșelile de logică, precum condițiile inversate sau inițializările greșite, taie mult mai mult din punctaj decât micile greșeli de sintaxă. Complexitățile de reținut: căutarea binară, O(log2 n), interclasarea și fuzionarea, O(n + m). Înainte de evaluare, exersează câte o problemă din fiecare tip și verifică cele trei cazuri de aur: date minime, date maxime și rezultat absent.
Definiții esențiale
- Evaluarea finală: Subiectul I - teorie (5 întrebări, 30p), Subiectul II - două probleme C++ (70p: matrice, căutare binară/interclasare).
- Punctajul problemelor se acordă pe pași: citire, inițializări, algoritm, copierea restului, afișare.
- Căutarea binară:
O(log2 n); interclasarea:O(n + m); fuzionarea elimină dublurile. - Verifică întotdeauna cazurile limită: date minime, date maxime, valoare inexistentă.
Algoritmul cheie - pseudocod
Algoritmul cheie - cod C++
st = 1;
dr = n;
poz = 0;
while (st <= dr) {
mij = (st + dr) / 2;
if (a[mij] == x) {
poz = mij;
break;
} else if (a[mij] < x) {
st = mij + 1;
} else {
dr = mij - 1;
}
}
if (poz == 0)
cout << -1;
else
cout << poz;
Greșeli comune de evitare
- Condiția
st < drîn loc dest <= dr: ultimul element nu mai este verificat. - Inițializarea greșită a contoarelor și sumelor: suma cu 0, contorul cu 0, maximul cu
a[1][1]. - Uitarea copierii restului la interclasare: elementele din lista neepuizată dispar.
Exemplu practic
La evaluarea finală, o problemă tipică de interclasare cere unirea a două liste sortate de numere de ordine ale elevilor, cu menținerea ordinii. Programul de mai jos este soluția model, exact la nivelul cerut la Subiectul II: citire, interclasare cu alegerea minimului, copierea restului și afișare.
#include <iostream>
using namespace std;
int main() {
int n, m, a[100005], b[100005], c[200005], i, j, k;
cin >> n;
for (i = 1; i <= n; i++)
cin >> a[i];
cin >> m;
for (j = 1; j <= m; j++)
cin >> b[j];
i = 1; j = 1; k = 0;
while (i <= n && j <= m) {
k++;
if (a[i] <= b[j]) { c[k] = a[i]; i++; }
else { c[k] = b[j]; j++; }
}
while (i <= n) { k++; c[k] = a[i]; i++; }
while (j <= m) { k++; c[k] = b[j]; j++; }
for (i = 1; i <= k; i++)
cout << c[i] << " ";
return 0;
}
Pentru listele 1 3 5 7 și 2 4 6, programul afișează 1 2 3 4 5 6 7, primind la barem puncte pentru fiecare pas logic corect: citire, bucla principală, copierea restului și afișarea.
Sfaturi practice și trucuri
- Scrie întotdeauna structura completă a programului, cu
#includeșiusing namespace std;. - Împarte punctajul pe pași și verifică fiecare pas pe un exemplu mic.
- La final, verifică cele trei cazuri de aur: minim, maxim, rezultat absent.