Ce este un algoritm

Ce face ca o listă de pași să fie un algoritm și de ce contează diferența la examen.

Ideea

Un algoritm este o succesiune finită de pași care, pornind de la niște date de intrare, ajunge la un rezultat.

Cuvântul important din definiție este finită. O listă de instrucțiuni care nu se termină niciodată nu este un algoritm. Este o problemă.

Un exemplu care nu are nimic de-a face cu calculatorul: „cum aflu dacă am destui bani pentru un bilet". Pașii sunt: număr banii din buzunar, mă uit la prețul biletului, compar cele două numere, iar dacă am cel puțin cât costă biletul răspund da, altfel răspund nu. Sunt cinci pași, se termină întotdeauna, iar oricine îi urmează ajunge la același răspuns.

Reține mai ales ultima parte: un algoritm nu depinde de cine îl execută.

Proprietățile pe care trebuie să le aibă

Nu orice text care descrie o rezolvare este un algoritm. Sunt cinci condiții. Fiecare apare des la examen, într-o întrebare de tipul „de ce nu este corect algoritmul de mai jos".

Este finit. Se termină după un număr de pași, oricare ar fi datele de intrare. Întotdeauna, nu doar „de obicei".

Fiecare pas este clar. „Împarte pe n la d" este un pas clar. „Alege un divizor potrivit" nu este: nu spune care.

Este determinist. Aceleași date de intrare duc de fiecare dată la același rezultat. Dacă la un pas ar trebui să ghicești ceva, nu este algoritm.

Are intrări și ieșiri. Se precizează datele de la care pornește și rezultatul la care ajunge. Un algoritm care calculează ceva, dar nu spune nimic despre rezultat, nu folosește la nimic.

Este general. Rezolvă o clasă întreagă de cazuri, nu unul singur. Un algoritm care află maximul dintre 7 și 12 nu valorează nimic. Unul care află maximul dintre două numere oarecare, da.

Trei feluri de a scrie același algoritm

Să luăm o problemă mică: se citesc trei numere întregi și se cere cel mai mare dintre ele.

În limbaj natural

Rețin primul număr ca fiind cel mai mare de până acum. Compar al doilea număr cu el. Dacă e mai mare, îl rețin pe acesta în locul lui. Fac la fel cu al treilea. La final, numărul reținut este maximul.

Se citește ușor, dar este imprecis: ce înseamnă exact „îl rețin"?

În pseudocod

citește a, b, c
max ← a
┌dacă b > max atunci
│ max ← b
└■
┌dacă c > max atunci
│ max ← c
└■
scrie max

Aici nu mai ai ce interpreta. Fiecare linie conține exact o operație, iar ← înseamnă „ia valoarea".

În C++

#include <iostream>
using namespace std;

int main() {
    int a, b, c, maxim;
    cin >> a >> b >> c;

    maxim = a;
    if (b > maxim) maxim = b;
    if (c > maxim) maxim = c;

    cout << maxim;
    return 0;
}

Avem trei descrieri ale aceluiași algoritm. Între ele diferă doar cât de precis vorbim. Ce facem rămâne la fel.

De ce contează ordinea asta

La bac ți se cer exact aceste trei niveluri, în subiecte diferite:

• Subiectul I îți dă pseudocod scris de altcineva și te întreabă ce afișează. Aici nu scrii nimic, doar citești.
• Subiectul II îți cere să scrii tu pseudocod sau să completezi unul început.
• Subiectul III îți cere programul C++ întreg.

Dacă sari direct la C++ și nu știi să urmărești un pseudocod pe hârtie, pierzi punctele de la Subiectul I, chiar dacă la programare nu greșești nimic. Sunt puncte separate și sunt cele mai ușor de luat din toată lucrarea.

Câți pași face un algoritm

Pe lângă „este corect?", te mai interesează cât de repede este.

Ca să afli dacă un număr n este prim, poți încerca toți divizorii de la 2 la n-1. Merge. Dar poți încerca doar până la radical din n, pentru că divizorii vin în perechi: dacă n = d · e și d ≤ e, atunci d ≤ √n. Pentru n de ordinul unui miliard, prima variantă face aproape un miliard de pași, iar a doua vreo treizeci de mii.

Ambele sunt algoritmi corecți, dar numai unul se termină înainte să expire timpul.

Ne vom întoarce des la această idee: corectitudinea nu este singurul criteriu.

De reținut

• Algoritm = pași finiți, clari, care duc de la intrare la rezultat, la fel de fiecare dată.
• Aceeași rezolvare se scrie în limbaj natural, în pseudocod și în C++. Diferă precizia, ideea rămâne.
• Examenul te testează pe toate trei, în subiecte diferite.
• Un algoritm corect poate fi totuși prea lent. Numărul de pași contează.