Vectori — Informatică Liceu

📋

Declararea și inițializarea vectorilor

🏠 Analogie: Vectorul = Bloc de apartamente

Gândeşte-te la un bloc cu N apartamente numerotate de la 1 la N. Fiecare apartament (element) are un număr de apartament (indicele) şi un chiriac (valoarea stocată). Calculatorul ştie exact unde e fiecare apartament fără să caute — acesta e accesul direct O(1).

🔑 v[3] = apartamentul 3 → acces instant
👥 Inserare la mijloc = toți chiriasii de la poziția k în sus se mută un etaj mai sus
🗳 Ștergere = toți chiriasii de deasupra se coboară un etaj

Un vector (tablou unidimensional) este o colecție de elemente de același tip, stocate consecutiv în memorie, accesate prin indice.

// Declarare vector de n elemente întregi (maxim 100000)
int v[100001];  // indexat de la 0 la 100000
int n;          // numărul de elemente folosite efectiv

// Citire din tastatură
cin >> n;
for (int i = 1; i <= n; i++)  // indexare de la 1 (stil BAC)
    cin >> v[i];

// Inițializare cu 0 a întregului tablou
int a[100] = {0};       // toți cu 0
int b[] = {3, 1, 4, 1, 5};  // dimensiune dedusă automat: 5

La BAC, indexarea începe de obicei de la 1: v[1], v[2], ..., v[n]. Tabloul trebuie declarat cu dimensiunea n+1 cel puțin.

Acces: O(1)

v[i] — acces direct la elementul i, indiferent de n

Memorie: O(n)

n elemente × sizeof(tip) octeți consecutiv în RAM

🔁

Parcurgerea vectorilor — operații frecvente

Sumă, minim, maxim — O(n)

int suma = 0, minim = v[1], maxim = v[1];
int pozMin = 1, pozMax = 1;

for (int i = 1; i <= n; i++) {
    suma += v[i];
    if (v[i] < minim) { minim = v[i]; pozMin = i; }
    if (v[i] > maxim) { maxim = v[i]; pozMax = i; }
}

Afișare în ordine inversă

for (int i = n; i >= 1; i--)
    cout << v[i] << " ";

Număr de elemente pare

int nrPare = 0;
for (int i = 1; i <= n; i++)
    if (v[i] % 2 == 0) nrPare++;
cout << "Elemente pare: " << nrPare;

Verificare dacă vectorul este sortat crescător

bool sortat = true;
for (int i = 1; i < n; i++)
    if (v[i] > v[i+1]) { sortat = false; break; }

🔍

Căutare secvențială și binară

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

int cautareSecventiala(int v[], int n, int x) {
    for (int i = 1; i <= n; i++)
        if (v[i] == x) return i;  // returnează poziția
    return -1;  // nu a fost găsit
}
// Funcționează pe vector NESORTAT sau SORTAT
// Best: O(1)  Average: O(n/2)  Worst: O(n)

Căutare binară — O(log n) — doar pe vector SORTAT

int cautareBinara(int v[], int n, int x) {
    int st = 1, dr = n;
    while (st <= dr) {
        int mij = (st + dr) / 2;
        if (v[mij] == x) return mij;  // găsit!
        else if (v[mij] < x) st = mij + 1;  // x e în dreapta
        else dr = mij - 1;              // x e în stânga
    }
    return -1;
}

Trasare căutare binară — x=7, v=[1,3,5,7,9,11,13]:
Pas 1: st=1, dr=7, mij=4 → v[4]=7 → GĂSIT la poziția 4

Atenție la BAC: Dacă problema spune "vector sortat" → folosiți căutare binară O(log n). Pe vector nesortat → căutare secvențială O(n).

🔀

Sortarea vectorilor

Bubble Sort — cel mai cerut la BAC

void bubbleSort(int v[], int n) {
    for (int i = 1; i <= n-1; i++)
        for (int j = 1; j <= n-i; j++)
            if (v[j] > v[j+1])
                swap(v[j], v[j+1]);
    // O(n²) — bun pentru demonstrații, mai lent în practică
}

