Test inițial · Clasa a XI-a

Text: caractere, cuvinte, ștergeri

M05 · <cstring>2 p

Se citește de la tastatură un text de cel mult 255 de caractere, format din cuvinte separate prin câte un spațiu. Se folosesc șiruri în stil C (char s[256]).

Exemplus = "azi avem test la informatica"

a) 11 vocale
b) cel mai lung cuvânt: informatica
c) după ștergerea literei 'a': "zi vem test l informtic"

a)Afișează numărul de vocale din text (indiferent de literă mare sau mică).0,5 p

b)Afișează cel mai lung cuvânt din text. Dacă sunt mai multe de lungime maximă, afișează-l pe primul.0,75 p

c)Elimină din text toate aparițiile literei 'a' și afișează rezultatul.0,75 p

Barem de corectare & rezolvare

a) 0,5 p

Citirea se face cu cin.getline — cin >> s s-ar opri la primul spațiu. Testul de vocală se scrie elegant cu strchr.

C++

#include <iostream>
#include <cstring>
#include <cctype>
using namespace std;

char s[256];

int main() {
    cin.getline(s, 256);          // ia toata linia, cu spatii

    int nv = 0;
    for (int i = 0; s[i]; i++) {
        char c = tolower(s[i]);
        if (strchr("aeiou", c)) nv++;
    }
    cout << nv << '\n';
    return 0;
}

b) 0,75 p

strtok este funcția-vedetă de la BAC. Atenție la două capcane de barem: primul apel primește șirul, iar următoarele primesc NULL; și strtok modifică șirul, punând \0 în locul separatorilor — de aceea se lucrează pe o copie.

C++

char copie[256], maxc[256] = "";
strcpy(copie, s);                     // strtok distruge sirul -> copie

char *p = strtok(copie, " ");
while (p != NULL) {
    if (strlen(p) > strlen(maxc)) strcpy(maxc, p);
    p = strtok(NULL, " ");            // apelurile urmatoare: NULL
}
cout << maxc << '\n';

c) 0,75 p

Trucul suprem al șirurilor: strcpy(s + i, s + i + 1) mută toată coada cu o poziție la stânga, peste caracterul de șters.
Capcana de barem: după o ștergere indicele i NU trebuie mărit — pe poziția i a venit un caracter nou, care poate fi tot 'a' (ex.: "baaba").

C++

int i = 0;
while (s[i]) {
    if (s[i] == 'a')
        strcpy(s + i, s + i + 1);   // suprascriu cu ce urmeaza; i RAMANE
    else
        i++;
}
cout << s << '\n';

Matrice pătratică

M06 · M06a2 p

Se citește un număr natural n (n ≤ 20) și apoi elementele unei matrice pătratice a cu n linii și n coloane, numere întregi. Se folosește indexarea de la 1.

Exemplun = 3
1 2 3
4 5 6
7 8 9

a) diagonala secundară: 3 + 5 + 7 = 15
b) linia cu suma maximă: linia 3, suma 24
c) matricea NU este simetrică (a[1][2] = 2 ≠ 4 = a[2][1])

a)Calculează și afișează suma elementelor de pe diagonala secundară.0,5 p

b)Determină și afișează indicele liniei cu suma elementelor maximă, împreună cu suma respectivă.0,75 p

c)Verifică dacă matricea este simetrică față de diagonala principală și afișează DA sau NU.0,75 p

Barem de corectare & rezolvare

a) 0,5 p

Pe diagonala secundară i + j = n + 1, deci pentru linia i coloana este n + 1 - i. E nevoie de o singură buclă, nu de două.

C++

int n, a[25][25];
cin >> n;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        cin >> a[i][j];

int s = 0;
for (int i = 1; i <= n; i++)
    s += a[i][n + 1 - i];        // diagonala secundara

cout << s << '\n';

b) 0,75 p

Suma pe linie se calculează cu bucla interioară pe coloane. Inițializarea corectă a maximului: cu suma primei linii (nu cu 0 — elementele pot fi negative).

C++

int best = 1, sbest = 0;
for (int j = 1; j <= n; j++) sbest += a[1][j];   // suma liniei 1

for (int i = 2; i <= n; i++) {
    int s = 0;
    for (int j = 1; j <= n; j++) s += a[i][j];
    if (s > sbest) { sbest = s; best = i; }
}
cout << "Linia " << best << ", suma " << sbest << '\n';

c) 0,75 p

Simetrică înseamnă a[i][j] = a[j][i] pentru orice i, j. Este suficient să verifici doar deasupra diagonalei (j > i) — jumătatea de jos e aceeași pereche, verificată de două ori degeaba. Un singur element diferit strică totul, deci se iese imediat din bucle.

C++

bool sim = true;
for (int i = 1; i <= n && sim; i++)
    for (int j = i + 1; j <= n; j++)
        if (a[i][j] != a[j][i]) { sim = false; break; }

cout << (sim ? "DA" : "NU") << '\n';

Recursivitate și divide et impera

M10 · M112 p

Toate subprogramele cerute trebuie scrise recursiv. O soluție iterativă corectă primește cel mult jumătate din punctaj.

a)Scrie funcția recursivă int cmmdc(int a, int b) (algoritmul lui Euclid).0,5 p

b)Scrie subprogramul recursiv void invers(int n) care afișează cifrele lui n în ordine inversă, și int nrCifre(int n) care întoarce numărul de cifre.0,75 p

