4/4

</> Informatica liceu

Breviar Bac Info

Lecția 4 ⏱ 90 min

📘 BAC Informatică — Breviar Complet¶

Specializarea Matematică-Informatică
Limbaj principal: C++ (limbaj de examen) · Referințe rapide: Python

Cheat sheet dens pentru recapitulare. Toate formulele, algoritmii și șabloanele de cod necesare la bacalaureat.

📋 Cuprins¶

Pseudocod — sintaxă
C++ — elementele de bază
Algoritmi cu cifrele unui număr
Divizibilitate & numere prime
CMMDC, CMMMC și Fibonacci
Tablouri unidimensionale (vectori)
Tablouri bidimensionale (matrice)
Șiruri de caractere
Înregistrări (struct)
Fișiere text
Sortare
Căutare
Interclasare
Complexitate
Subprograme
Recursivitate
Backtracking
Grafuri neorientate
Arbori
Formule & identități utile
Greșeli frecvente la BAC

1. Pseudocod — sintaxă¶

Citire / scriere¶

citește a, b, c
scrie a, b, "text"

Atribuire¶

x ← expresie

Decizie¶

┌dacă <condiție> atunci
│   <instrucțiuni>
│altfel
│   <instrucțiuni>
└■

Structuri repetitive¶

┌cât timp <cond> execută            ┌repetă                ┌pentru i ← 1, n, pas execută
│   <instr>                         │   <instr>            │   <instr>
└■                                  └până când <cond>      └■

Subprograme¶

┌subprogram nume(param) returnează tip
│   instr
└■

Operatori (pseudocod)¶

Aritmetici: +, -, *, /, ^ (putere), % (rest), [ ] (parte întreagă)
√ radical, % modulo

2. C++ — elementele de bază¶

Schelet minim¶

#include <iostream>
using namespace std;
int main() {
    int n; cin >> n;
    cout << n * 2;
    return 0;
}

Tipuri de date (intervale)¶

Tip	Dimensiune	Interval
`char`	1 B	-128 … 127 (sau 0..255 `unsigned`)
`short`	2 B	-32.768 … 32.767
`int`	4 B	≈ ±2·10⁹
`unsigned int`	4 B	0 … ≈4·10⁹
`long long`	8 B	≈ ±9·10¹⁸
`float`	4 B	~7 cifre semnificative
`double`	8 B	~15 cifre semnificative
`bool`	1 B	`true`/`false`

Operatori esențiali¶

Cat.	Operatori
Aritmetici	`+ - * / %`
Relaționali	`== != < > <= >=`
Logici	`&& \|\| !`
Bitwise	`& \| ^ ~ << >>`
Atribuire	`= += -= *= /= %=`
Incrementare	`++ --`
Ternar	`cond ? val1 : val2`

Atenție: 5/2 = 2 (împărțire întreagă); 5/2.0 = 2.5; 5%2 = 1.
Priorități (descrescător): ! > * / % > + - > < <= > == != > && > ||.

I/O rapid (pentru probleme cu multe date)¶

ios_base::sync_with_stdio(false);
cin.tie(NULL);

Structuri de control (C++)¶

// decizie
if (cond) { } else if (cond2) { } else { }

// switch
switch(x) {
    case 1: cout << "unu"; break;
    case 2: cout << "doi"; break;
    default: cout << "alt";
}

// while
while (cond) { }

// do-while
do { } while (cond);

// for
for (int i = 0; i < n; i++) { }

// break — ieșire din buclă
// continue — sare la următoarea iterație

Constante¶

const int N = 100;
#define MAX 1000

Conversii (cast)¶

int x = (int) 3.7;          // 3
double y = (double) 5 / 2;  // 2.5

3. Algoritmi cu cifrele unui număr¶

Operații fundamentale cu cifre¶

Operație	Formulă
Ultima cifră	`n % 10`
Eliminare ultima cifră	`n / 10` (cu `int`)
Adaugă cifra `c` la dreapta	`n = n*10 + c`
Adaugă `c` la stânga (dacă `n` are `k` cifre)	`n = c*10^k + n`

Șabloane esențiale¶

// Suma cifrelor
int suma_cifre(int n) {
    int s = 0;
    while (n) { s += n % 10; n /= 10; }
    return s;
}

// Număr de cifre
int nr_cifre(int n) {
    int c = 0;
    if (n == 0) return 1;
    while (n) { c++; n /= 10; }
    return c;
}

// Oglinditul unui număr
int oglindit(int n) {
    int o = 0;
    while (n) { o = o*10 + n%10; n /= 10; }
    return o;
}

// Palindrom
bool palindrom(int n) { return n == oglindit(n); }

// Maximul cifrelor
int cifra_max(int n) {
    int m = 0;
    while (n) { if (n%10 > m) m = n%10; n /= 10; }
    return m;
}

// Câte cifre pare are numărul
int nr_cifre_pare(int n) {
    int c = 0;
    while (n) { if ((n%10) % 2 == 0) c++; n /= 10; }
    return c;
}

// Elimină cifrele impare, păstrând ordinea cifrelor pare
int elim_impare(int n) {
    int rez = 0, p = 1;
    while (n) {
        int c = n % 10;
        if (c % 2 == 0) { rez = rez + c * p; p *= 10; }
        n /= 10;
    }
    return rez;
}

Verificări rapide¶

