Algoritmi și structuri de date

Elevii aprofundează conceptele de algoritm, structuri de date și metode de rezolvare a problemelor.

Algoritmul și proprietățile lui

Un algoritm este o succesiune finită și ordonată de pași prin care, pornind de la date de intrare, obținem date de ieșire — adică rezultatul problemei. Nu orice listă de pași e algoritm: trebuie respectate proprietățile algoritmilor, care se cer exact așa la evaluare:

• Finitudine — algoritmul se termină după un număr finit de pași. Un program care rulează la nesfârșit (buclă infinită) încalcă exact această proprietate.
• Generalitate — rezolvă o clasă întreagă de probleme, nu un singur caz. Un algoritm care calculează suma DOAR pentru numerele 3 și 5 nu e general; unul care calculează suma oricăror două numere citite, da.
• Claritate (determinism) — fiecare pas e precis definit, fără ambiguități: la aceleași date de intrare obținem mereu același rezultat.

Confuzia clasică: elevii cred că „algoritmul e programul”. Nu — algoritmul este ideea de rezolvare, iar programul este algoritmul scris într-un limbaj de programare. Același algoritm poate fi scris în pseudocod, în C++ sau în Pascal.

Algoritmii se reprezintă prin pseudocod (limbaj apropiat de cel natural, cu cuvinte-cheie ca „citește”, „scrie”, „dacă... atunci”, „cât timp”) sau prin schemă logică (desen cu blocuri: paralelogram pentru citire/scriere, dreptunghi pentru atribuiri, romb pentru decizii).

Tablouri unidimensionale (vectori)

Când avem multe valori de același tip (notele unei clase, temperaturile unei luni), nu declarăm 30 de variabile separate — folosim un tablou unidimensional, numit și vector: o înșiruire de elemente de același tip, așezate una după alta în memorie și accesate printr-un indice.

În pseudocod scriem v[1], v[2], ..., v[n]. În C++ declarăm int v[100]; și indicii pornesc de la 0, nu de la 1 — sursa clasică de greșeli când treci din pseudocod în cod.

Operațiile fundamentale, care apar în aproape orice subiect:

• Parcurgerea: vizităm fiecare element cu un contor — pentru i de la 1 la n execută ceva cu v[i].
• Suma și media: inițializăm s cu 0 ÎNAINTE de buclă, apoi adunăm s = s + v[i]. Dacă uiți inițializarea, rezultatul e imprevizibil.
• Maximul/minimul: inițializăm max cu primul element (v[1]), nu cu 0! Dacă toate elementele sunt negative și pornești de la 0, răspunsul iese greșit — capcană frecventă de punctaj.
• Numărarea elementelor care îndeplinesc o condiție (pare, pozitive, divizibile cu 5): un contor care crește doar când condiția e adevărată.

Regula de aur: indicele trebuie să rămână mereu în interiorul limitelor tabloului; accesarea lui v[n+1] este o eroare, chiar dacă uneori programul pare că merge.

Tablouri bidimensionale (matrice)

O matrice este un tablou cu două dimensiuni — un tabel cu linii și coloane. Elementul de pe linia i și coloana j se notează a[i][j]. Gândește-te la o tablă de șah: fiecare pătrățel e identificat de linia și coloana lui.

Parcurgerea pe linii folosește două bucle imbricate: pentru fiecare linie i, parcurgem toate coloanele j. Dacă inversăm buclele (j exterior, i interior), parcurgem pe coloane. Ordinea buclelor schimbă ordinea vizitării — întrebare tipică de urmărire a execuției.

La matricea pătratică (același număr de linii și coloane, n×n) apar noțiuni cerute des:

• Diagonala principală: elementele cu i = j (din colțul stânga-sus în dreapta-jos).
• Diagonala secundară: elementele cu i + j = n + 1 (dacă indexăm de la 1) sau i + j = n − 1 (dacă indexăm de la 0).
• Zonele deasupra/dedesubtul diagonalei principale: i < j, respectiv i > j.

Greșeala clasică e confundarea celor două diagonale sau scrierea condiției diagonalei secundare cu indexarea greșită. Verifică mereu de unde pornesc indicii în enunț!

Prelucrări uzuale: suma elementelor de pe o linie dată, maximul de pe fiecare coloană, numărarea elementelor pare din matrice — toate sunt combinații de bucle imbricate cu operațiile învățate la vectori.