c)Scrie funcția int maxim(int v[], int st, int dr) care determină, prin divide et impera, maximul dintre elementele v[st..dr].0,75 p

Barem de corectare & rezolvare

a) 0,5 p

Cazul de bază: b == 0 → răspunsul este a. Cazul general apelează funcția cu (b, a % b) — restul scade strict, deci se ajunge sigur la 0.

C++

int cmmdc(int a, int b) {
    if (b == 0) return a;          // cazul de baza
    return cmmdc(b, a % b);        // progres garantat: a % b < b
}

// cmmdc(12, 8) -> cmmdc(8, 4) -> cmmdc(4, 0) -> 4

b) 0,75 p

Diferența de aur: dacă afișezi înainte de apelul recursiv, cifrele ies în ordine inversă; dacă afișezi după, ies în ordine normală. Capcana: pentru n = 0 funcția invers nu afișează nimic — se tratează separat în main.

C++

void invers(int n) {
    if (n == 0) return;
    cout << n % 10;        // AFISEZ intai  -> ordine inversa
    invers(n / 10);
}

int nrCifre(int n) {
    if (n < 10) return 1;
    return 1 + nrCifre(n / 10);
}

// invers(1234) afiseaza 4321 ; nrCifre(1234) = 4
// atentie: pentru n = 0 se afiseaza separat cifra 0

c) 0,75 p

Cele trei etape se văd direct în cod: DIVIDE (mijlocul), STĂPÂNEȘTE (două apeluri pe jumătăți), COMBINĂ (maximul celor două rezultate). Apelul din main este maxim(v, 0, n - 1).

C++

int maxim(int v[], int st, int dr) {
    if (st == dr) return v[st];             // cazul de baza: un element

    int m = (st + dr) / 2;                  // DIVIDE
    int a = maxim(v, st, m);                // STAPANESTE (stanga)
    int b = maxim(v, m + 1, dr);            // STAPANESTE (dreapta)

    return (a > b) ? a : b;                 // COMBINA
}

// apel: cout << maxim(v, 0, n - 1);

Greedy și interclasare

M12 · M022 p

Două tehnici clasice și o întrebare de raționament despre limitele metodei Greedy.

Exemplua) S = 87 → 1×50, 3×10, 1×5, 2×1 = 7 monede
b) a = 1 4 7 9, b = 2 3 8 → c = 1 2 3 4 7 8 9

a)Se dispune de monede de 50, 10, 5 și 1 leu, în număr nelimitat. Scrie programul care plătește o sumă S cu număr minim de monede, afișând câte monede de fiecare fel se folosesc.0,75 p

b)Se dau doi vectori a (n elemente) și b (m elemente), fiecare deja sortat crescător. Interclasează-i într-un vector c, sortat crescător, fără să sortezi la final.0,75 p

c)Se schimbă sistemul de monede în 1, 3 și 4 lei, iar restul de plătit este 6 lei. Ce răspuns dă algoritmul Greedy de la a)? Care este soluția optimă? Ce concluzie tragi?0,5 p

Barem de corectare & rezolvare

a) 0,75 p

Alegerea lacomă: iei mereu cât mai multe monede din cea mai mare valoare disponibilă. S / mon[i] dă numărul de monede, S %= mon[i] lasă restul de plătit.

C++

int mon[4] = {50, 10, 5, 1};       // OBLIGATORIU descrescator
int S, total = 0;
cin >> S;

for (int i = 0; i < 4; i++) {
    int k = S / mon[i];            // alegerea lacoma
    if (k > 0) cout << k << " x " << mon[i] << '\n';
    total += k;
    S %= mon[i];                   // ce ramane de platit
}
cout << "Total monede: " << total << '\n';

b) 0,75 p

Doi indicatori pornesc de la începutul vectorilor și coboară de fiecare dată minimul. Capcana de barem: cele două bucle de la final, care golesc vectorul rămas — fără ele se pierd elemente. Complexitatea este O(n + m), față de O((n+m)log(n+m)) dacă ai fi sortat.

C++

int i = 0, j = 0, k = 0;

while (i < n && j < m)
    if (a[i] <= b[j]) c[k++] = a[i++];
    else              c[k++] = b[j++];

while (i < n) c[k++] = a[i++];     // ce a ramas din a
while (j < m) c[k++] = b[j++];     // ce a ramas din b

for (int t = 0; t < k; t++) cout << c[t] << ' ';

c) 0,5 p

Greedy alege lacom: 4 + 1 + 1 → 3 monede.
Optimul este 3 + 3 → 2 monede.
Concluzia: Greedy nu este corect pentru orice sistem de monede — el garantează optimul doar dacă sistemul are proprietatea potrivită (cum au 50/10/5/1 sau monedele reale). Pentru cazul general este nevoie de programare dinamică, exact ce se învață anul acesta.

Test inițial — Clasa a XI-a

Recapitulare — bagajul minim

Recursivitate

Matrice (tablou 2D)

Subprograme

Vectori și parcurgeri

Stivă și coadă

Căutare binară

Divide et impera

Greedy

Șiruri de caractere

Adrese și pointeri

Subiectul I — grilă

Subiectul II — probleme

Text: caractere, cuvinte, ștergeri

Barem de corectare & rezolvare

Matrice pătratică

Barem de corectare & rezolvare

Recursivitate și divide et impera

Barem de corectare & rezolvare

Greedy și interclasare

Barem de corectare & rezolvare

Nota ta