Algoritmi și date

Introducere în conceptul de algoritm, proprietăți și modalități de reprezentare, alături de tipuri de date utilizate în programare.

Ce este un algoritm și ce proprietăți trebuie să aibă

Un algoritm este o succesiune finită de pași, descriși fără ambiguitate, care pornește de la niște date de intrare și produce, într-un timp finit, date de ieșire — adică rezultatul problemei. Nu orice listă de instrucțiuni este algoritm: ea trebuie să respecte trei proprietăți care se cer explicit la examen.

• Finitudine – algoritmul se termină după un număr finit de pași, pentru orice date de intrare valide. O buclă care nu se oprește niciodată încalcă exact această proprietate.
• Determinism (claritate) – fiecare pas este precis definit: în aceeași situație, algoritmul face întotdeauna același lucru. Nu există pași de tipul „alege o valoare oarecare”.
• Generalitate (universalitate) – algoritmul rezolvă o clasă întreagă de probleme, nu un singur caz particular. Un algoritm care calculează media a două numere trebuie să funcționeze pentru orice pereche de numere, nu doar pentru 4 și 6.

Confuzia clasică: elevii cred că un program care merge pe exemplul din enunț este corect. Corectitudinea se judecă pe toate datele de intrare posibile — inclusiv cazurile-limită: zero, numere negative, șirul cu un singur element.

Reprezentarea algoritmilor: pseudocod și schemă logică

Același algoritm poate fi descris în mai multe moduri. La BAC se folosește pseudocodul — un limbaj intermediar între limbajul natural și limbajul de programare, cu cuvinte-cheie românești standardizate:

• citește a, b – preluarea datelor de intrare;
• scrie rezultat – afișarea datelor de ieșire;
• x ← expresie – atribuirea: valoarea expresiei din dreapta se memorează în variabila din stânga;
• dacă condiție atunci ... altfel ... – decizia;
• cât timp condiție execută ... – repetarea cu test inițial;
• repetă ... până când condiție – repetarea cu test final;
• pentru i ← a, b execută ... – repetarea cu contor.

Schema logică exprimă același lucru grafic: oval pentru start/stop, paralelogram pentru citire/scriere, dreptunghi pentru atribuiri (prelucrări) și romb pentru decizii, cu două ieșiri (da/nu). Săgețile arată ordinea de execuție.

De reținut din convențiile de subiect: [x] înseamnă partea întreagă a lui x, iar x % y (sau „restul împărțirii”) este restul împărțirii întregi. De exemplu [7/2] = 3, iar 7 % 2 = 1. Aceste notații apar în aproape orice subiect de bacalaureat.

Tipuri de date, variabile și constante

Orice dată prelucrată de calculator are un tip, care stabilește ce valori poate lua și ce operații are voie să suporte:

• întreg (int) – numere fără parte zecimală: -3, 0, 2026; suportă împărțirea întreagă și restul;
• real (float, double) – numere cu zecimale: 3.14, -0.5; NU are sens operatorul de rest;
• caracter (char) – un singur simbol: o literă, o cifră ca semn, un spațiu; intern e memorat printr-un cod numeric (ASCII);
• șir de caractere (string) – o secvență de caractere: un nume, o propoziție;
• logic (bool) – doar două valori: adevărat sau fals; e tipul rezultat al oricărei condiții.

O variabilă este o zonă de memorie cu un nume, un tip și o valoare care se poate schimba în timpul execuției. O constantă are valoare fixată o singură dată (de exemplu numărul zilelor unei săptămâni).

Capcana cea mai frecventă: împărțirea între întregi este întreagă. În C++, expresia 7/2 dă 3, nu 3.5 — partea zecimală se pierde, nu se rotunjește. Ca să obții 3.5 trebuie ca măcar un operand să fie real. Tot aici: cifra „7” ca caracter și numărul 7 ca întreg sunt date diferite, cu tipuri diferite.