Selection Sort — explicat pas cu pas

void selectionSort(int v[], int n) {
    for (int i = 1; i <= n-1; i++) {
        int pozMin = i;
        for (int j = i+1; j <= n; j++)
            if (v[j] < v[pozMin]) pozMin = j;
        if (pozMin != i) swap(v[i], v[pozMin]);
    }
    // O(n²) în toate cazurile, O(1) spațiu
}

Insertion Sort — eficient pe date aproape sortate

void insertionSort(int v[], int n) {
    for (int i = 2; i <= n; i++) {
        int cheie = v[i], j = i - 1;
        while (j >= 1 && v[j] > cheie) {
            v[j+1] = v[j];
            j--;
        }
        v[j+1] = cheie;
    }
}

sort() din STL — O(n log n)

#include <algorithm>
sort(v + 1, v + n + 1);              // crescător (v indexat de la 1)
sort(v + 1, v + n + 1, greater<int>());  // descrescător

🔗

Interclasarea (Merge) a doi vectori sortați

Problemă: Dați doi vectori sortați A[1..m] și B[1..n]. Construiți vectorul C[1..m+n] care conține toate elementele, sortat.

void interclasare(int a[], int m, int b[], int n, int c[]) {
    int i = 1, j = 1, k = 0;

    while (i <= m && j <= n) {
        if (a[i] <= b[j]) c[++k] = a[i++];
        else              c[++k] = b[j++];
    }
    // Copiem restul din A sau B
    while (i <= m) c[++k] = a[i++];
    while (j <= n) c[++k] = b[j++];
    // Complexitate: O(m+n) timp și spațiu
}

Exemplu:
A = [1, 3, 5, 7], B = [2, 4, 6]
C = [1, 2, 3, 4, 5, 6, 7] ✅

✏️

Inserare și ștergere elemente

Inserare pe poziția p — O(n)

void insereaza(int v[], int &n, int p, int val) {
    // Deplasăm elementele de la p la n cu o poziție la dreapta
    for (int i = n; i >= p; i--)
        v[i+1] = v[i];
    v[p] = val;
    n++;
}

Ștergere de pe poziția p — O(n)

void sterge(int v[], int &n, int p) {
    // Deplasăm elementele de la p+1 la n cu o poziție la stânga
    for (int i = p; i < n; i++)
        v[i] = v[i+1];
    n--;
}

Complexitate: Inserarea/ștergerea la mijloc = O(n) din cauza deplasărilor. La capăt (stânga sau dreapta) poate fi O(1) dacă ne permitem structuri mai avansate.

📊

Vectori de frecvență (Counting Sort)

Când valorile sunt din domeniu mic [0, K], putem număra aparițiile în O(n+K).

int freq[1001] = {0};  // domeniu valori 0..1000

// Numărăm aparițiile
for (int i = 1; i <= n; i++)
    freq[v[i]]++;

// Afișăm valorile sortate (Counting Sort)
for (int val = 0; val <= 1000; val++)
    for (int j = 0; j < freq[val]; j++)
        cout << val << " ";

// Cel mai frecvent element
int maxFreq = 0, elMaxFreq = -1;
for (int i = 0; i <= 1000; i++)
    if (freq[i] > maxFreq) { maxFreq = freq[i]; elMaxFreq = i; }

Avantaj: Sortare în O(n+K) — mult mai rapid decât O(n log n) când K este mic. Ideal pentru note, cifre, vârste etc.

🧱

Demo Interactiv — Inserare, Ștergere, Căutare

Vectorul de mai jos are 8 sloturi (capacitate maximă). Sloturile goale sunt gri. Apasă butoanele pentru a vedea operațiile pas cu pas.

⚡ Viteză: Normal

Apasă un buton pentru a vedea operația în acțiune.

Inserare: Poziție: Valoare:

Ștergere: Poziție: Căutare: Valoare:

Complexități de reținut:

Inserare la poziția k → mută n−k elemente la dreapta → O(n)
Ștergere de la poziția k → mută n−k elemente la stânga → O(n)
Căutare secvențială → parcurge tot vectorul în cel mai rău caz → O(n)
Acces direct v[i] → instant, nu depinde de n → O(1)

📝

Probleme tip BAC — vectori

Problemă 1 (BAC 2022): Se dă un vector cu n elemente întregi. Afișați elementele distincte în ordinea primei apariții.

Soluție:

bool aparut[1001] = {false};
for (int i = 1; i <= n; i++) {
    if (!aparut[v[i]]) {
        cout << v[i] << " ";
        aparut[v[i]] = true;
    }
}
// O(n) timp, O(K) spațiu

Problemă 2: Dați un vector sortat cu n elemente. Eliminați duplicatele (păstrați câte una din fiecare valoare).

Soluție:

int m = 1;  // noul n după eliminare
for (int i = 2; i <= n; i++)
    if (v[i] != v[i-1])
        v[++m] = v[i];
n = m;  // actualizăm dimensiunea

Problemă 3: Dați n și un vector v[1..n]. Verificați dacă vectorul este o permutare a lui {1, 2, ..., n}.

Soluție:

int freq[100001] = {0};
bool ok = true;
for (int i = 1; i <= n; i++) {
    if (v[i] < 1 || v[i] > n || freq[v[i]] > 0) { ok = false; break; }
    freq[v[i]]++;
}
cout << (ok ? "DA" : "NU");

🔢

Ciurul lui Eratostene

🎯 Ce este Ciurul lui Eratostene?

Ciurul lui Eratostene este algoritmul clasic pentru a găsi toate numerele prime până la un număr dat N, în timp O(N log log N). Este unul dintre cei mai eficienți algoritmi pentru această problemă și apare frecvent la BAC.

Ideea: pornești de la 2, marchezi toți multiplii lui 2 ca neprimi, treci la 3, marchezi multiplii lui 3, și tot așa.

Implementare standard

#include <iostream>
using namespace std;

const int NMAX = 1000001;
bool ciur[NMAX];  // ciur[i] = true dacă i este NEPRIM

void genereazaCiur(int n) {
    ciur[0] = ciur[1] = true;  // 0 și 1 nu sunt prime
    for (int i = 2; (long long)i * i <= n; i++) {
        if (!ciur[i]) {             // i este prim
            for (int j = i * i; j <= n; j += i)  // pornim de la i²
                ciur[j] = true;   // multiplii lui i sunt neprime
        }
    }
}

int main() {
    int n;
    cin >> n;
    genereazaCiur(n);
    for (int i = 2; i <= n; i++)
        if (!ciur[i]) cout << i << " ";
    return 0;
}

De ce pornim de la i² la pasul interior?
Toți multiplii mai mici decât i² (adică 2·i, 3·i, …, (i−1)·i) au fost deja marcați de pași anteriori. Astfel, evităm marcări duplicate.

Numărarea numerelor prime — problemă BAC frecventă

// Câte numere prime există în intervalul [a, b]?
genereazaCiur(b);
int cnt = 0;
for (int i = max(2, a); i <= b; i++)
    if (!ciur[i]) cnt++;
cout << cnt;

Verificare rapidă: este x prim?

// După apelul genereazaCiur(NMAX-1):
bool estePrim(x) { return x >= 2 && !ciur[x]; }

Complexitate timp: O(N log log N)

Practic linear pentru N ≤ 10⁶

Complexitate spațiu: O(N)

Un vector bool de N elemente = N bytes ≈ 1 MB pentru N=10⁶

Atenție la BAC: Declarați ciur[] ca variabilă globală, nu în main(). Un vector de 10⁶ elemente declarat local provoacă stack overflow!

