Noțiunea de algoritm

Un algoritm este o listă de pași prin care rezolvi o problemă. Pașii trebuie să fie clari, să poată fi făcuți și să se termine. De pildă, pentru a afla câte creioane sunt în două cutii, numeri creioanele din prima cutie, le numeri pe cele din a doua și aduni cele două numere. Numerele de la care pornești sunt date de intrare; suma este rezultatul sau data de ieșire.

Un pas precum „fă repede calculul” nu este destul de precis: nu spune ce calcul trebuie făcut. Un algoritm bun indică operația și ordinea pașilor. Dacă prima cutie are 3 creioane și a doua 4, parcurgi pașii: notezi 3, notezi 4, calculezi $3+4=7$ și comunici rezultatul, 7 creioane. Poți urmări fiecare pas fără să ghicești ce urmează.

Aceeași listă trebuie să funcționeze și pentru 5 și 2 creioane, nu numai pentru 3 și 4. Aceasta este ideea de generalitate: schimbi datele, dar păstrezi metoda. Algoritmul nu este același lucru cu programul. Poți descrie pașii prin cuvinte, desene sau pseudocod; un program îi scrie într-un limbaj pe care calculatorul îl poate executa.

Pentru a verifica o propunere, întreabă: „Știu de unde pornesc? Este limpede fiecare pas? Obțin răspunsul? Mă opresc?” Dacă răspunsul la una dintre întrebări este „nu”, metoda trebuie completată.

Exemplu rezolvat — cum afli dacă un număr este par. Algoritmul are trei pași:

1. Citești numărul, de exemplu 18.
2. Împarți numărul la 2 și te uiți la rest.
3. Dacă restul este 0, spui „par”; dacă este 1, spui „impar”.

Pentru 18 obții $18=2\cdot 9+0$, deci restul este 0 și răspunsul este „par”. Pentru 7 obții $7=2\cdot 3+1$, restul este 1 și răspunsul este „impar”. Algoritmul are o dată de intrare (numărul), o dată de ieșire (cuvântul „par” sau „impar”), pașii sunt clari și se termină după trei pași pentru orice număr natural. Același algoritm poate fi desenat cu blocuri legate prin săgeți sau scris în pseudocod, iar rezultatul rămâne același.

Un algoritm este descris prin date de intrare, prelucrări și date de ieșire. Proprietățile lui sunt: finitudinea (se termină după un număr finit de pași pentru orice intrare admisă), precizia (fiecare instrucțiune este neambiguă și executabilă), generalitatea (rezolvă toată clasa de probleme, nu un singur caz), corectitudinea (rezultatul respectă enunțul) și, în plus, eficiența (folosește puțin timp și puțină memorie). Corectitudinea se verifică urmărind valorile variabilelor pas cu pas, nu printr-un singur exemplu favorabil. Algoritmul este independent de limbaj: același algoritm se poate exprima în limbaj natural, prin schemă logică, în pseudocod sau într-un limbaj de programare.

Exemplul 1 — suma a două numere. Algoritmul: citește $a$ și $b$; calculează $s\leftarrow a+b$; afișează $s$. Implementarea în C++:

#include <iostream>
using namespace std;
int main() {
    int a, b;
    cin >> a >> b;
    int s = a + b;
    cout << s;
    return 0;
}

Pentru intrarea 3 4 după citire avem $a=3$ și $b=4$, atribuirea dă $s=7$, iar ieșirea este 7. Pentru 5 9 aceiași pași dau 14: datele de intrare diferă, algoritmul rămâne același.

Exemplul 2 — doi algoritmi pentru aceeași problemă. Se cere suma $1+2+\dots +n$. Primul algoritm adună pe rând fiecare număr; al doilea folosește formula $\frac{n(n+1)}{2}$.

#include <iostream>
using namespace std;
int main() {
    int n = 100;
    int s = 0;
    for (int i = 1; i <= n; ++i)
        s += i;
    cout << s << ' ' << n * (n + 1) / 2;
    return 0;
}

Programul afișează 5050 5050: rezultatele coincid, deci ambii algoritmi sunt corecți. Primul face $n=100$ de adunări, al doilea doar trei operații indiferent de $n$; de aceea al doilea este mai eficient. Corectitudinea nu cere eficiență, dar pentru valori mari ale lui $n$ diferența se vede.