Proprietate	Cod
Par	`n % 2 == 0`
Multiplu de `k`	`n % k == 0`
Ultima cifră e 5	`n % 10 == 5`
Divizibil cu 3 (prin cifre)	suma cifrelor divizibilă cu 3

4. Divizibilitate & numere prime¶

Divizori¶

// Toți divizorii lui n — O(√n)
for (int d = 1; d*d <= n; d++) {
    if (n % d == 0) {
        cout << d << " ";
        if (d != n/d) cout << n/d << " ";
    }
}

// Numărul de divizori
int nr_div(int n) {
    int nr = 0;
    for (int d = 1; d*d <= n; d++)
        if (n % d == 0) nr += (d == n/d) ? 1 : 2;
    return nr;
}

// Suma divizorilor
int sum_div(int n) {
    int s = 0;
    for (int d = 1; d*d <= n; d++)
        if (n % d == 0) {
            s += d;
            if (d != n/d) s += n/d;
        }
    return s;
}

Număr prim¶

bool prim(int n) {
    if (n < 2) return false;
    for (int d = 2; d*d <= n; d++)
        if (n % d == 0) return false;
    return true;
}

Descompunere în factori primi¶

void descompune(int n) {
    for (int d = 2; d*d <= n; d++)
        while (n % d == 0) {
            cout << d << " "; n /= d;
        }
    if (n > 1) cout << n;  // dacă a rămas un factor prim > √n_inițial
}

Ciurul lui Eratostene¶

bool ciur[1000001];

void eratostene(int n) {
    for (int i = 2; i <= n; i++) ciur[i] = true;
    for (int i = 2; i*i <= n; i++)
        if (ciur[i])
            for (int j = i*i; j <= n; j += i)
                ciur[j] = false;
}
// ciur[k] = true ⇔ k e prim

Număr perfect / abundent / deficient¶

int s = sum_div(n) - n;       // suma divizorilor proprii
// n perfect: s == n   (6, 28, 496, 8128)
// n abundent: s > n
// n deficient: s < n

5. CMMDC, CMMMC și Fibonacci¶

Algoritmul lui Euclid — CMMDC¶

// Cu împărțiri (rapid — O(log n))
int cmmdc(int a, int b) {
    while (b) { int r = a % b; a = b; b = r; }
    return a;
}

// Cu scăderi (clasic, mai lent)
int cmmdc_s(int a, int b) {
    while (a != b) { if (a > b) a -= b; else b -= a; }
    return a;
}

// Recursiv
int cmmdc(int a, int b) { return b == 0 ? a : cmmdc(b, a%b); }

CMMMC — Formula¶

$$\text{cmmmc}(a,b) = \frac{a \cdot b}{\text{cmmdc}(a,b)}$$

long long cmmmc(int a, int b) {
    return (long long)a * b / cmmdc(a, b);
}

Proprietăți¶

cmmdc(a, 0) = a
cmmdc(a, b) = cmmdc(b, a % b) (cheia algoritmului Euclid)
cmmdc(a, b) · cmmmc(a, b) = a · b
CMMDC a mai multor numere: se aplică asociativ — cmmdc(a,b,c) = cmmdc(cmmdc(a,b), c)

Șirul lui Fibonacci¶

$$F_0 = 0, \quad F_1 = 1, \quad F_n = F_{n-1} + F_{n-2}$$

Primii termeni: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144…

// Iterativ — O(n)
int fib(int n) {
    if (n < 2) return n;
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b; a = b; b = c;
    }
    return b;
}

// Recursiv (INEFICIENT — O(2^n))
int fib_r(int n) { return n < 2 ? n : fib_r(n-1) + fib_r(n-2); }

Raportul Fₙ₊₁/Fₙ → φ = (1+√5)/2 ≈ 1,618 (numărul de aur).

6. Tablouri unidimensionale (vectori)¶

Declarare & inițializare¶

int v[100];                       // nedefinit
int v[5] = {3, 7, 1, 9, 4};
int v[100] = {0};                 // toate 0
int n; cin >> n;
for (int i = 0; i < n; i++) cin >> v[i];

Algoritmi de bază (șabloane esențiale)¶

// SUMA
int s = 0;
for (int i = 0; i < n; i++) s += v[i];

// MINIMUL și poziția lui
int mn = v[0], poz = 0;
for (int i = 1; i < n; i++)
    if (v[i] < mn) { mn = v[i]; poz = i; }

// MAXIMUL — analog

// NUMĂR de elemente cu o proprietate
int cnt = 0;
for (int i = 0; i < n; i++)
    if (v[i] % 2 == 0) cnt++;

// CĂUTARE liniară
int poz = -1;
for (int i = 0; i < n; i++)
    if (v[i] == x) { poz = i; break; }

// INVERSARE pe loc
for (int i = 0, j = n-1; i < j; i++, j--)
    swap(v[i], v[j]);

// ȘTERGEREA unui element de pe poziția p
for (int i = p; i < n-1; i++) v[i] = v[i+1];
n--;

// INSERARE x pe poziția p
for (int i = n; i > p; i--) v[i] = v[i-1];
v[p] = x; n++;

// ELIMINĂ DUPLICATE (din vector sortat)
int k = 1;
for (int i = 1; i < n; i++)
    if (v[i] != v[i-1]) v[k++] = v[i];
n = k;

// SUMA MAXIMĂ a unui subvector (Kadane)
int s = 0, best = v[0];
for (int i = 0; i < n; i++) {
    s = max(v[i], s + v[i]);
    best = max(best, s);
}

