Recursivitate pe vector la BAC: prima valoare negativă

Căutarea recursivă într-un vector poate fi formulată ca o problemă despre un sufix: găsește prima valoare negativă începând de la o anumită poziție. La BAC, această formulare te ajută să identifici cazul de oprire, sensul rezultatului și argumentul care se modifică la fiecare apel.

Lecția privește recursivitatea și subprogramele de la matematică-informatică. Vom returna indicele primei valori negative sau minus unu dacă nu există. Indicii din funcție pornesc de la zero, iar programul principal transformă indicele într-o poziție numerotată de la unu pentru afișare. Această convenție trebuie adaptată la cerința de BAC pe care o rezolvi.

Definește exact problema fiecărui apel

Funcția primește vectorul, numărul elementelor și poziția de la care începe căutarea. Ea nu caută obligatoriu în întregul vector la fiecare apel. Caută în porțiunea dintre poziția curentă și ultimul element valid.

Pentru primul apel, poziția curentă este zero, deci porțiunea analizată este întregul vector. Dacă primul element nu este negativ, problema se reduce la sufixul care începe cu al doilea element.

Rezultatul rămâne un indice în vectorul original, nu o distanță față de începutul sufixului. Această alegere simplifică revenirea: apelul exterior poate returna direct rezultatul apelului interior, fără să adauge un număr de poziții.

Două opriri diferite

Dacă poziția curentă este egală cu numărul elementelor, sufixul este vid. Nu există niciun element de verificat, deci funcția returnează minus unu. Această condiție trebuie verificată înainte să accesezi vectorul la poziția curentă.

Dacă poziția este validă și elementul ei este negativ, ai găsit prima valoare negativă din sufix. Returnezi poziția imediat. Nu trebuie să continui căutarea, deoarece orice element ulterior ar avea o poziție mai mare.

Doar dacă niciuna dintre aceste opriri nu se aplică, funcția apelează aceeași căutare pentru poziția următoare. Fiecare ramură are astfel o semnificație clară: absență, succes sau reducerea problemei.

Program C++ complet

Programul citește o lungime între zero și o mie, apoi elementele întregi. Afișează poziția primei valori negative, numerotată de la unu, sau zero dacă nu există nicio valoare negativă. Zero la afișare este o convenție separată de minus unu folosit în funcție.

#include <iostream>
using namespace std;

int primaNegativa(const int v[], int n, int i) {
    if (i == n) return -1;
    if (v[i] < 0) return i;
    return primaNegativa(v, n, i + 1);
}

int main() {
    int n, v[1000];
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> v[i];
    int pozitie = primaNegativa(v, n, 0);
    if (pozitie == -1)
        cout << 0;
    else
        cout << pozitie + 1;
    return 0;
}

Funcția presupune că poziția inițială se află între zero și n, inclusiv. Apelul din programul principal respectă această condiție. În interior, poziția crește cu unu și nu depășește n, fiindcă acolo intervine oprirea.

Exemplu cu succes după câteva apeluri

Pentru vectorul patru, zero, minus trei, minus unu, primul apel verifică indicele zero. Valoarea patru nu este negativă, deci se trece la indicele unu. Valoarea zero nu este nici ea negativă.

La indicele doi apare minus trei. Funcția returnează doi, iar toate apelurile care așteptau returnează aceeași valoare. Programul principal afișează trei, deoarece pozițiile cerute la ieșire sunt numerotate de la unu.

Indice curent	Element	Decizie
0	4	Continuă cu indicele 1
1	0	Continuă cu indicele 2
2	-3	Returnează 2

Elementul minus unu nu mai este vizitat. Cerința privește prima valoare negativă, iar găsirea uneia la o poziție mai mică face inutilă inspectarea restului vectorului.

Exemplu fără rezultat

Pentru vectorul doi, zero, șapte, funcția vizitează indicii zero, unu și doi, fără succes. Următorul apel primește indicele trei, egal cu lungimea. El returnează minus unu fără să citească un element de pe acea poziție.