Reprezentări ale aceluiași algoritm. În limbaj natural: „citesc două numere, le adun și comunic suma”. În schema logică: blocul de început, un bloc de citire pentru $a$ și $b$, un bloc de calcul $seftarrowa+b$, un bloc de scriere pentru $s$ și blocul de sfârșit, legate prin săgeți. În pseudocod: citește a, b, s ← a + b, scrie s. În toate cele trei forme, pașii și ordinea lor sunt aceiași.

Domeniul datelor de intrare. Un algoritm este corect numai pentru intrările pentru care a fost gândit. Algoritmul care determină prima cifră dintr-un număr prin împărțiri la 10 este scris pentru numere naturale; pentru un număr negativ trebuie să alegi întâi o convenție, de pildă lucrul cu modulul. Enunțul precizează ce valori sunt admise.

Ce nu este algoritm. Secvența „citește $x$; cât timp $x>0$ execută $x\leftarrow x+1$” nu se termină pentru nicio valoare pozitivă a lui $x$, deci încalcă finitudinea. Instrucțiunea „alege un număr potrivit” este imprecisă, pentru că nu spune ce înseamnă „potrivit”.

Exemplul 3 — urmărirea valorilor. Cel mai mare divizor comun al numerelor 48 și 18 se află prin împărțiri repetate: cât timp $b\ne 0$, perechea $(a,b)$ se înlocuiește cu $(b,a\mathrm{mod}b)$. Perechile succesive sunt $(48,18)$, $(18,12)$, $(12,6)$ și $(6,0)$. Ciclul se oprește când $b=0$, iar rezultatul este $a=6$. Restul scade strict la fiecare pas, de aceea algoritmul se termină pentru orice pereche de numere naturale.

Structurile de bază. Structura liniară execută pașii unul după altul. Structura alternativă alege între două ramuri după valoarea unei condiții (dacă … atunci … altfel). Structura repetitivă reia un grup de pași: cu test inițial (cât timp), cu test final (repetă … până când) sau cu număr cunoscut de pași (pentru). Programarea structurată arată că oricare algoritm se poate scrie numai cu aceste trei structuri. Pseudocodul descrie algoritmul în cuvinte apropiate de limba română, cu reguli fixe de scriere; schema logică îl desenează din blocuri legate prin săgeți.

Algoritmii elementari de clasa a IX-a se reduc la câteva operații de reținut, pentru un număr natural $n$:

Cifrele se obțin de la dreapta la stânga, cu n % 10 și n / 10, iar un număr nou se construiește cu x * 10 + c. Din aceste două operații vin suma cifrelor, numărul cifrelor, cifra maximă, eliminarea cifrelor cu o proprietate și oglinditul unui număr, folosit la verificarea palindromului.

Aplicații elementare

Un număr $d$ divide $n$ dacă restul împărțirii lui $n$ la $d$ este 0. Divizorii vin în perechi ($d$ și $n/d$), așa că e suficient să îi cauți până la $\sqrt{n}$. Cel mai mare divizor comun a două numere se calculează rapid prin împărțiri repetate, cu algoritmul lui Euclid. Un număr natural este prim dacă are exact doi divizori, pe 1 și pe el însuși; pentru un singur număr, testul cu divizori până la $\sqrt{n}$ este suficient, iar pentru toate numerele prime până la o limită se folosește ciurul lui Eratostene.

Tot la algoritmii elementari intră șirul lui Fibonacci, în care fiecare termen este suma celor doi dinaintea lui, sumele cu termen general dat și determinarea minimului sau a maximului dintr-o secvență de valori citite una câte una. Toate folosesc aceeași schemă: inițializezi o variabilă, apoi o actualizezi la fiecare pas al structurii repetitive.

Exemple rezolvate

Se citește un număr natural nenul $n$. Afișează suma cifrelor lui și numărul divizorilor lui.