Subprograme: proceduri și funcții

Când o bucată de cod se repetă sau rezolvă o sarcină bine delimitată, o izolăm într-un subprogram. Avantajele: codul devine mai scurt, mai ușor de citit și de corectat — principiul modularizării.

Două tipuri de subprograme:

• Funcția — primește date, calculează și returnează un rezultat prin numele ei. În C++: int suma(int a, int b) { return a + b; }. Rezultatul se folosește direct în expresii: s = suma(3, 4).
• Procedura (în C++, funcție de tip void) — execută o acțiune (de exemplu afișează ceva), dar nu returnează o valoare prin nume.

Vocabular care se punctează exact:

• Parametri formali — cei din definiția subprogramului (a și b de mai sus).
• Parametri efectivi (actuali) — valorile concrete de la apel (3 și 4).

Parametrii formali și cei efectivi trebuie să corespundă ca număr, ordine și tip.

• Variabile locale — declarate în interiorul subprogramului; există doar cât acesta rulează și nu sunt vizibile în afara lui.
• Variabile globale — declarate în afara oricărui subprogram; vizibile peste tot.

Confuzia frecventă: elevii cred că modificarea unui parametru transmis prin valoare schimbă și variabila de la apel. Nu! Prin valoare se lucrează pe o copie — originalul rămâne neschimbat.

Recursivitate – primii pași

Un subprogram este recursiv dacă se apelează pe el însuși. Pare magie, dar e doar o altă formă de repetiție: în loc de buclă, problema mare se reduce la o problemă mai mică de același fel.

Orice recursivitate corectă are OBLIGATORIU două părți:

• Cazul de bază — situația simplă în care răspunsul se dă direct, fără alt apel. El oprește recursivitatea.
• Cazul general — reducerea problemei: apelul cu o valoare „mai mică”, care se apropie de cazul de bază.

Exemplul clasic, factorialul: n! = 1 · 2 · ... · n.

• Caz de bază: dacă n = 0, rezultatul e 1.
• Caz general: n! = n · (n−1)!

În C++: int fact(int n) { if (n == 0) return 1; return n * fact(n - 1); }

Cum se execută fact(3)? Se „desface” în 3 · fact(2), apoi 2 · fact(1), apoi 1 · fact(0), care returnează 1; abia apoi rezultatele se înmulțesc la întoarcere: 1, 1, 2, 6. Urmărirea acestor apeluri în ambele sensuri (coborâre și întoarcere) e exact ce se cere la exerciții.

Greșeala fatală: lipsa cazului de bază sau un caz de bază care nu e atins niciodată — apelurile nu se mai opresc și programul se blochează (depășire de stivă). Dacă fact ar fi apelat cu n negativ, condiția n == 0 nu s-ar îndeplini niciodată.

Eficiența algoritmilor

Două programe pot da același rezultat corect, dar unul termină într-o secundă și celălalt în ore. Eficiența unui algoritm măsoară cât de bine folosește resursele: timpul de execuție (numărul de operații efectuate) și memoria ocupată.

La nivelul clasei a VIII-a comparăm algoritmii prin numărul aproximativ de pași în funcție de n (dimensiunea datelor):

• Parcurgerea unui vector cu n elemente: aproximativ n pași — timp liniar.
• Două bucle imbricate de la 1 la n (de exemplu parcurgerea unei matrice n×n sau compararea fiecărei perechi): aproximativ n·n pași — timp pătratic; la n = 1000 înseamnă un milion de operații.
• Înjumătățirea repetată a intervalului (ca la căutarea binară): mult mai puțini pași — la n = 1000, doar vreo 10 înjumătățiri.

Exemplu concret: verificarea dacă un număr n este prim. Varianta naivă testează toți divizorii de la 2 la n−1. Varianta eficientă se oprește la radical din n, pentru că dacă n are un divizor mai mare decât radicalul, are obligatoriu și unul mai mic. Ambele sunt corecte; a doua e vizibil mai rapidă la numere mari.

De reținut: eficiența NU înseamnă cod mai scurt. Un program de trei rânduri poate fi mai lent decât unul de zece. Contează câte operații execută, nu câte rânduri are. La subiecte, când ți se cere un algoritm „eficient”, se așteaptă evitarea calculelor inutile — de exemplu să nu parcurgi vectorul de mai multe ori când ajunge o singură trecere.

Test — 6 întrebări ca la examen