Valoarea minus unu se propagă înapoi prin toate apelurile. Programul principal o recunoaște și afișează zero. Nu afișează pur și simplu ultimul indice verificat și nu confundă absența cu prima poziție.

Pentru vectorul vid, chiar primul apel are poziția zero egală cu lungimea zero. Rezultatul este imediat minus unu. Aceeași condiție tratează natural lipsa elementelor, fără acces la o valoare neinițializată.

De ce rezultatul apelului trebuie returnat

O funcție care are rezultat întreg trebuie să furnizeze acel rezultat pe fiecare traseu relevant. Simplul apel recursiv, scris fără returnare, nu transmite automat valoarea lui către apelul exterior.

În schema noastră, rezultatul problemei mai mici este exact rezultatul problemei curente, deoarece elementul curent a fost deja respins. De aceea, returnăm direct valoarea apelului pentru următorul sufix.

Dacă s-ar cere numărul valorilor negative, ar trebui să combinăm rezultatele prin adunare, nu să ne oprim la primul succes. Dacă s-ar cere ultima poziție negativă, ordinea căutării sau regula de combinare ar trebui schimbată. Semnificația rezultatului dictează forma recurenței.

Prima poziție nu este valoarea minimă

Pentru vectorul doi, minus unu, minus nouă, prima valoare negativă este minus unu, aflată pe poziția a doua. Minimul este minus nouă, dar cerința nu solicită minimul.

Un algoritm care păstrează cea mai mică valoare ar rezolva altă problemă. La fel, un algoritm care actualizează poziția la fiecare valoare negativă ar găsi ultima apariție, nu prima.

Scrie propoziția pe care trebuie să o respecte rezultatul: este o poziție cu element negativ și nu există o poziție mai mică, în zona căutată, cu aceeași proprietate. Această descriere clarifică ce trebuie demonstrat.

Timpul și memoria apelurilor

Dacă prima valoare este negativă, funcția se oprește după o singură verificare. Dacă nu există valori negative, parcurge toate elementele și ajunge la apelul pentru sufixul vid. Timpul în cel mai nefavorabil caz este proporțional cu lungimea vectorului.

Apelurile anterioare pot rămâne active până la obținerea rezultatului, deci analiza obișnuită atribuie memorie de stivă proporțională cu numărul apelurilor. Nu te baza pe o posibilă optimizare a compilatorului pentru a declara memoria constantă.

O variantă iterativă poate rezolva aceeași cerință cu memorie auxiliară constantă. Scopul exercițiului recursiv este să formulezi și să urmărești corect problema mai mică, nu să presupui că recursivitatea este automat mai eficientă.

Cum verifici soluția pe hârtie

Desenează vectorul cu indicii deasupra valorilor. Pentru fiecare apel, marchează începutul sufixului. Nu copia tot vectorul la fiecare pas; datele sunt aceleași, iar zona de căutare se restrânge.

Notează rezultatul găsit în cel mai adânc apel și propagă-l înapoi. Această metodă sprijină înțelegerea recursivității și face vizibilă diferența dintre valoare, indice și poziție afișată.

Exerciții cu răspunsuri

Vectorul este -5, 2, -8. Funcția returnează indicele zero, iar programul afișează poziția unu. Restul vectorului nu trebuie căutat.

Vectorul este 0, 0, 0. Nu există valori negative. Funcția returnează minus unu, iar programul afișează zero.

Vectorul este 7, 3, -2. Funcția returnează doi, iar programul afișează trei. Ultimul element poate fi primul care respectă proprietatea.

Întrebări frecvente

Zero este considerat negativ?

Nu. Condiția este strict mai mic decât zero. Dacă enunțul ar cere valori nepozitive, zero ar trebui inclus printr-o altă comparație.

De ce verific limita înaintea elementului?

La indicele egal cu lungimea nu există un element valid. Accesarea lui înaintea cazului de bază ar încălca limitele vectorului logic.

Cum adaptez căutarea la altă proprietate?

Păstrezi contractul despre prima poziție și schimbi testul elementului, dacă restul cerinței rămâne identic. Pentru o analiză a variantei tale, poți consulta un profesor de informatică.