Operatori și expresii

O expresie combină valori, variabile și operatori și produce un rezultat de un anumit tip.

• Operatori aritmetici: + , - , * , / , % (restul). Pe întregi, / este împărțire întreagă (câtul), iar % dă restul: 17 / 5 = 3 și 17 % 5 = 2. Restul are voie să existe doar între întregi.
• Operatori relaționali: < , <= , > , >= , == (egal), != (diferit). Rezultatul lor este întotdeauna logic (adevărat/fals).
• Operatori logici: și (&&), sau (||), not (!). „Și” e adevărat doar când ambele condiții sunt adevărate; „sau” e fals doar când ambele sunt false.

Prioritatea operatorilor decide ordinea de calcul: întâi not, apoi operatorii aritmetici (*, /, % înaintea lui + și -), apoi relaționalii, apoi && și la final ||. Parantezele bat orice prioritate.

Două greșeli care costă puncte: confuzia dintre = (atribuire) și == (comparație) — în pseudocod atribuirea e săgeata ←, dar în C++ scrierea „dacă (x = 5)” atribuie în loc să compare; și negarea condițiilor compuse — negația lui „x > 0 și y > 0” este „x <= 0 sau y <= 0” (legile lui De Morgan schimbă „și” în „sau”), nu „x <= 0 și y <= 0”.

Structurile de bază: secvențială, alternativă, repetitivă

Teorema de structură (Böhm–Jacopini) spune că orice algoritm se poate construi doar din trei structuri:

• Structura secvențială – pașii se execută unul după altul, în ordinea scrisă. Ordinea contează: dacă schimbi două atribuiri între ele, rezultatul se poate schimba complet.
• Structura alternativă – dacă condiția e adevărată se execută o ramură, altfel cealaltă. Ramura altfel poate lipsi. Deciziile se pot imbrica: un dacă în interiorul altui dacă.
• Structura repetitivă – un grup de instrucțiuni se execută de mai multe ori. Există trei forme, iar diferența dintre ele e subiect sigur de examen:
• cât timp condiție execută – testul e la început; dacă de prima dată condiția e falsă, corpul se execută de zero ori;
• repetă ... până când condiție – testul e la sfârșit; corpul se execută cel puțin o dată, iar repetarea se oprește când condiția devine adevărată;
• pentru i ← a, b – repetare cu contor, folosită când numărul de pași e cunoscut dinainte.

Atenție la sensul condițiilor: la cât timp se continuă cât condiția e adevărată, la până când se continuă cât condiția e falsă. Transformarea dintr-o formă în alta — cerință frecventă la BAC — presupune negarea condiției, nu copierea ei.

Urmărirea execuției pas cu pas — instrumentul de bază la examen

Cea mai sigură metodă de a răspunde la întrebarea „ce afișează algoritmul?” este urmărirea execuției (trasarea): construiești un tabel cu câte o coloană pentru fiecare variabilă și execuți pașii pe hârtie, rând cu rând, exact ca un calculator — fără să „ghicești” ce ar vrea algoritmul să facă.

Regulile de aur ale trasării:

• scrii valorile după fiecare atribuire, nu doar la final;
• la fiecare intrare în buclă verifici condiția cu valorile curente, nu cu cele inițiale;
• nu sări peste iterații „pentru că se vede tiparul” — exact în penultima iterație apar surprizele;
• verifici separat prima și ultima iterație: acolo se produc erorile „off by one” (o repetare în plus sau în minus).

Un algoritm-model care apare constant la examen: prelucrarea cifrelor unui număr. Cât timp n este diferit de 0, ultima cifră se extrage cu n % 10, apoi numărul se scurtează cu n ← [n/10]. Cu acest tipar se calculează suma cifrelor, numărul de cifre, oglinditul (inversul) unui număr. Merită exersat până devine reflex, pentru că e cărămida multor subiecte de la bacalaureat.

Test — 6 întrebări ca la examen