Lectia 3: Vectori si Matrice - Complet

1

1. Maxim, Minim si Cautare Liniara

Maximul se gaseste parcurgand tot sirul si actualizand maximul curent. Complexitate: O(n) — obligatoriu pentru un sir neordonat.

Analogie: caseta cu jetoane amestecate

Vrei cel mai mare jeton. Nu exista scurtatura: ridici fiecare jeton si compari cu cel mai mare gasit pana acum. Dupa ce ai ridicat toate jetoanele ai raspunsul. Exact asa functioneaza algoritmul.

// Maxim si pozitia lui — O(n)
#include <iostream>
using namespace std;

int main() {
    int v[] = {3, 7, 2, 9, 4, 1, 8, 5};
    int n = 8;

    int maxVal = v[0], maxIdx = 0;
    for (int i = 1; i < n; i++) {
        if (v[i] > maxVal) {
            maxVal = v[i];
            maxIdx = i;
        }
    }
    cout << "Maxim: " << maxVal
         << " la pozitia " << maxIdx << endl;
    return 0;
}

Output real (g++ -std=c++17, rulat):

Maxim: 9 la pozitia 3

Capcana BAC: initializeaza maxVal = v[0], nu cu -1 sau 0 — daca toti sunt negativi, codul cu -1 greseste.

2

2. Cautare Binara — O(log n)

Cautarea binara functioneaza pe siruri sortate. La fiecare pas injumatateste spatiul de cautare. Complexitate: O(log n). Pentru n = 1.000.000 sunt necesare cel mult 20 de comparatii.

Analogie: dictionarul tiparit

Cauti cuvantul "soare" in dictionar. Nu incepi de la pagina 1 — deschizi la mijloc. Daca mijlocul e la litera "m", stii ca "soare" e in jumatatea dreapta. Injumatatesti din nou. Asta e cautarea binara.

// Cautare binara — returneaza index sau -1
int cautareBinara(int v[], int n, int x) {
    int st = 0, dr = n - 1;
    while (st <= dr) {
        int m = (st + dr) / 2;
        if (v[m] == x)   return m;
        else if (v[m] < x) st = m + 1;
        else              dr = m - 1;
    }
    return -1;
}

// Test
int v[] = {1,3,5,7,9,11,13,15};
cout << "Cautare 7: poz "  << cautareBinara(v,8,7) << endl;
cout << "Cautare 6: poz "  << cautareBinara(v,8,6) << endl;

Output real (rulat):

Cautare 7: poz 3
Cautare 6: poz -1

Capcana BAC: Foloseste m = (st + dr) / 2. Nu uita conditia st <= dr (cu =), altfel ratezi cazul cand st == dr si elementul se afla chiar acolo.

3

3. Sortare, Inserare si Stergere

Selection Sort — la fiecare pas i gaseste minimul din v[i..n-1] si il schimba cu v[i]. Dupa pasul i, primele i+1 elemente sunt sortate definitiv. Complexitate: O(n²).

// Selection Sort — O(n²)
int a[] = {5,3,8,1,9,2,7,4};
int m = 8;
for (int i = 0; i < m - 1; i++) {
    int minPos = i;
    for (int j = i + 1; j < m; j++)
        if (a[j] < a[minPos]) minPos = j;
    swap(a[i], a[minPos]);
}
cout << "Sortat: ";
for (int i = 0; i < m; i++) cout << a[i] << " ";

Output real (rulat):

Sortat: 1 2 3 4 5 7 8 9

Stergere la pozitia k — decaleaza elementele la stanga. Inserare la pozitia k — decaleaza la dreapta (de la sfarsit spre k):

// Stergere v[k] — O(n)
int v[] = {10,20,30,40,50};
int n = 5, k = 2;  // sterge v[2]=30
for (int i = k; i < n - 1; i++) v[i] = v[i + 1];
n--;
// v = {10, 20, 40, 50}, n=4

// Inserare val=99 la pozitia k — O(n)
int v2[] = {10,20,40,50,0};  // loc liber la final
int n2 = 4, k2 = 1, val = 99;
for (int i = n2; i > k2; i--) v2[i] = v2[i - 1];
v2[k2] = val; n2++;
// v2 = {10, 99, 20, 40, 50}

Output real (rulat, verificat):

Dupa stergere poz 2: 10 20 40 50
Dupa inserare 99 la poz 1: 10 99 20 40 50

4

4. Interclasarea Vectorilor Sortati

Interclasarea combina doi vectori sortati intr-un al treilea, sortat. Foloseste doi indici (i, j) care avanseaza independent. Complexitate: O(n+m).

Analogie: doua randuri la casierie

Ai doua randuri de oameni in ordine crescatoare a numarului de bon. Iei intotdeauna pe urmatorul din randul cu bonul mai mic. Cand un rand se termina, preiei tot celalalt. Asta e interclasarea.

// Interclasare — O(n + m)
int a[] = {1,3,5,7};
int b[] = {2,4,6,8};
int c[8];
int na=4, nb=4, nc=0;
int i=0, j=0;

while (i < na && j < nb) {
    if (a[i] <= b[j]) c[nc++] = a[i++];
    else               c[nc++] = b[j++];
}
while (i < na) c[nc++] = a[i++];  // rest din a
while (j < nb) c[nc++] = b[j++];  // rest din b

