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 instrucțiuni (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 are sfârșit nu reprezintă un algoritm.

Un exemplu concret din viața reală: „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, dacă am mai mult decât costă biletul răspund da, altfel răspund nu. Sunt cinci pași, iar oricine îi urmează ajunge la același răspuns.

Un algoritm produce același rezultat, indiferent cine îl execută.

Caracteristicile unui algoritm

Este finit. Execuția sa se încheie după un număr finit de pași, oricare ar fi datele de intrare.

Fiecare pas este clar. Instrucțiunea „Împarte pe n la d" este una clară. „Alege un divizor potrivit", nu este.

Este determinist. Aceleași date de intrare duc de fiecare dată la același rezultat. La fiecare pas al algoritmului este clar care va fi următoarea instrucțiune executată.

Este general. Rezolvă o clasă de probleme, nu o instanță particulară. 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ă.