Invatare Atomica

Greseli frecvente la BAC Informatica si cum sa le eviti

Progres lectie:
0%
🎯

Obiectivul lectiei

Vei invata sa recunosti si sa eviti cele mai frecvente greseli pe care candidatii le fac la Bacalaureat Informatica, pentru a nu pierde puncte din neatentie.

Dupa aceasta lectie vei putea:

  • Sa identifici greseala off-by-one la indexarea vectorilor si sa o corectezi
  • Sa eviti confuzia intre operatorul de atribuire = si cel de comparatie ==
  • Sa distingi impartirea intreaga de cea reala si sa alegi tipul corect
  • Sa eviti algoritmul CMMDC scris gresit (variabila suprascrisa)
  • Sa implementezi corect recursivitatea cu caz de baza obligatoriu
  • Sa resetezi starea in backtracking dupa revenire (EXCLUSIV INTENSIV)

Incearca singur!

Provocare:

Urmatorul cod C++ calculeaza suma elementelor unui vector cu n=5. Gaseste greseala:

int v[5] = {10, 20, 30, 40, 50};
int suma = 0;
for (int i = 1; i <= 5; i++) suma += v[i];
💡 Ai nevoie de un indiciu?

Vectorii in C++ se indexeaza de la 0. Bucla i=1; i<=5 sare peste v[0] si acceseaza v[5] care este in afara tabloului!

Corect: for (int i = 0; i < 5; i++)

1

1. Greseala off-by-one: indexarea vectorilor

Greseala: Accesarea lui v[n] in loc de v[n-1], sau pornirea buclei de la i=1 in loc de i=0.
Consecinta: Undefined behavior — rezultate imprevizibile sau crash la examen.
Cod GRESIT vs CORECT:
// GRESIT: i <= n acceseaza v[n] care e out of bounds!
for (int i = 0; i <= n; i++) suma += v[i];

// CORECT: ultimul indice valid este n-1
for (int i = 0; i < n; i++) suma += v[i];
⚡ EXCLUSIV INTENSIV — Demo C++ compilat si rulat (g++ -std=c++17)
#include <iostream>
using namespace std;
int main() {
    int v[5] = {10, 20, 30, 40, 50};
    int n = 5;
    cout << "v[0]=" << v[0] << " v[n-1]=" << v[n-1] << endl;
    int suma = 0;
    for (int i = 0; i < n; i++) suma += v[i];
    cout << "Suma corecta: " << suma << endl;
    return 0;
}
Output real:
v[0]=10 v[n-1]=50
Suma corecta: 150
Exceptie: vectori cu conventie 1-based

Unele probleme BAC declara int v[101] si folosesc indicii 1..n. In acest caz bucla i=1; i<=n e corecta — dar trebuie sa declari tabloul cu dimensiunea n+1 pentru a evita overflow.

2

2. Confuzia = (atribuire) vs == (comparatie)

Greseala: Scrierea if (x = 5) in loc de if (x == 5).
Consecinta: Atribuie 5 lui x, testeaza daca 5 != 0 (mereu adevarat), si modifica variabila — bug silentios, greu de depistat!
GRESIT vs CORECT:
int x = 3;
// GRESIT: atribuie 5 lui x, testeaza 5!=0 (mereu true!)
if (x = 5) cout << "gresit";

// CORECT: compara x cu 5
if (x == 5) cout << "corect";
⚡ EXCLUSIV INTENSIV — Demo C++ compilat si rulat (g++ -std=c++17)
#include <iostream>
using namespace std;
int main() {
    int x = 5;
    if (x == 5) cout << "x este 5 (comparatie corecta)" << endl;
    return 0;
}
Output real:
x este 5 (comparatie corecta)
Truc de memorare

Un singur egal = pune valoare (atribuie). Doua egale == compara valorile. In orice conditie (if, while, for) vrei aproape intotdeauna ==.

3

3. Impartire intreaga vs impartire reala