Lista de frecvențe¶

int f[101] = {0};
for (int i = 0; i < n; i++) f[v[i]]++;   // pt. valori 0..100

// cea mai frecventă valoare
int cf = 0, val;
for (int i = 0; i <= 100; i++)
    if (f[i] > cf) { cf = f[i]; val = i; }

7. Tablouri bidimensionale (matrice)¶

Declarare & citire¶

int a[100][100];
int n, m; cin >> n >> m;
for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        cin >> a[i][j];

Parcurgeri standard¶

// Pe rânduri (linie cu linie)
for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) ...

// Pe coloane
for (int j = 0; j < m; j++)
    for (int i = 0; i < n; i++) ...

// Diagonala principală (i == j)
for (int i = 0; i < n; i++) a[i][i];

// Diagonala secundară (i + j == n-1)
for (int i = 0; i < n; i++) a[i][n-1-i];

// Sub diagonala principală (i > j)
// Peste diagonala principală (i < j)

Elemente speciale¶

Condiție	Semnificație
`i == j`	Diagonala principală
`i + j == n-1`	Diagonala secundară
`i < j`	Triunghiul superior (deasupra DP)
`i > j`	Triunghiul inferior (sub DP)
`i + j < n-1`	Triunghiul superior (deasupra DS)

Proprietăți ale matricelor¶

// Matrice pătratică  — n == m
// Simetrică față de DP: a[i][j] == a[j][i]
bool simetrica() {
    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++)
            if (a[i][j] != a[j][i]) return false;
    return true;
}

// Matrice identitate: DP = 1, rest = 0

// Transpusa
int t[100][100];
for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        t[j][i] = a[i][j];

Parcurgeri speciale¶

// În zigzag (șarpe)
for (int i = 0; i < n; i++)
    if (i % 2 == 0)
        for (int j = 0; j < m; j++) a[i][j];
    else
        for (int j = m-1; j >= 0; j--) a[i][j];

// Spirală (schelet)
int top=0, bot=n-1, lft=0, rgt=m-1;
while (top <= bot && lft <= rgt) {
    for (int j = lft; j <= rgt; j++) cout << a[top][j];
    top++;
    for (int i = top; i <= bot; i++) cout << a[i][rgt];
    rgt--;
    if (top <= bot) { for (int j = rgt; j >= lft; j--) cout << a[bot][j]; bot--; }
    if (lft <= rgt) { for (int i = bot; i >= top; i--) cout << a[i][lft]; lft++; }
}

Vecinii unui element¶

// 4 vecini (ortogonal)
int dx[] = {-1, 0, 0, 1};
int dy[] = { 0,-1, 1, 0};

// 8 vecini (cu diagonale)
int dx[] = {-1,-1,-1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1,-1, 1,-1, 0, 1};

for (int k = 0; k < 4; k++) {
    int ni = i + dx[k], nj = j + dy[k];
    if (ni >= 0 && ni < n && nj >= 0 && nj < m)
        // a[ni][nj] e vecin valid
}

8. Șiruri de caractere¶

Două moduri în C++¶

// 1. Stil C — char[]
char s[100] = "Salut";

// 2. Stil C++ — string (RECOMANDAT)
#include <string>
string s = "Salut";

Operații esențiale cu `string`¶

string s = "Informatica";

s.length();           // sau s.size() → 11
s[0];                 // 'I'
s.front();            // 'I'
s.back();             // 'a'
s.substr(3, 4);       // "rmat"  (poz 3, lungime 4)
s.find("mat");        // 5 (prima apariție)  |  string::npos dacă nu există
s.rfind("a");         // 10 (ultima apariție)
s.insert(5, "XX");    // inserează la poziția 5
s.erase(5, 2);        // șterge 2 caractere de la poziția 5
s.replace(0, 3, "YY");// înlocuiește primele 3 caractere
s += " rocks";        // concatenare
s.clear();            // golește

// Comparație lexicografică (ca în dicționar)
if (s1 == s2) ...
if (s1 < s2) ...

Operații cu `char[]` (stil C)¶

#include <cstring>

strlen(s);              // lungimea
strcpy(dest, src);      // dest = src
strcat(dest, src);      // dest = dest + src
strcmp(s1, s2);         // <0 / 0 / >0
strchr(s, 'a');         // pointer spre prima apariție a 'a'
strstr(s, "abc");       // pointer spre prima apariție a "abc"
strrev(s);              // inversează (nu e standard pe Linux)

// Tokenizare
char* p = strtok(s, " ,.!?");
while (p) { cout << p << endl; p = strtok(NULL, " ,.!?"); }

Conversii¶

// string → int / double
int n = stoi("42");
double d = stod("3.14");

// int → string
string s = to_string(42);

// char[] → int / double
int n = atoi(s);
double d = atof(s);

// sprintf / sscanf — stil C
char buf[20];
sprintf(buf, "%d", 42);
int x; sscanf("123 abc", "%d", &x);

Verificări caractere (din `<cctype>`)¶

Funcție	Returnează true dacă
`isalpha(c)`	literă
`isdigit(c)`	cifră
`isalnum(c)`	literă sau cifră
`isspace(c)`	spațiu, tab, newline
`isupper(c)`	literă mare
`islower(c)`	literă mică
`toupper(c)`	→ majusculă
`tolower(c)`	→ minusculă

