Ce vei învăța astăzi?
După această lecție vei cunoaște structura exactă a evaluării finale a modulului și vei rezolva probleme model de tip Subiectul I și Subiectul II, identice ca format cu cele de la test.
Structura evaluării finale a modulului
Definiție: Evaluarea finală a Modulului 4 verifică toate competențele (abilitățile și cunoștințele cerute de programă) dobândite în cele 14 ore și are două subiecte. Subiectul I conține 5 întrebări de teorie (definiții, complexități, scheme de algoritmi), notate cu câte 6 puncte, în total 30 de puncte. Subiectul II conține 2 probleme de programare în C++, notate cu câte 35 de puncte, în total 70 de puncte. Nota finală se calculează împărțind punctajul total la 10.
| Subiect | Conținut | Punctaj |
|---|---|---|
| Subiectul I | 5 întrebări de teorie: definiții, cazuri de bază, complexități, criterii greedy | 30p (5 × 6p) |
| Subiectul II, problema 1 | problemă rezolvată cu Divide et impera (sumă, maxim, merge sort, căutare binară) | 35p |
| Subiectul II, problema 2 | problemă rezolvată cu Greedy (monede, spectacole, rucsac fracționar, platou) | 35p |
Analogie: proba de atletism
O probă combinată de atletism are mai multe discipline: o probă de viteză (Subiectul I, întrebări scurte), o probă de rezistență (problema D&I) și o probă de tehnică (problema Greedy). Punctajul se adună, iar medalia (nota) depinde de suma totală. Un sportiv bun știe exact ce se cere la fiecare disciplină și se antrenează specific pentru fiecare.
Problemă model Subiectul II: Divide et impera
Cerință model: Se citește n și apoi n numere întregi. Să se determine și să se afișeze valoarea maximă și valoarea minimă, folosind două funcții recursive de tip Divide et impera. Funcțiile se definesc înainte de main(), iar tabloul este global.
#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 minim(int st, int dr) {
if (st == dr) {
return v[st];
}
int mij = (st + dr) / 2;
int a = minim(st, mij);
int b = minim(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) << " " << minim(1, n) << endl;
return 0;
}
Ce învățăm: această problemă acoperă punctele de lucru ale baremului: definirea corectă a funcțiilor, cazul de bază, divizarea la mijloc, reținerea rezultatelor în variabile și combinarea prin comparație.
Problemă model Subiectul II: Greedy
Cerință model: Se citește 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, prin metoda Greedy (sistemul de monede este canonic).
#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: baremul punctează: tabloul descrescător, bucla while (nu if!), scăderea din sumă, numărarea și afișarea. Pentru S = 88, răspunsul este 7 monede.
main(), lipsa #include, variabile nedeclarate; verifică programul înainte de predare, pentru că o eroare de compilare anulează tot punctajul problemei.Aprofundare
Cum se punctează la Subiectul II: punctajul nu se acordă doar pentru programul final. Se punctează pe etape: înțelegerea enunțului (date de intrare, date de ieșire), alegerea metodei potrivite, pseudocodul sau descrierea algoritmului, implementarea corectă a fiecărei funcții și testarea pe exemplul dat. Scrie mereu și etapele, nu doar codul.
Tehnica de lucru în timpul evaluării: citește ambele probleme înainte de a începe; rezolvă întâi problema pe care o știi mai bine; pentru fiecare problemă, scrie mai întâi schema (metoda, structura funcțiilor, cazurile de bază), apoi completează codul; verifică la final programul pe exemplul din enunț, rulându-l mental.
Subiectul I, teme tipice: definește metoda Divide et impera și etapele ei; scrie cazul de bază pentru suma, maxim, căutare binară; dă complexitatea merge sort și a căutării binare; definește optimul local și substructura optimală; numește criteriul greedy pentru monede, spectacole, rucsac; explică de ce Greedy nu reconsideră deciziile; compară cele două metode.
Greșelile care costă puncte: program care nu compilează (funcții definite după main(), lipsa #include); cazuri de bază greșite; afișarea rezultatului fără verificarea pe exemplu; uitarea long long la probleme cu valori mari; criteriu greedy greșit la spectacole (sortare după început).
Exemplu din viața reală: evaluarea finală seamănă cu pregătirea unui șofer pentru examenul de conducere: înainte de proba propriu-zisă, șoferul repetă manevrele standard (parcare, mers înapoi), exact cum tu repeți algoritmii standard ai modulului. La examen, manevrele sunt aceleași, doar contextul se schimbă puțin.
Exercițiu de completare
Completează enunțul despre evaluarea finală:
Evaluarea finală are două subiecte. ______ conține 5 întrebări de teorie, în total 30 de puncte. ______ conține două probleme de programare, în total 70 de puncte. Problema 1 se rezolvă cu metoda Divide et ______, iar problema 2 cu metoda ______. Nota finală se obține împărțind punctajul total la ______.
Bancă de cuvinte:
Exercițiu de completare: pregătirea pentru Subiectul II
Completează cu pașii de lucru corecți:
Înainte de a scrie codul, ______ ambele probleme și identifică ______ potrivită. Scrie mai întâi ______ algoritmului: funcțiile și cazurile de ______. La final, verifică programul ______ pe exemplul din enunț.
Bancă de cuvinte:
Test de înțelegere
Test rapid - evaluarea finală:
1. Punctajul Subiectului I este:
2. La Subiectul II, problema 1 se rezolvă cu:
3. Nota finală se calculează:
Model Subiectul II - Problema 1: Suma parelor prin D&I
Enunț:
Cerință: Se citește n și apoi n numere naturale. Să se afișeze suma elementelor pare ale vectorului, calculată 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 suma elementelor pare.
Restricții și precizări:
1 ≤ n ≤ 1000; elementele sunt numere naturale mai mici decât 1000; suma poate depăși 2 miliarde, deci se folosește long long.
Exemplu:
Intrare:
6 1 4 2 7 8 3
Ieșire:
14
Cum gândim soluția:
- Cazul de bază: st == dr; returnăm v[st] dacă este par, altfel 0
- Divizăm la mijloc și adunăm rezultatele jumătăților
- Afișăm suma ca long long
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
int v[1001];
long long sumaPare(int st, int dr) {
if (st == dr) {
if (v[st] % 2 == 0) {
return v[st];
}
return 0;
}
int mij = (st + dr) / 2;
return sumaPare(st, mij) + sumaPare(mij + 1, dr);
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> v[i];
}
cout << sumaPare(1, n) << endl;
return 0;
}
Ce învățăm: pentru exemplul dat, elementele pare sunt 4, 2 și 8, iar suma lor este 14. La cazul de bază, elementul „votează" cu valoarea lui dacă este par și cu 0 altfel.
Model Subiectul II - Problema 2: Spectacolele (Greedy)
Enunț:
Cerință: Se citesc n spectacole, fiecare cu ora de început și ora de sfârșit. Să se afișeze numărul maxim de spectacole care pot fi văzute într-o singură sală, astfel încât niciun spectacol să nu se suprapună cu altul (metoda Greedy).
Date de intrare:
Programul citește n, apoi n perechi început sfârșit.
Date de ieșire:
Programul va afișa numărul maxim de spectacole.
Restricții și precizări:
1 ≤ n ≤ 100; 1 ≤ început < sfârșit ≤ 1440; se folosește metoda Greedy, cu sortare după ora de sfârșit.
Exemplu:
Intrare:
4 1 3 2 5 4 6 6 8
Ieșire:
3
Cum gândim soluția:
- Sortăm spectacolele crescător după sfârșit, mutând împreună începuturile
- Alegem primul spectacol și numărăm; apoi fiecare spectacol cu început >= ultimul sfârșit
- Afișăm numărul total
Scrie soluția în C++:
Soluție corectă:
#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;
}
Ce învățăm: pentru exemplul dat, spectacolele alese sunt (1,3), (4,6), (6,8), deci 3 spectacole. Baremul punctează sortarea perechilor (nu doar a sfârșiturilor), inițializarea și condiția de compatibilitate.
Exercițiul Practic: simulare de evaluare finală
Sarcini de lucru
Rezolvă sarcinile de mai jos în formatul exact al Subiectului II, pentru a te pregăti pentru evaluare
Sarcina 1: Subiectul II - problema D&I
Cerință: Scrie programul C++ complet pentru problema: se citesc n și n numere întregi; să se afișeze numărul de elemente negative, calculat cu o funcție recursivă de tip Divide et impera. Scrie mai întâi schema algoritmului pe hârtie, apoi codul.
Soluție pentru Sarcina 1:
#include <iostream>
using namespace std;
int v[1001];
int nrNegative(int st, int dr) {
if (st == dr) {
if (v[st] < 0) {
return 1;
} else {
return 0;
}
}
int mij = (st + dr) / 2;
return nrNegative(st, mij) + nrNegative(mij + 1, dr);
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> v[i];
}
cout << nrNegative(1, n) << endl;
return 0;
}
Verifică: pentru n = 5 și valorile -2 4 -6 8 -1, rezultatul este 3. La cazul de bază, fiecare element „votează" 1 dacă este negativ și 0 altfel; combinarea este o simplă adunare.
Sarcina 2: Subiectul II - problema Greedy
Cerință: Scrie programul C++ complet pentru problema: se citesc n obiecte (valoare, greutate) și capacitatea g; să se afișeze valoarea maximă încărcată, cu două zecimale, folosind metoda Greedy (rucsac fracționar). Alege sortarea cu care te simți sigur la evaluare.
Soluție pentru Sarcina 2:
#include <iostream>
#include <iomanip>
using namespace std;
int valoare[101], greutate[101];
void sorteaza(int n) {
for (int i = 1; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
if (valoare[i] * greutate[j] < valoare[j] * greutate[i]) {
int aux = valoare[i];
valoare[i] = valoare[j];
valoare[j] = aux;
aux = greutate[i];
greutate[i] = greutate[j];
greutate[j] = aux;
}
}
}
}
int main() {
int n, g;
cin >> n >> g;
for (int i = 1; i <= n; i++) {
cin >> valoare[i] >> greutate[i];
}
sorteaza(n);
double castig = 0;
for (int i = 1; i <= n && g > 0; i++) {
if (greutate[i] <= g) {
castig += valoare[i];
g -= greutate[i];
} else {
castig += valoare[i] * 1.0 * g / greutate[i];
g = 0;
}
}
cout << fixed << setprecision(2) << castig << endl;
return 0;
}
Verifică: pentru n = 3, g = 10 și obiectele (60,10), (100,20), (120,30), câștigul este 240.00. Sortarea prin selecție este suficientă pentru n ≤ 100 și este cea mai sigură de scris din memorie la evaluare.
Scrie pe caiet - Evaluare finală a modulului
Titlul lecției
- Ora 14: Evaluare finală a modulului
Definiția lecției
Evaluarea finală a modulului 4 are două subiecte: Subiectul I, cu 5 întrebări de teorie (definiții, cazuri de bază, complexități, criterii greedy), notate cu 5 × 6 = 30 de puncte, și Subiectul II, cu două probleme de programare C++ (una de Divide et impera, una de Greedy), notate cu 2 × 35 = 70 de puncte. Nota finală se obține împărțind punctajul total la 10. Baremul acordă puncte pe etape: înțelegerea enunțului, metoda aleasă, funcțiile scrise corect și testarea pe exemplu, deci și schema algoritmului contează, nu doar programul final. Înainte de evaluare se reiau din memorie programele principale: maxim, merge sort, monede, spectacole, rucsac fracționar.
Definiții esențiale
- Subiectul I: 5 întrebări de teorie, câte 6 puncte, total 30 de puncte: definiții, cazuri de bază, complexități, criterii greedy.
- Subiectul II: 2 probleme de programare C++, câte 35 de puncte, total 70 de puncte: una de D&I și una de Greedy.
- Nota finală: punctajul total (din 100) împărțit la 10.
- Baremul: puncte pe etape: înțelegerea enunțului, metoda aleasă, funcțiile scrise corect, testarea pe exemplu.
Algoritmul cheie - pseudocod
- Schema D&I pentru Subiectul II: caz de bază, divizare la mijloc, apeluri recursive, combinare.
- Schema Greedy: sortare după criteriul local, buclă de alegeri cu condiții de oprire.
Algoritmul cheie - cod C++
maxim(st, dr)șiminim(st, dr): reține rezultatele înașib, apoi compară.- Monede:
while (n >= monede[i])cu scădere și numărare. - Spectacole: sortare perechi după
sfarsit, condițieinceput[i] >= ultimul. - Rucsac:
valoare[i] * 1.0 * g / greutate[i]pentru fracțiune, afișare cu două zecimale.
Greșeli comune de evitat
- Cod care nu compilează: funcții după
main(), lipsă#includesauusing namespace std;. - Cazuri de bază greșite (
st == drvsst > dr). - Tipuri prea mici:
long longpentru sume și numărări mari. - Nu verifica programul pe exemplul din enunț înainte de a-l considera gata.
Sfaturi practice și trucuri
- Citește ambele probleme înainte de a scrie orice cod; rezolvă întâi cea mai ușoară.
- Scrie schema algoritmului (metoda, funcțiile, cazurile de bază) înainte de codul complet.
- Rularea mentală pe exemplul din enunț prinde cele mai multe greșeli.
- La teorie, răspunsurile scurte și precise valorează mai mult decât cele lungi și vagi; numește întotdeauna complexitățile.
Exemplu practic
La o problemă model de Subiectul II, un elev trebuie să afle maximul unui vector prin Divide et impera. Scrie schema algoritmului (metodă, caz de bază, funcții), apoi codul de mai jos, și îl testează pe exemplul din enunț înainte de a-l considera gata:
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;
}