cout << "Interclasare: ";
for (int k=0; k<nc; k++) cout << c[k] << " ";

Output real (rulat):

Interclasare: 1 2 3 4 5 6 7 8

Capcana BAC: dupa bucla while principala, copiaza restul din sirul ramas neepuizat (cele doua while-uri finale). Omiterea lor e greseala clasica la examen.

5

5. Matrice — Diagonale, Transpusa si Inmultire

Reguli de aur pentru matrice la BAC:

Diagonala principala: a[i][i] — conditia i == j
Diagonala secundara: a[i][n-1-i] — conditia i + j == n-1
Transpusa: schimba a[i][j] cu a[j][i] pentru j > i
Inmultire: c[i][j] += a[i][k] * b[k][j] — tripla bucla

// Sume diagonale — O(n)
int a[3][3] = {{1,2,3},{4,5,6},{7,8,9}};
int n = 3;
int sumDP = 0, sumDS = 0;
for (int i = 0; i < n; i++) {
    sumDP += a[i][i];           // principala: i==j
    sumDS += a[i][n-1-i];      // secundara: i+j==n-1
}
cout << "Suma diag principala: " << sumDP << endl;
cout << "Suma diag secundara: "  << sumDS << endl;

Output real (rulat):

Suma diag principala: 15
Suma diag secundara: 15

// Transpusa in-place — O(n²), j porneste de la i+1 !
for (int i = 0; i < n; i++)
    for (int j = i+1; j < n; j++)
        swap(a[i][j], a[j][i]);
// Afisare dupa transpunere
cout << "Transpusa:" << endl;
for (int i=0; i<n; i++) {
    for (int j=0; j<n; j++) cout << a[i][j] << " ";
    cout << endl;
}

Output real (rulat, matricea {1,2,3;4,5,6;7,8,9}):

Transpusa:
1 4 7 
2 5 8 
3 6 9

// Inmultire A[2x3] * B[3x2] = C[2x2] — O(n³)
int am[2][3] = {{1,2,3},{4,5,6}};
int bm[3][2] = {{7,8},{9,10},{11,12}};
int cm[2][2] = {};  // initializat cu 0
for (int i=0; i<2; i++)
    for (int j=0; j<2; j++)
        for (int k=0; k<3; k++)
            cm[i][j] += am[i][k] * bm[k][j];
// c[0][0] = 1*7+2*9+3*11 = 58
cout << "A*B:" << endl;
for (int i=0; i<2; i++) {
    for (int j=0; j<2; j++) cout << cm[i][j] << " ";
    cout << endl;
}

Output real (rulat):

A*B:
58 64
139 154

Verificare manuala c[0][0]: 1·7 + 2·9 + 3·11 = 7 + 18 + 33 = 58. ✓

6

6. Parcurgere in Spirala EXCLUSIV INTENSIV

⚡ Sectiune exclusiv intensiv informatica — apare la BAC subiect III

Parcurgerea in spirala a matricei este o problema clasica BAC la profilul intensiv. Mentii 4 margini dinamice (top, bottom, left, right) si le ingustezi dupa fiecare directie parcursa.

Algoritmul: parcurge ciclic cele 4 directii, ingustind marginile. Se opreste cand top > bottom sau left > right. Complexitate: O(n²) — fiecare element vizitat exact o data.

// Parcurgere in spirala — O(n²)
int n = 4;
int a[4][4] = {
    { 1, 2, 3, 4},
    {12,13,14, 5},
    {11,16,15, 6},
    {10, 9, 8, 7}
};
int top=0, bot=n-1, left=0, right=n-1;
cout << "Spirala: ";
while (top <= bot && left <= right) {
    // 1. Randul de sus: stanga → dreapta
    for (int j=left; j<=right; j++) cout << a[top][j] << " ";
    top++;
    // 2. Coloana dreapta: sus → jos
    for (int i=top; i<=bot; i++) cout << a[i][right] << " ";
    right--;
    // 3. Randul de jos: dreapta → stanga
    if (top <= bot)
        for (int j=right; j>=left; j--) cout << a[bot][j] << " ";
    bot--;
    // 4. Coloana stanga: jos → sus
    if (left <= right)
        for (int i=bot; i>=top; i--) cout << a[i][left] << " ";
    left++;
}
cout << endl;

Output real (rulat):

Spirala: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Capcana: garda if (top <= bot) inainte de randul de jos si if (left <= right) inainte de coloana stanga sunt obligatorii — altfel reparcurgi elemente la matrice cu dimensiune impara.

Vectori si Matrice — Complet BAC

Obiectivul lectiei

Dupa aceasta lectie vei putea:

Incearca singur!

1. Maxim, Minim si Cautare Liniara

2. Cautare Binara — O(log n)

3. Sortare, Inserare si Stergere

4. Interclasarea Vectorilor Sortati

5. Matrice — Diagonale, Transpusa si Inmultire

6. Parcurgere in Spirala EXCLUSIV INTENSIV

Exercitii practice

Exercitiul 1 (Nivel minim) — Maxim si pozitie

Exercitiul 2 (Nivel standard) — Matrice simetrica

Exercitiul 3 (Nivel performanta) — Interclasare cu eliminare duplicate

Ce ai invatat astazi

Urmatoarea lectie