Bacalaureatul la Informatică se apropie, iar emoțiile cresc odată cu numărul de algoritmi pe care trebuie să îi stăpânești. Dacă simți că te îneci în sortări, căutări și prelucrări de șiruri, nu te îngrijora – ești exact acolo unde trebuie să fii. În acest articol, vei găsi o colecție de algoritmi clasici C++, cu subiecte rezolvate și explicații pas cu pas, special gândite pentru a te ajuta să obții punctaj maxim la examen. Fiecare algoritm este însoțit de exemple concrete și de sfaturi practice, astfel încât să poți trece cu încredere peste orice problemă.
1. Sortarea prin selecție (Selection Sort)
Unul dintre cei mai simpli și mai frecvent întâlniți algoritmi la Bacalaureatul de Informatică este sortarea prin selecție. Ideea de bază: se caută elementul minim dintr-o porțiune a vectorului și se plasează la începutul acelei porțiuni. Algoritmul parcurge vectorul de la stânga la dreapta, pentru fiecare poziție i găsind minimul în intervalul [i, n-1] și interschimbându-l cu elementul de pe poziția i.
- Complexitate: O(n²) – potrivit pentru vectori mici (sub 1000 de elemente).
- Avantaj: Ușor de implementat și de reținut.
- Exemplu: Pentru vectorul [5, 2, 8, 1], după prima iterație obținem [1, 2, 8, 5].
Implementare simplă: for (int i = 0; i < n-1; i++) { int minIdx = i; for (int j = i+1; j < n; j++) if (v[j] < v[minIdx]) minIdx = j; swap(v[i], v[minIdx]); }
2. Sortarea prin inserție (Insertion Sort)
Un alt algoritm clasic, adesea prezent în subiectele de bac, este sortarea prin inserție. Metoda simulează modul în care un jucător de cărți își ordonează cărțile în mână: se ia pe rând fiecare element și se inserează în poziția corectă dintre elementele deja sortate. Este eficient pentru vectori aproape sortați și are o implementare intuitivă.
- Complexitate: O(n²) în cazul mediu, dar O(n) pentru vectori deja sortați.
- Exemplu: Pentru [3, 1, 4, 2], primul pas: [1, 3, 4, 2] (1 se inserează în fața lui 3).
Sfaturi pentru bac: Învață să scrii acest algoritm din memorie, pentru că apare frecvent la cerințe de tip „scrieți pseudocodul” sau „implementați în C++”.
3. Căutarea binară (Binary Search)
Căutarea binară este un algoritm fundamental pe care orice absolvent de informatică trebuie să îl stăpânească. Se aplică doar pe vectori sortați și funcționează prin împărțirea repetată a intervalului de căutare în două jumătăți. La fiecare pas, se compară elementul din mijloc cu valoarea căutată și se decide în ce jumătate se continuă căutarea.
- Complexitate: O(log n) – extrem de rapid.
- Condiție esențială: Vectorul trebuie să fie sortat crescător (sau descrescător, după caz).
- Exemplu: Căutarea valorii 7 în [1, 3, 5, 7, 9] – se începe cu mijlocul 5, apoi se trece la jumătatea dreaptă.
Implementare: int st = 0, dr = n-1; while (st <= dr) { int mid = (st + dr) / 2; if (v[mid] == x) return mid; else if (v[mid] < x) st = mid + 1; else dr = mid - 1; }
4. Prelucrarea șirurilor de caractere (Stringuri)
La Bacalaureat, problemele cu șiruri de caractere sunt nelipsite. De la numărarea aparițiilor unui caracter, la eliminarea duplicatelor sau verificarea palindroamelor – toate sunt algoritmi care testează înțelegerea operațiilor pe stringuri. În C++, șirurile pot fi tratate ca vectori de caractere (char[]) sau cu clasa string.
- Exemplu clasic: Verificarea dacă un șir este palindrom (se citește la fel de la stânga la dreapta și invers).
- Algoritm: Se compară caracterul de la început cu cel de la sfârșit, avansând spre centru.
Problema rezolvată: „Se dă un șir. Să se afișeze toate cuvintele care încep cu vocală.” – Se parcurge șirul, se identifică începutul fiecărui cuvânt și se verifică prima literă.
5. Algoritmi pe matrici (parcurgere, diagonale, bordare)
Matricile sunt un subiect vast și frecvent întâlnit la subiectele de bac. Pe lângă parcurgerea simplă (linie cu linie), trebuie să știi să lucrezi cu diagonalele principale și secundare, să bordezi o matrice (adaugi un rând sau o coloană de valori constante) și să aplici diverse transformări.
- Parcurgerea în spirală – apare uneori la probleme de dificultate medie.
- Diagonale: Diagonala principală: i == j; diagonala secundară: i + j == n – 1.
- Bordarea: Se creează o matrice cu o marjă de valori sentinelă (de exemplu, 0) pentru a evita verificările de margine.
Exemplu: „Înlocuiți toate elementele de pe diagonala principală cu suma elementelor de pe linia respectivă.”
6. Algoritmul lui Euclid (cmmdc) și numere prime
Problemele cu numere prime și cel mai mare divizor comun sunt nelipsite din Bacalaureatul de Informatică. Algoritmul lui Euclid pentru cmmdc este extrem de eficient și se scrie în câteva linii. De asemenea, testarea primalității (prin divizori până la rădăcina pătrată) este un algoritm de bază.
- Cmmdc: while (b) { int r = a % b; a = b; b = r; } return a;
- Ciurul lui Eratostene – pentru a genera toate numerele prime până la o limită dată (de exemplu, 10^6).
Problema rezolvată: „Se citesc n numere. Să se afișeze câte dintre ele sunt prime.” – Se scrie o funcție bool isPrime(int x) și se contorizează.
7. Prelucrarea fișierelor (citire/scriere)
La Bacalaureat, multe subiecte implică lucrul cu fișiere text. Trebuie să știi să deschizi un fișier, să citești datele (numere, șiruri), să le prelucrezi și să scrii rezultatul într-un alt fișier. De cele mai multe ori, se folosesc ifstream și ofstream din biblioteca
- Citire: ifstream fin("date.in"); fin >> n; fin.close();
- Scriere: ofstream fout("date.out"); fout << rezultat; fout.close();
- Atenție: Verifică întotdeauna dacă fișierul s-a deschis corect (!fin.fail()).
Exemplu: „Se dau două fișiere cu numere. Să se creeze un al treilea fișier care conține numerele comune.” – Se citesc ambele fișiere în vectori, apoi se aplică o căutare sau o sortare.
8. Recursivitatea – aplicații clasice
Recursivitatea este un concept care apare frecvent la Bacalaureat, fie sub forma unor funcții recursive simple (factorial, suma cifrelor), fie în algoritmi mai complecși (Turnurile din Hanoi, generarea permutărilor). Învață să identifici cazul de bază și pasul de recurență.
- Factorial: int fact(int n) { if (n <= 1) return 1; return n * fact(n-1); }
- Suma cifrelor: int sumCif(int n) { if (n == 0) return 0; return n % 10 + sumCif(n / 10); }
Problema rezolvată: „Să se genereze toate permutările mulțimii {1, 2, ..., n}.” – Se folosește backtracking, care este o formă avansată de recursivitate.
Concluzie
Stăpânirea acestor algoritmi clasici C++ îți va oferi o bază solidă pentru a aborda cu încredere orice subiect de Bacalaureat la Informatică. Nu uita să exersezi cât mai mult, scriind cod de mână și testându-l pe exemple simple. Dacă simți că ai nevoie de mai multă practică sau de explicații detaliate, edubro.ro este aici pentru tine! Platforma noastră gratuită, bazată pe inteligență artificială, îți oferă exerciții interactive, lecții personalizate și feedback instantaneu. Învață mai eficient, în ritmul tău, și transformă-ți emoțiile în încredere!
Accesează edubro.ro acum și începe să exersezi algoritmii C++ pentru Bacalaureat!