Greseala: Cand ambii operanzi sunt int, / face impartire intreaga (trunchiaza), chiar daca rezultatul e stocat intr-un double.
Consecinta: Pierdere de zecimale — greseala clasica la probleme cu medii sau rapoarte.
⚡ EXCLUSIV INTENSIV — Demo C++ compilat si rulat (g++ -std=c++17)
#include <iostream>
using namespace std;
int main() {
    int a = 7, b = 2;
    double rez_gresit = a / b;          // impartire intreaga: 3
    double rez_corect = (double)a / b;  // cast inainte de /: 3.5
    cout << "7/2 int: " << rez_gresit << endl;
    cout << "7/2 real: " << rez_corect << endl;
    return 0;
}
Output real:
7/2 int: 3
7/2 real: 3.5
Regula de aur

Daca vrei impartire reala, castureaza CEL PUTIN UN operand inainte de operatie: (double)a / b sau a / (double)b. Alternativ, declara variabilele ca double de la inceput.

4

4. CMMDC gresit, recursivitate fara caz de baza, terminator sir

Greseala CMMDC: Suprascrierea lui a inainte de a calcula restul — rezultat intotdeauna gresit.
Greseala recursivitate: Omiterea cazului de baza — stack overflow garantat.
Greseala sir: Confuzia '\0' (terminator nul) cu spatiu sau cu un caracter de continut.
⚡ EXCLUSIV INTENSIV — Demo C++ compilat si rulat (g++ -std=c++17)
#include <iostream>
using namespace std;

