Tablouri unidimensionale (vectori)

Declararea, inițializarea și prelucrarea tablourilor unidimensionale în rezolvarea problemelor.

Ce este un vector și de ce avem nevoie de el

Imaginează-ți că trebuie să memorezi notele a 30 de elevi. Cu variabile simple ai avea nevoie de n1, n2, ..., n30 — și nu ai putea scrie o buclă care să le parcurgă. Vectorul (tabloul unidimensional) rezolvă exact această problemă: este o colecție de valori de același tip, așezate una după alta în memorie și accesibile prin același nume plus un indice.

În C++, declararea arată așa: int v[100]; — un vector cu 100 de elemente întregi. Elementul de pe poziția i se accesează cu v[i], iar v[i] se comportă exact ca o variabilă obișnuită: îl citești, îl afișezi, îi atribui valori.

Două lucruri esențiale despre indici:

• În C++, indexarea începe de la 0: primul element al lui int v[100] este v[0], iar ultimul este v[99]. În pseudocod și în multe probleme, indexarea se face de la 1 — citește mereu enunțul ca să vezi convenția folosită. Mulți programatori începători declară int v[101]; și folosesc doar pozițiile 1..n, ca să lucreze natural de la 1.
• Accesarea unei poziții din afara vectorului (de exemplu v[100] la un vector de 100 de elemente) NU este semnalată de compilator — programul poate afișa valori aiurea sau se poate opri brusc. Este o eroare de logică, nu de sintaxă.

Dimensiunea declarată este capacitatea maximă; numărul de elemente efectiv folosite, notat de obicei n, se citește separat și poate fi mai mic.

Citirea, afișarea și parcurgerea unui vector

Aproape orice problemă cu vectori începe la fel: se citește n (numărul de elemente), apoi cele n elemente, cu o buclă for:

• citire: for (i = 0; i < n; i++) cin >> v[i];
• afișare: for (i = 0; i < n; i++) cout << v[i] << ' ';

Acest tipar se numește parcurgerea vectorului: vizitezi fiecare element, o singură dată, în ordine. Toate prelucrările din acest capitol sunt variații ale parcurgerii — diferă doar ce faci cu fiecare element vizitat.

Detalii care aduc puncte:

• dacă lucrezi cu indici de la 0, condiția este i < n (strict); dacă lucrezi de la 1, condiția este i <= n. Amestecarea lor (i <= n cu start de la 0) atinge o poziție în plus — eroare off-by-one clasică;
• parcurgerea inversă se face cu for (i = n - 1; i >= 0; i--) — utilă la afișarea elementelor în ordine inversă;
• se poate parcurge și din 2 în 2 (i += 2) sau doar o porțiune a vectorului (de la p la q).

Diferența dintre poziție și valoare trebuie să îți fie mereu limpede: v[3] = 7 înseamnă că pe poziția 3 se află valoarea 7. Întrebarea „care este poziția maximului?” cere indicele, nu valoarea — iar la examen cele două se punctează diferit. Când problema cere „elementele de pe poziții pare”, verifici i % 2 == 0; când cere „elementele cu valori pare”, verifici v[i] % 2 == 0 — sunt condiții complet diferite!

Suma, produsul, media și numărarea

Prelucrările de bază combină parcurgerea cu un acumulator — o variabilă care adună rezultatul pe măsură ce avansezi:

• Suma: s = 0; for (i = 0; i < n; i++) s += v[i]; — inițializarea cu 0 este obligatorie, pentru că 0 este elementul neutru la adunare;
• Produsul: p = 1; for (i = 0; i < n; i++) p *= v[i]; — aici inițializarea corectă este 1 (elementul neutru la înmulțire); dacă pornești de la 0, produsul rămâne 0 orice ai înmulți;
• Media aritmetică: media = suma împărțită la n. Capcană: dacă s și n sunt amândouă întregi, s / n face împărțire întreagă și pierde zecimalele — corect este (float) s / n sau s * 1.0 / n;
• Numărarea elementelor cu o proprietate: k = 0; for (...) if (conditie) k++; — de exemplu, câte elemente sunt pare, câte sunt negative, câte sunt egale cu o valoare dată.