Coduri ASCII esențiale¶

Caracter	Cod
`'0'`	48
`'9'`	57
`'A'`	65
`'Z'`	90
`'a'`	97
`'z'`	122
`' '`	32

Relații utile:

c - '0' → valoarea numerică a cifrei
'A' + k → a k-a literă mare (0-indexed)
c - 'a' + 'A' → transformă literă mică în mare

Șabloane clasice¶

// Numără vocale
int voc(string s) {
    string vc = "aeiouAEIOU";
    int c = 0;
    for (char x : s) if (vc.find(x) != string::npos) c++;
    return c;
}

// Inversare
string rev = string(s.rbegin(), s.rend());

// Spart în cuvinte
#include <sstream>
stringstream ss(s);
string cuv;
while (ss >> cuv) cout << cuv << endl;

// Palindrom
bool pal(string s) {
    for (int i = 0, j = s.size()-1; i < j; i++, j--)
        if (s[i] != s[j]) return false;
    return true;
}

9. Înregistrări (struct)¶

Definire și utilizare¶

struct Elev {
    char nume[30];
    int varsta;
    float media;
};

// Declarare
Elev e;                              // variabilă
Elev clasa[30];                      // vector de înregistrări
Elev a = {"Ana", 17, 9.50};          // inițializare

// Acces la câmpuri
strcpy(e.nume, "Alex");
e.varsta = 17;
cin >> e.media;

// Pointer
Elev *p = &e;
p->varsta;   // echivalent cu (*p).varsta

Sortare vector de struct-uri¶

// După medie descrescător
for (int i = 0; i < n-1; i++)
    for (int j = i+1; j < n; j++)
        if (clasa[i].media < clasa[j].media)
            swap(clasa[i], clasa[j]);

Înregistrări imbricate¶

struct Data { int zi, luna, an; };
struct Persoana {
    char nume[30];
    Data nastere;
};

Persoana p;
p.nastere.an = 2008;

10. Fișiere text¶

Stil C++ (`fstream`) — RECOMANDAT¶

#include <fstream>
using namespace std;

// Scriere
ofstream fout("iesire.txt");
fout << "text " << 42 << endl;
fout.close();

// Citire
ifstream fin("intrare.txt");
int x;
while (fin >> x) {            // citire până la EOF
    // procesează x
}
fin.close();

// Citire pe linii
string linie;
while (getline(fin, linie)) { }

Stil C (`FILE*`)¶

#include <cstdio>
FILE *f = fopen("date.txt", "r");      // "w", "a", "r+"
int x;
while (fscanf(f, "%d", &x) == 1) { }
fclose(f);

Operații comune¶

// Număr de linii
int nr = 0; string l;
ifstream f("a.txt");
while (getline(f, l)) nr++;

// Copiere între fișiere
ifstream in("a.txt"); ofstream out("b.txt");
string l;
while (getline(in, l)) out << l << "\n";

// Verificare deschidere
ifstream f("a.txt");
if (!f.is_open()) { cout << "Eroare!"; return 1; }

11. Sortare¶

Bubble Sort (metoda bulelor)¶

Idee: compară vecini adiacenți, schimbă dacă sunt în ordine greșită.

void bubble(int v[], int n) {
    bool sch;
    do {
        sch = false;
        for (int i = 0; i < n-1; i++)
            if (v[i] > v[i+1]) {
                swap(v[i], v[i+1]);
                sch = true;
            }
    } while (sch);
}

Complexitate: O(n²) general, O(n) dacă e deja sortat (cu optimizare).

Selection Sort (selecția minimului)¶

Idee: găsește minimul și îl mută la început.

void selection(int v[], int n) {
    for (int i = 0; i < n-1; i++) {
        int pm = i;
        for (int j = i+1; j < n; j++)
            if (v[j] < v[pm]) pm = j;
        swap(v[i], v[pm]);
    }
}

Complexitate: O(n²) întotdeauna.

Sortare cu `std::sort` (dacă e permis)¶

#include <algorithm>
sort(v, v + n);                         // crescător
sort(v, v + n, greater<int>());         // descrescător
sort(v, v + n, [](int a, int b) { return a > b; });  // cu lambda

Comparație¶

Algoritm	Cel mai bun	Mediu	Cel mai rău	Stabilă?	Memorie
Bubble	O(n)	O(n²)	O(n²)	Da	O(1)
Selection	O(n²)	O(n²)	O(n²)	Nu	O(1)
Insertion	O(n)	O(n²)	O(n²)	Da	O(1)
Merge	O(n log n)	O(n log n)	O(n log n)	Da	O(n)
Quick	O(n log n)	O(n log n)	O(n²)	Nu	O(log n)

12. Căutare¶

Căutare secvențială (liniară) — O(n)¶

int cautare_lin(int v[], int n, int x) {
    for (int i = 0; i < n; i++)
        if (v[i] == x) return i;
    return -1;
}

Căutare binară — O(log n)¶

Condiție: vectorul trebuie să fie SORTAT!

int binar(int v[], int n, int x) {
    int st = 0, dr = n - 1;
    while (st <= dr) {
        int m = st + (dr - st) / 2;
        if (v[m] == x) return m;
        if (v[m] < x) st = m + 1;
        else          dr = m - 1;
    }
    return -1;
}

Varianta recursivă:

