Vectori (tablouri unidimensionale) la atestatul de informatică

După numere și divizibilitate, vectorii sunt al doilea grup mare de subiecte la proba de programare. Vestea bună: aproape toate problemele se reduc la cinci tehnici, iar odată ce le recunoști, enunțurile încep să semene între ele.

Citirea unui vector

Forma standard, pe care o scrii aproape identic la fiecare problemă:

int n;
cin >> n;

int x[100];
for (int i = 0; i < n; i++) cin >> x[i];

Trei lucruri de reținut:

• Indicii merg de la 0 la n - 1. Ultimul element e x[n - 1], nu x[n].
• Dimensiunea declarată e fixă. int x[n]; nu e C++ standard — se declară o rezervă acoperitoare (100), independent de câte elemente se citesc efectiv.
• Tipul urmează enunțul. „Numere reale" înseamnă double; cu int valorile s-ar trunchia.

Poziții vs. indici. Enunțurile numără pozițiile de la 1, C++ numără indicii de la 0. Poziția k corespunde indicelui k - 1. Verifică întotdeauna exemplul din enunț — e una dintre cele mai frecvente surse de puncte pierdute.

Tehnica 1 — Filtrare cu doi indici

Cea mai folosită structură din toată categoria. Construiești un vector nou din elementele care trec un test, folosind doi indici care avansează independent:

int m = 0;                          // cate elemente are Y
for (int i = 0; i < n; i++)
    if (x[i] % 2 == 0) y[m++] = x[i];

i parcurge tot, m avansează doar când chiar scrii ceva. La final m e și lungimea lui Y, și răspunsul la „există vreunul?".

Afișarea merge până la m, niciodată până la n — restul lui Y conține valori nedefinite.

Poți filtra și pe loc, rescriind în același vector: m rămâne mereu în urma lui i, deci nu suprascrii niciodată un element nedeschis încă.

Probleme: vectorul elementelor pare · eliminarea elementelor nule · elementele din afara unui interval

Tehnica 2 — Contor sau flag pentru cazul gol

Aproape toate enunțurile cer un mesaj special când nu s-a găsit nimic. Nu poți ști asta decât după ce ai parcurs tot vectorul:

bool gasit = false;
for (...)
    if (...) { /* ... */ gasit = true; }
if (!gasit) cout << "NU EXISTA";

Când enunțul cere câte sunt, contorul înlocuiește flagul — îți dă și răspunsul, și informația „există sau nu". Iar când filtrezi pe loc, comparația m < n spune singură dacă s-a eliminat ceva, fără variabilă în plus.

Probleme: numărarea valorilor prime · numerele perfecte din vector · numere palindrom

Tehnica 3 — Căutare

Parcurgi și compari. Ce diferă de la o problemă la alta e ce afișezi și dacă te oprești:

for (int i = 0; i < n; i++)
    if (x[i] == a) cout << " " << i + 1;   // pozitii numerotate de la 1

Dacă enunțul cere toate aparițiile, nu pui break. Dacă cere doar prima, îl pui.

Probleme: căutarea unei valori și pozițiile ei

Tehnica 4 — Maxim, minim, sumă (acumulator)

Aici stă capcana cea mai des întâlnită: cu ce valoare pornești?

Reflexul int maxim = 0; e greșit de câte ori valorile căutate pot fi negative. Iar maxim = x[0]; e greșit când primul element nu îndeplinește condiția cerută.

Soluția generală — pornești de la primul element care se califică:

if (!gasit || x[i] > maxim) maxim = x[i];

La prima potrivire, !gasit e adevărat și inițializează corect. De la a doua încolo contează doar comparația. Același flag spune la final dacă a existat vreun rezultat.

Pentru sume, acumulatorul pornește de la 0; pentru produse, de la 1.

Probleme: maximul valorilor negative · înlocuirea cu media celorlalte · c.m.m.d.c. al elementelor

Trucul sumei totale. Când ai nevoie de „suma celorlalte elemente", n-ai nevoie de bucle imbricate: suma - x[i] dă exact asta, dintr-o scădere.

Tehnica 5 — Inserare și ștergere

Un vector nu are operații de inserare sau ștergere. Elementele stau lipite în memorie, deci trebuie deplasate manual. Regula care decide totul e sensul parcurgerii:

// STERGERE de pe pozitia k -> tragi la stanga, parcurgi de la stanga
for (int i = k - 1; i < n - 1; i++) x[i] = x[i + 1];
n--;

// INSERARE pe pozitia k -> impingi la dreapta, parcurgi de la dreapta
for (int i = n; i >= k; i--) x[i] = x[i - 1];
x[k - 1] = a;
n++;

Când muți la dreapta, pornești de la dreapta. Când muți la stânga, pornești de la stânga. Dacă inversezi, primul element mutat suprascrie următorul și se copiază aceeași valoare peste tot.

Nu uita n-- / n++ — lungimea vectorului s-a schimbat. Și validează poziția înainte de orice modificare: k trebuie să fie între 1 și n, deci și k < 1 e invalid, nu doar k > n.

Probleme: ștergerea elementului de pe poziția k · inserarea pe poziția k

Sortare și date structurate

Pentru n mic (la atestat, mereu sub 100), sortarea prin selecție e suficientă și e cea mai ușor de scris corect din memorie:

for (int i = 0; i < n - 1; i++)
    for (int j = i + 1; j < n; j++)
        if (x[j] > x[i]) {          // ">" = descrescator, "<" = crescator
            int aux = x[i];
            x[i] = x[j];
            x[j] = aux;
        }

Variabila aux e obligatorie: fără ea, prima atribuire distruge valoarea pe care urma s-o muți.

Când fiecare element are mai multe informații care trebuie să rămână împreună (nume + medie), se folosește struct. Astfel interschimbarea mută structura întreagă și e imposibil ca numele să ajungă pe media altcuiva:

struct Elev {
    char nume[30];
    double media;
};

Elev aux = e[i];
e[i] = e[j];
e[j] = aux;

Probleme: elevii ordonați după medie

Greșeli care se repetă

• Afișarea până la n în loc de m după o filtrare — apar valori nedefinite din memorie
• Folosirea lui k direct ca indice, fără - 1 — se lucrează pe elementul vecin
• Sensul greșit de parcurgere la inserare/ștergere — un element se copiază peste tot
• int maxim = 0; când valorile pot fi negative
• Uitarea lui n++ / n-- după inserare sau ștergere
• int x[n]; cu n citit — nu e C++ standard
• Vectori paraleli în loc de struct — numele ajung pe mediile greșite la sortare
• int în loc de double când enunțul spune „numere reale"

Toate problemele din această categorie

Fiecare are rezolvare completă în C++, explicată pas cu pas.