Teorie
Vectori (tablouri unidimensionale) la atestatul de informatică
Citirea și parcurgerea unui vector, filtrarea cu doi indici, inserarea și ștergerea pe poziția k, căutarea, maximul condiționat și sortarea — cu problemele de atestat în care apar.
6
minute de citit
10
secțiuni
59
probleme rezolvate legate
Actualizat pe .
Pe această pagină
- Citirea unui vector
- Tehnica 1 — Filtrare cu doi indici
- Tehnica 2 — Contor sau flag pentru cazul gol
- Tehnica 3 — Căutare
- Tehnica 4 — Maxim, minim, sumă (acumulator)
- Tehnica 5 — Inserare și ștergere
- Sortare și date structurate
- Greșeli care se repetă
- Unde exersezi mai departe
- Toate problemele din această categorie
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
0lan - 1. Ultimul element ex[n - 1], nux[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; cuintvalorile s-ar trunchia.
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ă.
Exersează pe subiecte reale
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.
Exersează pe subiecte reale
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 1Dacă enunțul cere toate aparițiile, nu pui break. Dacă cere doar prima, îl pui.
Exersează pe subiecte reale
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.
Exersează pe subiecte reale
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.
Exersează pe subiecte reale
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;Exersează pe subiecte reale
Greșeli care se repetă
- Afișarea până la
nîn loc demdupă o filtrare — apar valori nedefinite din memorie - Folosirea lui
kdirect 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];cuncitit — nu e C++ standard- Vectori paraleli în loc de
struct— numele ajung pe mediile greșite la sortare intîn loc dedoublecând enunțul spune „numere reale"
Mai departe
Unde exersezi mai departe
Tehnicile de mai sus (doi indici, acumulator, inserare/ștergere) se fixează doar rezolvând multe probleme scurte, una după alta.
Pentru asta, pbinfo.ro e cea mai bună resursă românească: peste 2500 de probleme de informatică cu evaluator automat, și o trimiți la testat direct din browser. E construită pentru olimpiadă și bacalaureat, deci se completează cu ce găsești aici — noi acoperim subiectele de atestat, cu rezolvări scrise.
Dacă dai și bacalaureatul la informatică, subiectebac.ro adună variantele oficiale de BAC la informatică din 2009 încoace, cu bareme, separate pe specializare și pe limbaj. Baremul îți arată cum se punctează o rezolvare, nu doar dacă e corectă.
Toate problemele din această categorie
Fiecare are rezolvare completă în C++, explicată pas cu pas.
59Arată toate problemele rezolvateAscunde lista59 programare
- Arbore dat prin vectorul de tați: rădăcina, nodurile cu cei mai mulți fii și frunzele (subprogramul pozitie)
- Cel mai mare divizor comun al celor n numere citite
- Cel mai mic element cu suma cifrelor impară și numărul lui de apariții
- Cel mai mic multiplu de k dintre două elemente consecutive, în fișier
- Cel mai mic palindrom din vector și ultima poziție pe care apare
- Cele mai mari două elemente ale unui vector, în ordine descrescătoare
- Cele mai mici trei elemente care au exact d divizori
- Cmmdc și cmmmc pentru fiecare pereche de elemente vecine
- Câte elemente sunt divizibile cu suma propriilor cifre
- Căutare binară printre numerele de trei cifre, ordonate descrescător (construire și cautare)
- Căutarea unei valori într-un vector și afișarea pozițiilor pe care apare
- De câte ori apar două elemente egale pe poziții consecutive
- Elementele comune ale unui tablou crescător și ale unuia descrescător (subprogramul tablou)
- Elementele cu aceeași ultimă cifră ca ultimul element
- Elementele divizibile cu numărul lor de apariții în vector
- Elementele oglindite — inversul lor apare și el în vector
- Elementele prime care au cifre distincte
- Elementele unui vector care au suma cifrelor număr prim
- Elementul care apare de cele mai multe ori într-un vector
- Elevii ordonați descrescător după medie, folosind date structurate
- Eliminarea nodurilor de grad minim și numărul muchiilor rămase (nrElem1 și sumaElem)
- Inserarea părții întregi a mediei între oricare două elemente vecine
- Inserarea valorii 0 după fiecare element par
- Inversarea cifrelor, fără prima, la numerele cu peste 4 divizori (inversareCifre și nrDivizori)
- Lungimea maximă a unei secvențe strict crescătoare
- Media aritmetică a elementelor cu toate cifrele distincte
- Numere cu prima cifră pătrat perfect, ordonate descrescător (p_cifra recursiv și sortare)
- Numerele de două cifre care nu apar într-un șir
- Numerele de trei cifre care apar de exact două ori într-un fișier, descrescător
- Numărarea elementelor din intervalul [a,b] și vectorul celor din afara lui
- Ordonarea crescătoare după numărul de cifre, apoi după valoare
- Ordonarea descrescătoare după ultima cifră, apoi după valoare
- Perechi de vecini cu aceeași sumă a cifrelor
- Perechi de vecini în care primul e mai mic decât suma cifrelor celui de-al doilea
- Poziția primului element impar dintr-un vector
- Poziția unui element în vectorul ordonat, fără a-l ordona
- Poziția unui element într-un vector ordonat — căutare binară
- Rădăcina și matricea de adiacență a unui arbore dat prin vectorul de tați
- Sortarea descrescătoare a unor numere reale cu poziția maximului (citeste și pozmax)
- Suma maximă a unei secvențe de elemente pozitive consecutive
- Suma numerelor complexe cu modul întreg (struct complexi: modul și suma)
- Sumele parțiale ale unui vector, scrise în fișier
- Să se afişeze maximul valorilor negative
- Să se afişeze numerele perfecte din vector
- Să se afişeze numărul elementelor care sunt numere palindrom
- Să se afişeze numărul valorilor prime din vector
- Să se calculeze şi să se afişeze cel mai mare divizor comun al elementelor vectorului
- Să se elimine elementele nule din vector şi să se afişeze vectorul astfel obţinut
- Să se genereze şi să se afişeze un alt vector Y care conţine elementele pare din vectorul X
- Să se insereze pe poziţia k, o valoare a citită de la tastatură
- Să se înlocuiască fiecare element cu media aritmetică a celorlalte n–1 elemente
- Să se şteargă elementul de pe poziţia k (citită de la tastatură)
- Toate secvențele care încep și se termină cu valoarea k (subprogramul secv_tablou)
- Vectorul cu reprezentările în baza 2 ale elementelor
- Vectorul sumelor cifrelor elementelor
- Verificarea dacă un vector este o permutare a mulțimii {1, 2, …, n}
- Înjumătățirea numerelor cu toate cifrele pare (subprogramele verif și modif)
- Ștergerea din vector a numerelor cu cifre de aceeași paritate (sterge și cif)
- Ștergerea tuturor aparițiilor ultimului element
Alte pagini de teorie