Un șablon înrudit: suma doar a elementelor care îndeplinesc o condiție (suma elementelor impare, suma celor de pe poziții pare) — combină acumulatorul cu un if în interiorul buclei.

Greșeala care strică tot: inițializarea acumulatorului în interiorul buclei în loc de înaintea ei. Dacă scrii s = 0 în corpul for-ului, suma se resetează la fiecare pas și rezultatul final este doar ultimul element. Inițializarea se face o singură dată, înainte de buclă.

Căutarea secvențială și minim/maxim

Căutarea secvențială răspunde la întrebarea: apare valoarea x în vector, și dacă da, pe ce poziție? Parcurgi vectorul și compari fiecare element cu x. Șablonul robust folosește o variabilă santinelă pentru poziție:

poz = -1; for (i = 0; i < n; i++) if (v[i] == x) { poz = i; break; }

Dacă la final poz a rămas -1, valoarea nu există în vector — nu uita acest caz, enunțurile cer aproape mereu un mesaj special pentru el. break-ul oprește căutarea la prima apariție; fără break, poz va păstra ultima apariție — citește atent ce cere problema.

Minimul și maximul: inițializezi cu primul element, apoi compari cu restul:

max = v[0]; for (i = 1; i < n; i++) if (v[i] > max) max = v[i];

De ce nu inițializăm cu 0? Dacă toate elementele sunt negative, maximul „calculat” ar fi 0 — o valoare care nici măcar nu există în vector. Inițializarea cu primul element este singura mereu corectă.

Pentru poziția maximului, memorezi indicele în loc de valoare: pmax = 0; if (v[i] > v[pmax]) pmax = i; La egalitate de valori, condiția cu > păstrează prima poziție a maximului, iar >= ar păstra-o pe ultima — încă un detaliu pe care enunțurile îl exploatează.

Toate aceste prelucrări fac o singură trecere prin vector — n comparații pentru n elemente. La clasa a VII-a nu ai nevoie de mai mult; căutarea binară și sortările vin în clasa a VIII-a.

Probleme aplicative tipice

Subiectele combină șabloanele de bază în enunțuri scurte. Iată tiparele care apar cel mai des și ideea de rezolvare pentru fiecare:

• Verificarea unei proprietăți pentru toate elementele („toate elementele sunt pare?”): pornești cu un steag ok = 1 și îl faci 0 la primul element care încalcă proprietatea. Dacă după parcurgere ok e tot 1, proprietatea e adevărată pentru toate. Greșeala tipică: să resetezi steagul înapoi la 1 în buclă — odată găsit un contraexemplu, verdictul rămâne negativ;
• Existența unui element cu o proprietate („există măcar un element negativ?”): invers — pornești cu gasit = 0 și îl faci 1 când găsești;
• Interschimbarea a două elemente v[i] și v[j]: cu variabilă auxiliară, exact ca la variabilele simple: aux = v[i]; v[i] = v[j]; v[j] = aux; Cu acest pas se construiește răsturnarea vectorului: interschimbi v[i] cu v[n-1-i] pentru i de la 0 la jumătatea vectorului — dacă mergi până la capăt, vectorul revine la forma inițială pentru că fiecare pereche se schimbă de două ori;
• Deplasarea și ștergerea: ștergerea elementului de pe poziția p se face mutând toate elementele următoare cu o poziție la stânga (v[i] = v[i+1]) și micșorând n; inserarea — invers, mutare la dreapta începând de la capăt și n crește;
• Compararea a doi vectori: sunt egali dacă au aceeași lungime și v[i] == w[i] pentru fiecare i — se verifică element cu element, tot cu un steag.

Strategia de examen: recunoaște șablonul din enunț (sumă? numărare? maxim? căutare? steag?), scrie-l corect, apoi adaptează condiția din if la cerința exactă.

Test — 6 întrebări ca la examen