Parcurgerea vectorilor la BAC: indici și vecini

Parcurgerea unui vector înseamnă să vizitezi elementele lui într-o ordine stabilită și să aplici o operație fiecăruia sau unor perechi de elemente. La BAC, multe erori nu provin din operația matematică, ci din confuzia dintre indice și valoare ori din accesarea unei poziții din afara tabloului.

Vom folosi un vector de numere întregi cu cel puțin un element și cel mult o mie de elemente. În program, indicii încep de la zero. Pe foaia de examen, poți întâlni și numerotarea de la unu; important este să păstrezi aceeași convenție în toate limitele și afișările. Exersează recunoașterea convenției și pe subiecte de BAC.

Indicele și valoarea elementului

În vectorul cu valorile opt, minus trei, opt și cinci, elementul de indice unu are valoarea minus trei. Indicele spune unde se află elementul, iar valoarea spune ce este memorat acolo. Două elemente pot avea aceeași valoare și indici diferiți.

Indice în C++	Poziție numerotată de la unu	Valoare
0	1	8
1	2	-3
2	3	8
3	4	5

Dacă enunțul cere elementele de pe poziții pare, trebuie să verifici poziția, nu valoarea. În convenția pozițiilor numerotate de la unu, acestea corespund indicilor unu, trei, cinci și așa mai departe. Dacă enunțul cere elementele cu valori pare, verifici valoarea memorată.

Această diferență schimbă rezultatul exemplului. Pe poziții pare se află minus trei și cinci. Valorile pare sunt cele două apariții ale lui opt. Citirea atentă a substantivului de lângă „pare” este un pas al rezolvării, nu doar o chestiune de exprimare.

Limitele unei parcurgeri complete

Pentru un vector cu un număr dat de elemente și indici de la zero, primul indice valid este zero, iar ultimul este cu unu mai mic decât numărul elementelor. Bucla completă începe de la zero și continuă cât timp indicele este strict mai mic decât numărul elementelor.

Dacă folosești o comparație care include egalitatea cu numărul elementelor, apare un acces în afara porțiunii valide. Uneori programul pare să funcționeze, dar acest comportament nu dovedește corectitudinea. Citirea unei valori neinițializate sau accesarea memoriei greșite nu reprezintă o soluție acceptabilă.

Capacitatea tabloului și numărul elementelor folosite sunt lucruri diferite. Un tablou declarat cu o mie de poziții poate conține în problema curentă doar șapte elemente relevante. Parcurgerea cerută se oprește după cele șapte, nu după întreaga capacitate declarată.

Suma și numărarea folosesc actualizări diferite

Dacă vrei suma valorilor pozitive, adaugi valoarea fiecărui element pozitiv. Dacă vrei numărul lor, adaugi unu. Ambele cerințe pot avea aceeași condiție de selecție, dar acumulatori cu sens diferit.

Pentru vectorul minus doi, patru, zero și șapte, suma valorilor pozitive este unsprezece, iar numărul lor este doi. Un test care conține numai valori unu poate ascunde confuzia, fiindcă suma și numărul aparițiilor coincid. Alege exemple cu valori diferite pentru a verifica implementarea.

La o sumă, ține cont și de limitele datelor. Dacă fiecare element este de cel mult un miliard în valoare absolută și sunt o mie de elemente, suma poate depăși capacitatea unui întreg semnat pe 32 de biți. Un tip mai larg poate fi necesar chiar dacă fiecare element încape în tipul obișnuit.

Perechi vecine și limite adaptate

Pentru a compara fiecare element cu următorul, indicele curent trebuie să se oprească înaintea ultimului element. Ultimul nu are un succesor în interiorul vectorului. Numărul perechilor vecine este cu unu mai mic decât numărul elementelor, pentru un vector nevid.

O alternativă este să începi de la al doilea element și să îl compari pe fiecare cu precedentul. Atunci indicele precedent este întotdeauna valid. Cele două variante verifică aceleași perechi, dar limitele nu pot fi amestecate.

Vom număra perechile strict crescătoare: valoarea din dreapta este mai mare decât cea din stânga. Pentru vectorul patru, patru, șapte, doi, cinci, perechile acceptate sunt patru–șapte și doi–cinci. Perechea patru–patru nu este strict crescătoare.