int binar(int v[], int st, int dr, int x) {
    if (st > dr) return -1;
    int m = (st + dr) / 2;
    if (v[m] == x) return m;
    if (v[m] < x) return binar(v, m+1, dr, x);
    return binar(v, st, m-1, x);
}

13. Interclasare¶

Problemă: două vectori sortați → unul singur sortat.
Complexitate: O(n + m).

void interclas(int a[], int n, int b[], int m, int c[], int &k) {
    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++];
    while (j < m) c[k++] = b[j++];
}

14. Complexitate¶

Notația O (worst-case)¶

O(…)	Nume	Exemplu
O(1)	constant	acces la `v[i]`
O(log n)	logaritmic	căutare binară
O(n)	liniar	parcurgere vector
O(n log n)	liniar-log.	merge sort, `sort()`
O(n²)	pătratic	bubble, selection
O(n³)	cubic	3 bucle imbricate
O(2ⁿ)	exponențial	Fibonacci recursiv
O(n!)	factorial	permutări

Cât de mult poate fi `n`?¶

Pentru o secundă de timp de executare:

O(n): n ≤ 10⁸
O(n log n): n ≤ 10⁶
O(n²): n ≤ 10⁴
O(n³): n ≤ 500
O(2ⁿ): n ≤ 25
O(n!): n ≤ 10

Cum se calculează¶

Bucle secvențiale: O(n) + O(m) = O(n + m).
Bucle imbricate: se înmulțesc: O(n * m).
Constante se ignoră: O(3n) = O(n).
Se păstrează termenul dominant: O(n² + n) = O(n²).

Spațiul de memorie¶

int v[N] → 4·N octeți.
Matrice a[N][N] → 4·N² octeți.
Pentru N = 10⁴, matrice int → 400 MB (PROBLEMĂ!).

15. Subprograme¶

Sintaxă C++¶

// Funcție cu valoare returnată
int max2(int a, int b) { return a > b ? a : b; }

// Procedură (void)
void afisare(int v[], int n) {
    for (int i = 0; i < n; i++) cout << v[i] << " ";
}

Transfer parametri¶

Tip	Sintaxă	Efect
Prin valoare	`void f(int x)`	`x` = copie; modificările NU afectează originalul
Prin referință	`void f(int &x)`	`x` = alias; modificările afectează originalul
Const-referință	`void f(const int &x)`	Nu se modifică, dar se evită copia
Vector (adresă)	`void f(int v[], int n)`	Modificările SE vor vedea (transfer prin adresă)

void schimba(int a, int b) { swap(a, b); }     // nu face nimic (copii)
void schimba(int &a, int &b) { swap(a, b); }   // FUNCȚIONEAZĂ

Variabile locale vs globale¶

Locale — declarate în funcție; vizibile DOAR acolo.
Globale — declarate în afara funcțiilor; vizibile PESTE TOT.
O locală „ascunde” o globală cu același nume.

int x = 10;     // globală
void f() {
    int x = 5;  // locală — ascunde globala
    cout << x;  // 5
}

Domeniu de vizibilitate (scope)¶

Local bloc { } — variabila dispare la }.
Global — pe toată durata programului.

16. Recursivitate¶

Anatomia unei funcții recursive¶

3 ingrediente obligatorii:

Caz de bază — condiția care OPREȘTE recursivitatea.
Pas recursiv — apel cu argumente „mai simple”.
Progres — fiecare apel să se apropie de cazul de bază.

Exemple clasice¶

// Factorial
int fact(int n) { return n <= 1 ? 1 : n * fact(n-1); }

// Suma primelor n numere
int sum(int n) { return n == 0 ? 0 : n + sum(n-1); }

// CMMDC Euclid
int cmmdc(int a, int b) { return b == 0 ? a : cmmdc(b, a%b); }

// Putere rapidă — O(log n)
int putere(int a, int n) {
    if (n == 0) return 1;
    if (n % 2 == 0) { int x = putere(a, n/2); return x*x; }
    return a * putere(a, n-1);
}

// Suma cifrelor
int s_c(int n) { return n == 0 ? 0 : n%10 + s_c(n/10); }

// Fibonacci (INEFICIENT)
int fib(int n) { return n < 2 ? n : fib(n-1) + fib(n-2); }

// Verifică palindrom
bool pal(string s, int st, int dr) {
    if (st >= dr) return true;
    return s[st] == s[dr] && pal(s, st+1, dr-1);
}

Recursivitate directă vs. indirectă¶

Directă — funcția f se apelează pe sine.
Indirectă — f apelează g, g apelează f.

Stiva de apeluri¶

Fiecare apel recursiv ocupă loc pe stiva programului. În C++, stiva e de obicei 1-8 MB — cam 10⁵ apeluri adânci.

Eroare tipică: stack overflow = recursivitate infinită sau prea adâncă.

17. Backtracking¶

Schema generală¶

int st[100];      // soluția în construcție
int n;

void back(int k) {
    if (k == n+1) {
        // afișare / procesare soluție
        return;
    }
    for (int v = 1; v <= n; v++) {
        st[k] = v;
        if (valid(k)) back(k + 1);
    }
}

Permutări¶

// Toate permutările mulțimii {1..n}
bool folosit[100];

void perm(int k) {
    if (k == n+1) {
        for (int i = 1; i <= n; i++) cout << st[i];
        cout << endl;
        return;
    }
    for (int v = 1; v <= n; v++)
        if (!folosit[v]) {
            st[k] = v; folosit[v] = true;
            perm(k+1);
            folosit[v] = false;
        }
}

