Algoritmi și structuri de date

Aprofundarea conceptelor algoritmice și a structurilor de date fundamentale folosite în rezolvarea problemelor.

Tablouri unidimensionale și bidimensionale

Un tablou este o structură de date care păstrează, sub un singur nume, mai multe valori de același tip, așezate la poziții numerotate. Poziția unei valori se numește indice.

• Tabloul unidimensional (vectorul) — o singură linie de valori: `v[0], v[1], ..., v[n-1]`. În C++ indexarea începe de la 0, capcană clasică: ultimul element al unui vector cu n elemente este `v[n-1]`, nu `v[n]`.
• Tabloul bidimensional (matricea) — valori organizate pe linii și coloane: `a[i][j]` este elementul de pe linia i, coloana j.

La o matrice pătratică de dimensiune n contează pozițiile speciale, cerute constant la BAC:

• diagonala principală: elementele cu `i == j`;
• diagonala secundară: elementele cu `i + j == n - 1`;
• deasupra diagonalei principale: `i < j`; sub ea: `i > j`.

Parcurgerea completă a unei matrice se face cu două instrucțiuni for imbricate: cea exterioară fixează linia, cea interioară trece prin coloanele liniei respective. Dacă inversezi rolurile, parcurgi pe coloane — rezultatul e același ca mulțime de elemente, dar ordinea vizitării diferă, ceea ce contează la probleme de afișare.

Șiruri de caractere

Un șir de caractere este un vector ale cărui elemente sunt caractere, terminat în C++ (stil C) cu caracterul nul `\0` — un marcaj invizibil care spune unde se termină șirul. Lungimea utilă a șirului nu include acest terminator.

Funcțiile clasice din biblioteca `cstring`, cerute la examen:

• strlen(s) — returnează numărul de caractere până la terminator (nu dimensiunea vectorului!);
• strcpy(d, s) — copiază șirul s peste d;
• strcat(d, s) — concatenează: lipește s la sfârșitul lui d;
• strcmp(a, b) — compară lexicografic: returnează 0 dacă șirurile sunt egale, o valoare negativă dacă a este înaintea lui b în ordine lexicografică, pozitivă altfel;
• strchr(s, c) — caută prima apariție a caracterului c și returnează adresa ei (sau NULL).

Confuzia clasică: `strcmp(a, b) == 0` înseamnă șiruri egale, nu diferite — mulți elevi citesc 0 ca „fals” și inversează condiția. Alt detaliu de punctaj: compararea a două șiruri cu operatorul `==` compară adresele, nu conținutul.

Caracterele au coduri ASCII consecutive pe litere: transformarea literă mare → literă mică se face adunând diferența `'a' - 'A'` (32).

Subprograme: funcții și proceduri

Un subprogram este o porțiune de program cu nume propriu, care rezolvă o sarcină bine delimitată și poate fi apelată ori de câte ori e nevoie. Avantaje: evită duplicarea codului, ușurează testarea și permite lucrul modular.

În pseudocodul de BAC și în C++ distingem:

• funcții care returnează o valoare (în C++ au tip de retur diferit de `void`) — apelul lor apare într-o expresie;
• proceduri (funcții `void`) — execută acțiuni, nu returnează nimic prin nume.

Termeni pe care examenul îi cere exact:

• parametri formali — cei din antetul subprogramului, nume locale folosite în definiție;
• parametri efectivi (actuali) — valorile sau variabilele din apel.

Transmiterea parametrilor:

• prin valoare — subprogramul primește o copie; modificările NU se văd în programul apelant;
• prin referință (în C++ cu `&` în antet) — subprogramul lucrează direct pe variabila originală; modificările rămân după apel.

O variabilă locală există doar pe durata execuției subprogramului; o variabilă globală e vizibilă în tot programul. Dacă o variabilă locală are același nume cu una globală, în interiorul subprogramului locala o ascunde pe cea globală — sursă frecventă de răspunsuri greșite la subiectele de urmărire a codului.

Recursivitate

Un subprogram este recursiv dacă se apelează pe el însuși, direct sau indirect. Orice recursivitate corectă are două componente obligatorii:

• cazul de bază — condiția de oprire, pentru care rezultatul se dă direct, fără alt apel;
• cazul general — problema se reduce la o instanță mai mică a ei însăși.

Fără caz de bază (sau cu o reducere care nu se apropie de el), apelurile se acumulează la nesfârșit și programul se oprește cu depășire de stivă (stack overflow), pentru că fiecare apel ocupă memorie pe stiva de execuție.

Exemple canonice: factorialul (`f(n) = n * f(n-1)`, cu `f(0) = 1`), suma cifrelor unui număr, cel mai mare divizor comun prin resturi (`cmmdc(a, b) = cmmdc(b, a % b)`, cu `cmmdc(a, 0) = a`).

La subiectele de urmărire, cheia este ordinea efectelor față de apelul recursiv: o afișare pusă înainte de apel produce valorile în ordinea coborârii (de exemplu cifrele unui număr de la ultima către prima), iar una pusă după apel produce valorile în ordinea întoarcerii din apeluri — adesea exact ordinea inversă. Elevii care ignoră acest detaliu inversează sistematic rezultatul.

Orice algoritm recursiv poate fi rescris iterativ (cu cicluri), uneori cu o stivă gestionată explicit; alegerea ține de claritate și de consumul de memorie.

Complexitatea algoritmilor — noțiuni introductive

Complexitatea timp a unui algoritm măsoară cum crește numărul de operații în funcție de dimensiunea datelor de intrare n — nu timpul în secunde, care depinde de calculator. Se exprimă cu notația O (ordinul de mărime), reținând doar termenul dominant, fără constante:

• O(1) — timp constant: accesul la un element de tablou prin indice;
• O(log n) — logaritmic: căutarea binară, care înjumătățește zona de căutare la fiecare pas;
• O(n) — liniar: parcurgerea unui vector, căutarea secvențială;
• O(n log n) — sortările eficiente prin interclasare sau QuickSort în cazul mediu;
• O(n²) — pătratic: două cicluri imbricate pe același vector, sortările elementare (selecție, inserție, bule).

Practic, diferența e uriașă: pentru n = 1.000.000, un algoritm O(n²) face aproximativ 10¹² operații (minute sau ore), pe când unul O(n log n) face în jur de 2·10⁷ (o fracțiune de secundă).

Greșeala tipică: a confunda complexitatea cu numărul de linii de cod. Un program scurt cu două for-uri imbricate este O(n²); unul lung, dar cu o singură parcurgere, rămâne O(n). Există și complexitate spațiu — memoria suplimentară folosită — care se analizează cu aceeași notație.

Algoritmi de căutare și sortare

Căutarea secvențială verifică elementele pe rând, de la primul la ultimul: funcționează pe orice vector, sortat sau nu, în timp O(n).

Căutarea binară cere obligatoriu un vector sortat: compară valoarea căutată cu elementul din mijloc, apoi continuă doar în jumătatea care mai poate conține valoarea. La fiecare pas zona se înjumătățește, deci timpul este O(log n). Condiția de vector sortat este exact detaliul pe care grilele îl testează — aplicată pe un vector nesortat, căutarea binară dă rezultate greșite.

Sortări elementare, toate O(n²):

• selecție — la pasul i se caută minimul din zona nesortată și se aduce pe poziția i; face puține interschimbări (cel mult n-1);
• inserție — fiecare element nou se inserează la locul lui în zona deja sortată din stânga; foarte rapidă pe vectori aproape sortați;
• metoda bulelor (bubble sort) — compară și interschimbă perechi vecine, repetând parcurgerile până când nu mai are loc nicio interschimbare.

Sortări eficiente, O(n log n):

• interclasarea (MergeSort) — împarte vectorul în două jumătăți, le sortează recursiv, apoi le interclasează; garantează O(n log n) în orice caz, dar folosește memorie suplimentară;
• QuickSort — alege un pivot și rearanjează elementele în mai mici, respectiv mai mari decât pivotul; în medie O(n log n), dar în cazul cel mai defavorabil O(n²).

Operația de interclasare a doi vectori deja sortați într-unul singur sortat se face într-o singură parcurgere paralelă, în timp O(m + n) — subiect frecvent de sine stătător la BAC.

Test — 6 întrebări ca la examen