Program C++ complet

#include <iostream>
using namespace std;

int main() {
    int n, v[1000];
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> v[i];

    int crescatoare = 0;
    for (int i = 1; i < n; ++i)
        if (v[i - 1] < v[i]) ++crescatoare;

    cout << crescatoare;
    return 0;
}

Pentru un singur element, a doua buclă nu se execută și rezultatul este zero. Aceasta este valoarea corectă, deoarece nu există nicio pereche de elemente vecine. Nu este nevoie să inventezi un element anterior sau următor pentru a trata cazul.

Programul are timp liniar în numărul elementelor: o parcurgere pentru citire și una pentru comparații. Două parcurgeri consecutive nu înseamnă timp pătratic. Memoria ocupată de tablou depinde de capacitatea declarată; pentru problema generalizată, stocarea elementelor este proporțională cu lungimea șirului.

Când poți evita memorarea vectorului

Cerința despre perechi vecine poate fi rezolvată și citind valorile succesiv. Păstrezi valoarea precedentă, citești valoarea curentă, compari și apoi actualizezi precedenta. Nu ai nevoie de toate elementele simultan.

Totuși, dacă o cerință ulterioară solicită acces repetat la poziții diferite, tabloul poate fi necesar. Alegerea dintre memorare și prelucrare imediată pornește de la operațiile cerute. Nu adăuga o structură doar fiindcă enunțul folosește cuvântul „șir”, dar nici nu renunța la ea înainte să verifici toate cerințele.

Această analiză a dependențelor este mai utilă decât memorarea unei singure bucle universale. Poți aplica metoda de învățare prin înțelegere: explică ce informație din trecut este necesară la pasul curent.

Parcurgerea inversă

Dacă vrei să afișezi elementele în ordine inversă, începi de la ultimul indice valid și scazi indicele până la zero inclusiv. Pentru contorul care trebuie să treacă apoi la minus unu, un tip întreg semnat este alegerea simplă în această schemă.

O variabilă fără semn nu devine negativă după scăderea de la zero. De aceea, o condiție care așteaptă ca ea să fie mai mică decât zero nu va funcționa cum te-ai aștepta. Verifică tipul contorului împreună cu direcția parcurgerii.

Afișarea inversă nu modifică vectorul. Dacă cerința solicită inversarea efectivă a elementelor, trebuie să schimbi valorile perechilor simetrice sau să construiești un alt tablou. Verbul din cerință decide dacă este suficientă doar ordinea afișării.

Exerciții cu răspunsuri explicate

Vectorul trei, unu, doi, doi, cinci: câte perechi vecine sunt strict crescătoare? Două: unu–doi și doi–cinci. Egalitatea dintre cele două valori doi nu este acceptată.

Vectorul minus patru, minus doi, zero: care sunt pozițiile pare, numerotate de la unu? Numai poziția a doua, cu valoarea minus doi. Toate trei valorile sunt pare, dar aceasta este o altă proprietate.

Un vector are opt elemente, cu indici de la zero. Ultimul indice valid este șapte. Pentru comparația cu următorul, ultimul indice curent permis este șase.

Un vector conține un singur element. Suma este valoarea lui, numărul perechilor vecine este zero, iar afișarea inversă produce tot acel element. Același caz-limită trebuie interpretat în funcție de operația cerută.

Întrebări frecvente

Pot numerota elementele de la unu în C++?

Poți alege să folosești acele poziții dintr-un tablou suficient de mare, dar trebuie să adaptezi declarația și toate limitele. Nu combina această convenție cu o buclă care presupune indici de la zero.

De ce două bucle nu înseamnă automat timp pătratic?

Dacă rulează una după alta, numărul pașilor se adună. Timpul pătratic apare în anumite parcurgeri imbricate, când pentru fiecare element se execută din nou o parcurgere de lungime comparabilă.

Cum verific rapid limitele?

Scrie primul și ultimul indice accesat de fiecare expresie, inclusiv de vecini. Testează un singur element și două elemente. Pentru feedback pe aceste verificări, poți apela la un profesor de informatică.