Număr de permutări: n!

Aranjamente A(n, k)¶

// k elemente distincte aranjate într-o ordine
void aranj(int poz, int k) {
    if (poz == k+1) { /* afișare */ return; }
    for (int v = 1; v <= n; v++)
        if (!folosit[v]) {
            st[poz] = v; folosit[v] = true;
            aranj(poz+1, k);
            folosit[v] = false;
        }
}

Formula: A(n,k) = n! / (n-k)!

Combinări C(n, k)¶

// k elemente alese din n, ordine nu contează
void comb(int poz, int start) {
    if (poz == k+1) { /* afișare */ return; }
    for (int v = start; v <= n; v++) {
        st[poz] = v;
        comb(poz+1, v+1);
    }
}
// apel: comb(1, 1);

Formula: C(n,k) = n! / (k! · (n-k)!)

Produs cartezian¶

// secvențe de k elemente din {1..n}, cu repetiție
void prod(int poz, int k) {
    if (poz == k+1) { /* afișare */ return; }
    for (int v = 1; v <= n; v++) {
        st[poz] = v;
        prod(poz+1, k);
    }
}

Număr: nᵏ.

Submulțimi¶

// Toate submulțimile mulțimii {1..n}
void sub(int k) {
    if (k == n+1) {
        cout << "{";
        for (int i = 1; i <= n; i++)
            if (st[i]) cout << i << " ";
        cout << "}\n";
        return;
    }
    st[k] = 0; sub(k+1);       // NU includem k
    st[k] = 1; sub(k+1);       // INCLUDEM k
}

Număr de submulțimi: 2ⁿ.

Problema N-reginelor¶

int st[20], n;

bool valid(int k) {
    for (int i = 1; i < k; i++)
        if (st[i] == st[k] || abs(st[i]-st[k]) == abs(i-k))
            return false;
    return true;
}

void regine(int k) {
    if (k == n+1) {
        // afișare soluție
        return;
    }
    for (int v = 1; v <= n; v++) {
        st[k] = v;
        if (valid(k)) regine(k+1);
    }
}

Formule combinatoriale¶

Tip	Formula	Exemplu n=3,k=2
Permutări P(n)	n!	P(3)=6
Aranjamente A(n,k)	n! / (n-k)!	A(3,2)=6
Combinări C(n,k)	n! / (k!(n-k)!)	C(3,2)=3
Produs cartezian	nᵏ	3²=9
Submulțimi	2ⁿ	2³=8

18. Grafuri neorientate¶

Definiții esențiale¶

Termen	Definiție
Graf G=(V,E)	V = mulțimea nodurilor, E = muchiilor
Muchie `{u,v}`	Legătură neorientată între u și v
Adiacență	u și v adiacente ⇔ ∃ muchia
Incidență	muchie incidentă cu nodul u ⇔ u e extremitate
Grad `deg(v)`	nr. muchii incidente cu v
Lanț	succesiune de muchii consecutive
Lanț elementar	fără nod repetat
Lanț simplu	fără muchie repetată
Ciclu	lanț în care primul = ultimul nod
Ciclu elementar	ciclu fără nod repetat (excepție capete)
Lungime	nr. muchii din lanț/ciclu
Subgraf	se obține ștergând unele noduri (și muchiile incidente)
Graf parțial	se obține ștergând doar muchii
Conex	există lanț între orice 2 noduri
Componentă conexă	subgraf conex maximal
Complet (Kₙ)	orice 2 noduri adiacente; are n(n-1)/2 muchii

Proprietăți fundamentale¶

Σ deg(v) = 2 · m (suma gradelor = de 2 ori numărul muchiilor).
Numărul de noduri de grad impar este par.
Într-un graf complet Kₙ, m = n(n-1)/2.
Un graf cu n noduri are cel mult n(n-1)/2 muchii.

Reprezentări¶

Matrice de adiacență¶

int a[100][100];   // a[i][j] = 1 dacă muchie {i,j}, altfel 0
// Pentru graf neorientat: a[i][j] == a[j][i] (SIMETRIC)
// Diagonala = 0 (de obicei nu avem bucle)

Memorie: O(n²). Verifică adiacență: O(1).

Liste de adiacență¶

vector<int> adj[100];
// adj[i] = lista vecinilor lui i
// Adăugare muchie {u,v}: adj[u].push_back(v); adj[v].push_back(u);

Memorie: O(n + m). Mai bună pentru grafuri rare.

Gradul unui nod¶

// Din matrice
int grad(int i) {
    int g = 0;
    for (int j = 0; j < n; j++) g += a[i][j];
    return g;
}

// Din listă
int grad(int i) { return adj[i].size(); }

Parcurgere în lățime (BFS) — O(n + m) / O(n²)¶

#include <queue>
bool viz[100];

void bfs(int s) {
    queue<int> q;
    q.push(s); viz[s] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        cout << u << " ";
        // Cu matrice:
        for (int v = 0; v < n; v++)
            if (a[u][v] && !viz[v]) {
                viz[v] = true;
                q.push(v);
            }
        // Cu liste: for (int v : adj[u]) if (!viz[v]) { ... }
    }
}

Parcurgere în adâncime (DFS) — O(n + m)¶

bool viz[100];