1. Suma cifrelor: cât timp $n$ are cifre, aduni ultima cifră și o elimini. Lucrezi pe o copie, ca să nu pierzi valoarea lui $n$.
2. Divizorii: pentru fiecare $d$ cu $d\cdot d<n$ care divide $n$, numeri doi divizori ($d$ și $n/d$); dacă $n$ este pătrat perfect, rădăcina lui se numără o singură dată.

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int x = n, s = 0;
    while (x > 0) {
        s = s + x % 10;   // adaug ultima cifra
        x = x / 10;       // elimin ultima cifra
    }
    int nrd = 0, d;
    for (d = 1; 1LL * d * d < n; d++)
        if (n % d == 0)
            nrd = nrd + 2;   // d si n / d
    if (1LL * d * d == n)
        nrd++;               // n este patrat perfect
    cout << s << " " << nrd << "\n";
    return 0;
}

Produsul se calculează ca 1LL * d * d, adică în tipul long long: pentru $n$ apropiat de valoarea maximă a lui int (2147483647), d * d calculat în int ar putea depăși tipul înainte ca bucla să se oprească. În tabelul de mai sus, aceeași grijă apare ca d <= n / d, echivalent cu $d\cdot d\le n$ pentru numere pozitive.

Pentru $n=360$, programul afișează:

9 24

Verificare: $3+6+0=9$, iar $360=2^3\cdot 3^2\cdot 5$ are $(3+1)(2+1)(1+1)=24$ de divizori. Pentru $n=1$, bucla nu se execută, $d$ rămâne 1, iar $1\cdot 1=1$, deci programul numără corect un singur divizor.

La un enunț cu cod sau pseudocod, separă ce calculează algoritmul de felul în care este scris. Urmărește valorile variabilelor după fiecare atribuire și verifică oprirea repetărilor: o buclă a cărei condiție nu se schimbă niciodată nu se termină. Același rezultat poate fi obținut prin algoritmi diferiți, iar enunțul poate cere doar valoarea afișată, nu felul în care a fost calculată. Dacă două secvențe dau aceleași rezultate pentru toate intrările admise, ele sunt echivalente, chiar dacă una folosește un ciclu și cealaltă o formulă. Pentru a decide ce afișează o secvență, nu ghici scopul ei: execută-o pe intrarea dată și scrie valorile succesive.

Exemplu în formatul examenului. Ce se afișează în urma executării secvenței de mai jos?

int x = 4827;
while (x >= 10)
    x = x / 10;
cout << x;

• a) 7
• b) 4
• c) 48
• d) 482

Răspunsul corect este b). Valorile lui $x$ sunt 4827, 482, 48, 4. Cât timp $x\ge 10$ se elimină ultima cifră prin împărțire întreagă la 10; ciclul se oprește când $x=4<10$. Algoritmul determină prima cifră a unui număr natural; pentru $x=7$ condiția $x\ge 10$ este falsă de la început, ciclul nu se execută și se afișează 7. Varianta a) ar fi ultima cifră, $x\mathrm{mod}10$, iar variantele c) și d) sunt valori intermediare ale ciclului.

Atenție la limită: dacă în secvența de mai sus condiția ar fi x > 10, pentru $x=10$ ciclul nu s-ar executa și s-ar afișa 10, nu cifra 1. Compară întotdeauna valoarea de la limită cu semnul > sau >=.

Unde apare la examen

La Bacalaureatul la informatică, matematică-informatică, programa de examen are un capitol „Algoritmi” (noțiunea de algoritm, structurile de bază, descrierea algoritmilor în pseudocod) și un capitol „Algoritmi elementari” (cifrele unui număr, divizibilitate, numere prime, algoritmul lui Euclid, șirul lui Fibonacci, minim și maxim, sortare, căutare, complexitate), în anexa 2 la OMECTS 4800/2010. La sesiunea din iunie–iulie 2026, Subiectul al II-lea a pornit de la un algoritm în pseudocod, iar primul subprogram cerut la Subiectul al III-lea a prelucrat cifrele unui număr (subiectele și baremele Bac 2026).

Greșeli frecvente

• Greșit: un algoritm este obligatoriu un program C++.
  Corect: algoritmul este metoda; programul este o implementare într-un limbaj.
• Greșit: o metodă care merge pentru un singur exemplu este suficientă.
  Corect: ea trebuie să rezolve toate intrările admise de problemă.
• Greșit: o repetare care nu se oprește poate fi un algoritm corect.
  Corect: finitudinea cere încheierea pentru fiecare intrare admisă.

Înainte și după

Întrebări frecvente