Exemplu — prime până la 20:
Start: [F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F,F]
Marchează multiplii lui 2: 4,6,8,10,12,14,16,18,20
Marchează multiplii lui 3: 9,15
Marchează multiplii lui 5: 25 > 20 → stop
Prime: 2, 3, 5, 7, 11, 13, 17, 19 ✅

🔢

Ciurul lui Eratostene

🎯 Ce este Ciurul lui Eratostene?

Ideea: pornești de la 2, marchezi toți multiplii lui 2 ca neprimi, treci la 3, marchezi multiplii lui 3, și tot așa.

Implementare standard

#include <iostream>
using namespace std;

const int NMAX = 1000001;
bool ciur[NMAX];  // ciur[i] = true dacă i este NEPRIM

void genereazaCiur(int n) {
    ciur[0] = ciur[1] = true;  // 0 și 1 nu sunt prime
    for (int i = 2; (long long)i * i <= n; i++) {
        if (!ciur[i]) {             // i este prim
            for (int j = i * i; j <= n; j += i)  // pornim de la i²
                ciur[j] = true;   // multiplii lui i sunt neprimi
        }
    }
}

int main() {
    int n;
    cin >> n;
    genereazaCiur(n);
    for (int i = 2; i <= n; i++)
        if (!ciur[i]) cout << i << " ";
    return 0;
}

De ce pornim de la i² la pasul interior?
Toți multiplii mai mici decât i² (adică 2·i, 3·i, …, (i−1)·i) au fost deja marcați de pași anteriori. Astfel, evităm marcări duplicate și algoritmul este mai rapid.

Numărarea numerelor prime — problemă BAC frecventă

// Câte numere prime există în intervalul [a, b]?
genereazaCiur(b);
int cnt = 0;
for (int i = max(2, a); i <= b; i++)
    if (!ciur[i]) cnt++;
cout << cnt;

Verificare rapidă: este x prim?

// După apelul genereazaCiur(NMAX-1):
bool estePrim(int x) { return x >= 2 && !ciur[x]; }

Complexitate timp: O(N log log N)

Practic liniar pentru N ≤ 10⁶

Complexitate spațiu: O(N)

Un vector bool de N elemente ≈ 1 MB pentru N=10⁶

Atenție la BAC: Declarați ciur[] ca variabilă globală, nu în main(). Un vector de 10⁶ elemente declarat local provoacă stack overflow!

Exemplu — prime până la 20:
Start: toți false (neprimii vor fi marcați true)
Marchează multiplii lui 2: 4, 6, 8, 10, 12, 14, 16, 18, 20
Marchează multiplii lui 3: 9, 15 (6, 12, 18 deja marcate)
4² = 16 > 20 → stop
Prime găsite: 2, 3, 5, 7, 11, 13, 17, 19 ✅

💪

📦 Vectori

Declararea și inițializarea vectorilor

Parcurgerea vectorilor — operații frecvente

Sumă, minim, maxim — O(n)

Afișare în ordine inversă

Număr de elemente pare

Verificare dacă vectorul este sortat crescător

Căutare secvențială și binară

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

Căutare binară — O(log n) — doar pe vector SORTAT

Sortarea vectorilor

Bubble Sort — cel mai cerut la BAC

Selection Sort — explicat pas cu pas

Insertion Sort — eficient pe date aproape sortate

sort() din STL — O(n log n)

Interclasarea (Merge) a doi vectori sortați

Inserare și ștergere elemente

Inserare pe poziția p — O(n)

Ștergere de pe poziția p — O(n)

Vectori de frecvență (Counting Sort)

Demo Interactiv — Inserare, Ștergere, Căutare

Probleme tip BAC — vectori

Ciurul lui Eratostene

Implementare standard

Numărarea numerelor prime — problemă BAC frecventă

Verificare rapidă: este x prim?

Ciurul lui Eratostene

Implementare standard

Numărarea numerelor prime — problemă BAC frecventă

Verificare rapidă: este x prim?

Exerciții interactive — testează cunoștințele