void dfs(int u) {
    viz[u] = true;
    cout << u << " ";
    // Cu matrice:
    for (int v = 0; v < n; v++)
        if (a[u][v] && !viz[v]) dfs(v);
    // Cu liste: for (int v : adj[u]) if (!viz[v]) dfs(v);
}

Aplicații BFS/DFS¶

1. Conexitate

bool conex() {
    for (int i = 0; i < n; i++) viz[i] = false;
    dfs(0);
    for (int i = 0; i < n; i++) if (!viz[i]) return false;
    return true;
}

2. Număr componente conexe

int nr_comp() {
    int nr = 0;
    for (int i = 0; i < n; i++) viz[i] = false;
    for (int i = 0; i < n; i++)
        if (!viz[i]) { dfs(i); nr++; }
    return nr;
}

3. Distanța minimă (BFS)

int dist[100];
// inițial -1, dist[s] = 0; în BFS: dist[v] = dist[u] + 1

19. Arbori¶

Definiții echivalente¶

Un graf cu n noduri este arbore ⇔ oricare din:

Este conex și aciclic.
Este conex și are n-1 muchii.
Este aciclic și are n-1 muchii.
Între orice 2 noduri există lanț unic.

Terminologie (arbore cu rădăcină)¶

Termen	Definiție
Rădăcină	Nodul special, de start
Descendent direct (fiu)	Nod imediat subordonat
Ascendent direct (tată/părinte)	Nod imediat superior
Descendent	Orice nod în subarborele lui
Ascendent	Orice nod pe drum spre rădăcină
Frați	Noduri cu același tată
Frunză / nod terminal	Fără descendenți
Nivel	Distanța (în muchii) de la rădăcină
Înălțime	Nivelul maxim

Reprezentări¶

1. Vector de tați (cea mai compactă)¶

int tata[100];   // tata[i] = părintele nodului i; 0 pt. rădăcină

Avantaje: memorie O(n), găsești ușor ascendenții.

2. Matrice de adiacență¶

Ca la grafuri generale, dar simetrică și fără cicluri.

3. Listă de fii¶

vector<int> fii[100];  // fii[i] = lista descendenților direcți

Găsirea rădăcinii¶

// Din vector de tați: rădăcina e nodul i cu tata[i] == 0
int radacina() {
    for (int i = 1; i <= n; i++) if (tata[i] == 0) return i;
    return -1;
}

Niveluri și înălțime¶

// Nivelul unui nod (cu vector de tați)
int nivel(int x) {
    int nv = 0;
    while (tata[x]) { x = tata[x]; nv++; }
    return nv;
}

// Înălțimea arborelui
int inaltime() {
    int h = 0;
    for (int i = 1; i <= n; i++)
        h = max(h, nivel(i));
    return h;
}

Frunze¶

// Un nod e frunză dacă nu e tată al nimănui
bool frunza[100] = {false};
for (int i = 1; i <= n; i++) frunza[i] = true;
for (int i = 1; i <= n; i++)
    if (tata[i]) frunza[tata[i]] = false;

Arbori binari¶

Fiecare nod are cel mult 2 fii: stâng și drept.

struct Nod { int val; Nod *stg, *drp; };

Parcurgeri arbori binari¶

Denumire	Ordine	Exemplu pentru `1-(2,(4,5)),3-(,(6))`
Preordine (RSD)	Rădăcină → Stânga → Dreapta	1 2 4 5 3 6
Inordine (SRD)	Stânga → Rădăcină → Dreapta	4 2 5 1 3 6
Postordine (SDR)	Stânga → Dreapta → Rădăcină	4 5 2 6 3 1

void preord(Nod* n) {
    if (!n) return;
    cout << n->val << " ";
    preord(n->stg); preord(n->drp);
}

void inord(Nod* n) {
    if (!n) return;
    inord(n->stg);
    cout << n->val << " ";
    inord(n->drp);
}

void postord(Nod* n) {
    if (!n) return;
    postord(n->stg); postord(n->drp);
    cout << n->val << " ";
}

20. Formule & identități utile¶

Sume remarcabile¶

Suma	Formula
1 + 2 + 3 + … + n	n(n+1)/2
1² + 2² + … + n²	n(n+1)(2n+1)/6
1³ + 2³ + … + n³	[n(n+1)/2]²
1 + 3 + 5 + … + (2n-1) (impare)	n²
2 + 4 + 6 + … + 2n (pare)	n(n+1)
1 + 2 + 4 + … + 2ⁿ	2ⁿ⁺¹ − 1
q⁰ + q¹ + q² + … + qⁿ	(qⁿ⁺¹ − 1)/(q − 1)

Combinatorica¶

Permutări: P(n) = n!
Aranjamente: A(n,k) = n!/(n-k)! = n·(n-1)·…·(n-k+1)
Combinări: C(n,k) = n!/(k!·(n-k)!)
Submulțimi ale unei mulțimi cu n elemente: 2ⁿ
Identitatea lui Pascal: C(n,k) = C(n-1,k-1) + C(n-1,k)
Simetrie: C(n,k) = C(n,n-k)

Proprietăți numere¶

Test	Verificare
Par	`n % 2 == 0`
Divizibil cu 3	suma cifrelor div. cu 3
Divizibil cu 9	suma cifrelor div. cu 9
Divizibil cu 5	ultima cifră 0 sau 5
Divizibil cu 4	ultimele 2 cifre formează număr div. cu 4
Divizibil cu 11	suma alternată a cifrelor div. cu 11