// CMMDC CORECT: variabila temporara r salveaza restul
// GRESIT ar fi: a=b; b=a%b;  (pierde valoarea originala a lui a)
int cmmdc(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

// Recursivitate CORECTA: cazul de baza este OBLIGATORIU
int factorial(int n) {
    if (n <= 1) return 1;  // fara asta: stack overflow!
    return n * factorial(n - 1);
}

// Sir de caractere: '\0' e terminatorul NUL, nu caracter de continut
void lungime_sir() {
    char s[] = "Hello";
    int lung = 0;
    while (s[lung] != '\0') lung++;
    cout << "Lungime 'Hello': " << lung << endl;
}

int main() {
    cout << "CMMDC(12,8) = " << cmmdc(12, 8) << endl;
    cout << "5! = " << factorial(5) << endl;
    lungime_sir();
    return 0;
}
Output real:
CMMDC(12,8) = 4
5! = 120
Lungime 'Hello': 5
De ce '\0' conteaza

Un sir "Hello" in memorie are 6 bytes: H, e, l, l, o, \0. Numeri pana gasesti \0 si obtii 5 (lungimea corecta). Daca confunzi '\0' cu ' ' (spatiu), bucla continua in memorie nedefinita.

5

5. Overflow la int: numere mari la examen EXCLUSIV INTENSIV

⚡ Sectiune doar pentru intensiv informatica

int pe 32 biti tine maxim 2 147 483 647 (aprox. 2,1 miliarde). Daca produsul sau suma depaseste aceasta limita, apare overflow — un rezultat complet gresit, fara eroare de compilare!

Overflow GRESIT vs CORECT:
int n = 100000;

// GRESIT: n*n = 10^10, depaseste int (max ~2.1*10^9)
int p_gresit = n * n;                    // overflow: valoare incorecta

// CORECT: cast la long long INAINTE de inmultire
long long p_corect = (long long)n * n; // 10000000000
Output demonstrativ (comportament tipic g++, two's complement 32-bit):
n*n long long: 10000000000
n*n int overflow: 1410065408

Nota: overflow pentru int este Undefined Behavior in C++. Valoarea 1410065408 este caracteristica pe sisteme two's complement pe 32 biti: 1010 mod 232 reinterpretat ca signed. Nu te baza pe ea.

Regula practica: Daca n > 40 000 si calculezi n*n, sau n > 1 300 si calculezi n3, foloseste long long cu cast explicit. Complexitate CMMDC: O(log min(a,b)).
6

6. Backtracking: omiterea resetarii starii EXCLUSIV INTENSIV

⚡ Sectiune doar pentru intensiv informatica

Cea mai frecventa greseala la backtracking: dupa apelul recursiv, candidatii uita sa reseteze starea (f[i] = 0). Rezultat: se genereaza mult mai putine solutii decat cele corecte.

Pattern GRESIT vs CORECT:
// GRESIT: lipseste resetarea
for (int i = 1; i <= n; i++) {
    if (!f[i]) {
        v[k] = i; f[i] = 1;
        perm(k + 1);
        // LIPSESTE: f[i] = 0;
    }
}

// CORECT: resetezi starea dupa revenire (backtrack)
for (int i = 1; i <= n; i++) {
    if (!f[i]) {
        v[k] = i; f[i] = 1;
        perm(k + 1);
        f[i] = 0;  // obligatoriu!
    }
}
#include <iostream>
using namespace std;
int v[10], n = 3, f[10] = {0};

void perm(int k) {
    if (k > n) {
        for (int i = 1; i <= n; i++) cout << v[i] << " ";
        cout << "\n";
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!f[i]) {
            v[k] = i; f[i] = 1;
            perm(k + 1);
            f[i] = 0;  // backtrack!
        }
    }
}

int main() {
    cout << "Permutarile {1,2,3}:\n";
    perm(1);
    return 0;
}
Output real (g++ -std=c++17):
Permutarile {1,2,3}:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
Complexitate: Generarea tuturor permutarilor: O(n!). Pentru n=3: 6 solutii. Fara resetarea starii, se genereaza cel mult n solutii in loc de n! solutii.

Exercitii practice

Exercitiul 1 (Nivel minim) — Gaseste greseala

Urmatorul cod calculeaza media aritmetica a doua numere intregi a si b. Ce e gresit?

int a = 5, b = 8;
double medie = a + b / 2;

Raspuns: Doua greseli: (1) din cauza precedentei operatorilor, se calculeaza b/2 inainte (impartire intreaga: 8/2=4), dand 5+4=9.0 in loc de 6.5; (2) niciunul din operanzi nu este castuit la double. Corect: double medie = (double)(a + b) / 2;

Exercitiul 2 (Nivel standard) — Corectare cod CMMDC

Codul de mai jos contine o greseala clasica. Identific-o si scrie varianta corecta:

int cmmdc(int a, int b) {
    while (b != 0) {
        a = b;
        b = a % b;
    }
    return a;
}

Raspuns: a = b distruge valoarea lui a inainte de a % b, deci b = a%b calculeaza de fapt b%b = 0. Corect: int r = a % b; a = b; b = r;

Exercitiul 3 (Nivel performanta) — Analiza completa INTENSIV

Urmatorul cod genereaza combinari C(4,2). Contine 3 greseli. Gaseste-le pe toate:

int v[5], n = 4, k = 2;
void comb(int pos, int start) {
    if (pos = k + 1) {
        for (int i = 1; i <= k; i++) cout << v[i] << " ";
        cout << "\n";
        return;
    }
    for (int i = start; i <= n; i++) {
        v[pos] = i;
        comb(pos + 1, i);
    }
}

Raspuns: (1) if (pos = k+1) trebuie if (pos == k+1) — atribuire vs comparatie; (2) comb(pos+1, i) trebuie comb(pos+1, i+1) — in combinari urmatoarea alegere porneste de la i+1, nu i; (3) lipsesc #include <iostream> si using namespace std; pentru compilare.

Ce ai invatat astazi

  • Off-by-one: vectorii in C++ se indexeaza de la 0, bucla corecta e i < n nu i <= n
  • Atribuire = vs comparatie ==: in conditii foloseste intotdeauna ==
  • Impartire intreaga: pentru rezultat real, castureaza cel putin un operand la double inainte de /
  • CMMDC: salveaza restul intr-o variabila temporara inainte de a suprascrie a
  • Recursivitate: cazul de baza este obligatoriu — fara el programul crapa prin stack overflow
  • Backtracking (INTENSIV): reseteaza intotdeauna starea (f[i] = 0) dupa revenire
  • Overflow (INTENSIV): pentru numere mari (n > 40 000 si calcul n*n), foloseste long long cu cast explicit

Felicitari! Modulul este complet.

Ai parcurs toate lectiile de recapitulare. Mergi la simulari pentru a testa tot ce ai invatat!

Simulare #1 →