Algoritmi și structuri de date

Elevii învață să conceapă și să reprezinte algoritmi folosind pseudocod și scheme logice, cu accent pe structuri de control.

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

Un algoritm este o succesiune finită de pași, descriși clar și fără ambiguitate, care rezolvă o problemă pornind de la niște date de intrare și producând date de ieșire. O rețetă de clătite sau instrucțiunile de montaj ale unui dulap sunt algoritmi din viața reală: pași ordonați, pe care îi execuți exact în ordinea dată.

Ca să fie cu adevărat algoritm, o succesiune de pași trebuie să respecte câteva proprietăți — acestea se cer aproape mereu la teste:

• Finitudine — algoritmul se termină după un număr finit de pași. Un program care se învârte la nesfârșit în aceeași buclă nu este un algoritm corect.
• Claritate (determinism) — fiecare pas este precis, fără interpretări. „Adaugă puțină sare” nu e clar; „adaugă 5 grame de sare” este.
• Generalitate — algoritmul rezolvă o clasă întreagă de probleme, nu un singur caz. Un algoritm care adună două numere trebuie să funcționeze pentru orice două numere, nu doar pentru 3 și 7.
• Eficiență — pașii pot fi executați efectiv, într-un timp rezonabil.

Confuzia clasică: elevii cred că datele de intrare sunt obligatorii. Nu este așa — există algoritmi fără date de intrare (de exemplu, afișarea primelor 10 numere pare), dar orice algoritm util produce cel puțin o dată de ieșire, altfel nu am afla niciodată rezultatul.

Pseudocod și scheme logice

Un algoritm poate fi descris în mai multe feluri. Cele două reprezentări studiate în gimnaziu sunt pseudocodul și schema logică.

Pseudocodul este un limbaj intermediar între limbajul natural și un limbaj de programare. Folosește cuvinte-cheie standard:

• citește a, b — preia datele de intrare;
• scrie s — afișează datele de ieșire;
• s ← a + b — instrucțiunea de atribuire: valoarea expresiei din dreapta se memorează în variabila din stânga;
• dacă ... atunci ... altfel — decizie;
• cât timp ... execută — repetare.

Schema logică desenează algoritmul cu blocuri geometrice legate prin săgeți: ovalul marchează început/sfârșit, paralelogramul — citire/scriere, dreptunghiul — calcul/atribuire, iar rombul — o decizie cu două ieșiri (Da/Nu).

Atenție la atribuire: x ← x + 1 este perfect valid și înseamnă „noua valoare a lui x devine vechea valoare plus 1”. Nu este o ecuație matematică! La atribuire, vechea valoare a variabilei se pierde — se suprascrie. De aceea, ca să interschimbi valorile a două variabile a și b, ai nevoie de o a treia variabilă auxiliară: aux ← a, apoi a ← b, apoi b ← aux. Dacă scrii direct a ← b, valoarea inițială a lui a a dispărut pentru totdeauna.

Structura liniară și structura alternativă

Structura liniară (secvențială) este cea mai simplă: pașii se execută unul după altul, exact o dată fiecare, în ordinea scrisă. Exemplu: citește două numere, calculează suma, afișeaz-o. Nicio decizie, nicio repetare.

Structura alternativă (decizia) alege între două drumuri în funcție de o condiție — o expresie care poate fi adevărată sau falsă:

• dacă a > b atunci scrie a altfel scrie b — afișează maximul dintre două numere;
• ramura altfel este opțională: poți avea o decizie care face ceva doar când condiția e adevărată.

Condițiile se construiesc cu operatori relaționali (<, >, =, ≠, ≤, ≥) și pot fi combinate cu operatori logici: și (ambele condiții adevărate), sau (cel puțin una adevărată), nu (neagă condiția).

Două capcane care apar constant în teste:

• și vs sau: „n este divizibil cu 2 și cu 3” înseamnă divizibil cu ambele (adică cu 6); „divizibil cu 2 sau cu 3” e adevărat și pentru 4, și pentru 9. Elevii le inversează frecvent.
• Deciziile imbricate: un dacă poate conține în interior alt dacă. Ramura altfel se leagă întotdeauna de cel mai apropiat dacă fără altfel — citește cu atenție indentarea (spațiile de la începutul rândurilor).

Structurile repetitive: cât timp, pentru, repetă până când

Structurile repetitive (buclele) execută un grup de instrucțiuni de mai multe ori. Există trei forme, iar diferențele dintre ele sunt subiect sigur de test:

• cât timp condiție execută — bucla cu test inițial: condiția se verifică ÎNAINTE de fiecare execuție. Dacă e falsă de la început, corpul buclei nu se execută niciodată (zero execuții posibile).
• pentru i ← 1, n execută — bucla cu contor: se folosește când știm dinainte de câte ori repetăm. Contorul i pornește de la 1 și crește automat cu 1 la fiecare pas, până la n.
• repetă ... până când condiție — bucla cu test final: corpul se execută mai întâi, apoi se verifică condiția. Corpul se execută deci cel puțin o dată, oricum ar fi condiția. Atenție: repetarea continuă cât timp condiția e falsă și se oprește când devine adevărată — exact invers față de cât timp!

Bucla infinită e greșeala fatală: dacă în corpul lui cât timp nu modifici nicio variabilă din condiție, condiția rămâne mereu adevărată și programul nu se mai oprește — se încalcă proprietatea de finitudine.

Cel mai important exercițiu de examen este urmărirea execuției (trace): iei un tabel cu variabilele pe coloane și scrii valoarea fiecăreia după fiecare pas. Metoda pare lentă, dar este singura care garantează răspunsul corect la întrebarea „ce afișează algoritmul?”.

Algoritmi elementari pe care trebuie să îi stăpânești

Câțiva algoritmi apar atât de des încât trebuie recunoscuți din prima privire:

• Suma și numărarea: inițializezi s ← 0 (pentru sumă) sau k ← 0 (pentru numărare) ÎNAINTE de buclă, apoi în buclă aduni sau numeri. Dacă uiți inițializarea, rezultatul e imprevizibil.
• Maxim/minim dintr-un șir de numere citite: inițializezi maximul cu primul număr citit (nu cu 0! — dacă toate numerele sunt negative, 0 ar da un rezultat greșit), apoi compari fiecare număr nou cu maximul curent și îl înlocuiești când găsești unul mai mare.
• Cifrele unui număr: n mod 10 este ultima cifră a lui n, iar n div 10 este numărul fără ultima cifră (div = câtul împărțirii întregi, mod = restul). Ca să prelucrezi toate cifrele, repeți aceste două operații cât timp n ≠ 0. Așa se construiesc suma cifrelor, numărul de cifre și inversul (oglinditul) unui număr: inv ← inv * 10 + n mod 10.
• Paritate și divizibilitate: n e par dacă n mod 2 = 0; n e divizibil cu d dacă n mod d = 0.

Tablourile unidimensionale (vectorii) apar aici la nivel introductiv: un vector este o înșiruire de valori de același tip, numerotate printr-un indice. În loc de 20 de variabile separate, ai v[1], v[2], ..., v[20] și le parcurgi cu o buclă pentru. Prelucrările clasice — suma elementelor, maximul, numărarea celor pare — sunt exact algoritmii de mai sus, aplicați element cu element.

Test — 6 întrebări ca la examen