Baze de numerație¶

Conversia 10 → b: împărțiri succesive la b, se citesc resturile invers.
Conversia b → 10: folosind schema lui Horner: ((c₀·b + c₁)·b + c₂)·b + ....

Logaritmi (pentru complexitate)¶

log₂(n) = numărul aproximativ de împărțiri la 2 până ajunge la 1.
log₂(1000) ≈ 10, log₂(10⁶) ≈ 20, log₂(10⁹) ≈ 30.

Grafuri — formule rapide¶

Σ deg(v) = 2m (neorientat).
Kₙ are n(n-1)/2 muchii.
Arborele cu n noduri are n-1 muchii.
Graf bipartit ⇔ nu conține cicluri de lungime impară.

21. Greșeli frecvente la BAC¶

La citire/scriere¶

❌ Uiți cin >> înainte de variabilă.
❌ Citești din fișier greșit (fin vs. fout).
❌ Nu închizi fișierele (.close()).

La tablouri¶

❌ v[n] când n = dimensiune (deja out-of-bounds — last index = n-1).
❌ Folosire v[i-1] când i = 0 (index negativ).
❌ Nu inițializezi vectorii statici cu {0} când ai nevoie.

La cifre¶

❌ while (n > 0) dar și n = 0 trebuie tratat separat.
❌ Oglinditul lui 120 e 21, nu 021 (zerourile se pierd).

La divizori/prime¶

❌ Parcurgi până la n în loc de √n — TIME LIMIT.
❌ Uiți cazul n = 1 (nu e prim, dar are 1 divizor).
❌ Uiți să afișezi și n/d când d ≠ n/d.

La CMMDC¶

❌ Schimbi a și b în timpul Euclid și pierzi valori.
❌ cmmdc(0, 0) — caz limită; returnează 0 (convenție).

La Fibonacci¶

❌ Indice: F₀=0 sau F₁=1? Ambele convenții există — verifică enunțul.

La recursivitate¶

❌ Uiți cazul de bază → recursivitate infinită.
❌ Pas care nu apropie de cazul de bază.
❌ Apel recursiv care face mai multă muncă decât trebuie (ex: Fibonacci naiv).

La Backtracking¶

❌ Nu „dai înapoi” (folosit[v] = false; după apel).
❌ Condiția de oprire greșită (k == n vs. k == n+1).
❌ Indexul: vector de la 0 sau de la 1?

La grafuri¶

❌ Crezi că a[i][j] = 1 pentru neorientat implică automat a[j][i] = 1 — la citire, trebuie setat manual!
❌ Pentru BFS nu marchezi vizitat ÎNAINTE de a pune în coadă → adaugi același nod de 2 ori.
❌ Nu inițializezi viz[] la începutul fiecărui algoritm.

La șiruri¶

❌ char s[10] dar șirul e de 10 caractere → depășire (are nevoie de \0 final).
❌ Uiți #include <cstring> pentru strlen etc.
❌ Comparație șiruri cu == în stil C (nu merge; folosește strcmp).

La struct¶

❌ Nu ai copy-constructor când folosești string → comportament nedefinit pentru cazuri rare.
❌ Accesezi câmpul unui pointer cu . în loc de ->.

La complexitate¶

❌ Crezi că 3 bucle imbricate for i, j, k sunt O(n²) — sunt O(n³)!
❌ Uiți că vector.size() returnează unsigned → scăderi pot da valori mari ciudate.

Checklist final pentru examen¶

✅ Variabile inițializate (int cnt = 0)?
✅ Vectori cu dimensiune suficientă?
✅ Fișiere deschise și închise?
✅ Cazuri limită: n=0, n=1, vector vid?
✅ Overflow? Pentru sume mari, folosește long long!
✅ Respecți formatul de intrare/ieșire cerut (spații, newline)?

🎯 Sfaturi de ultim moment¶

Înainte de examen¶

Rezolvă variante BAC din anii anteriori — structura e foarte similară.
Exersează scrierea de mână — codul pe foaia de examen trebuie să fie lizibil.
Testează mental codul: urmărește valorile variabilelor pas cu pas.

În timpul examenului¶

Citește enunțul de 2 ori — mulți pierd puncte pentru că înțeleg greșit.
Start simplu — rezolvă întâi problemele ușoare (sigur ai punctele).
Comentează codul important — ajuți profesorul să vadă logica.
Verifică la final: citire, inițializări, condiții de oprire, afișare.

Strategia pe puncte¶

La subiectul III (problema de programare):

Algoritm corect + cod complet = 10 puncte.
Algoritm corect + eroare mică = 7-8 puncte.
Idee bună + implementare parțială = 4-5 puncte.
Orice cod care compilează > foaie goală.

NU LĂSA SUBIECTE NEREZOLVATE — scrie măcar pseudocod sau un schelet!

📚 Pentru recapitulare suplimentară¶

pbinfo.ro — probleme categorizate pe capitole BAC.
variantele-bacalaureat.ro — variante oficiale.
VisuAlgo — animații algoritmi.

Breviar realizat conform programei de bacalaureat pentru Informatică, specializarea Matematică-Informatică (Ordin MEN 3237/2021). Toate codurile sunt scrise în C++ — limbaj oficial acceptat la BAC.

Succes la examen! 🍀

← Anterior Informatica clasa 11

Pe această pagină