Structuri de control – repetitive

Prezentarea și utilizarea structurilor repetitive cu număr cunoscut și necunoscut de pași.

De ce avem nevoie de repetiție

Multe probleme cer executarea acelorași pași de mai multe ori: afișarea numerelor de la 1 la 100, adunarea a 20 de note, verificarea fiecărei cifre a unui număr. A scrie de 100 de ori „scrie i” ar fi absurd — pentru asta există structurile repetitive (buclele): un grup de instrucțiuni, numit corpul buclei, se execută în mod repetat, cât timp o condiție permite acest lucru.

Orice buclă corectă are trei ingrediente, iar lipsa oricăruia este sursa clasică de greșeli:

• inițializarea – variabilele buclei primesc valori de pornire ÎNAINTE de buclă (de exemplu s ← 0, i ← 1);
• condiția – decide dacă execuția continuă sau se oprește;
• actualizarea – în corpul buclei, ceva trebuie să se schimbe (de exemplu i ← i + 1), altfel condiția rămâne veșnic la fel.

Dacă actualizarea lipsește sau condiția nu poate deveni niciodată falsă, obținem o buclă infinită — algoritmul nu se mai termină, încălcând proprietatea de finitudine. Exemplu de buclă infinită: i ← 1; cât timp i <= 5 execută scrie i — fără i ← i + 1 în corp, i rămâne mereu 1 și afișarea nu se oprește niciodată. Întrebarea „de ce nu se termină algoritmul?” are aproape întotdeauna acest răspuns: variabila din condiție nu se modifică în corpul buclei.

Structura pentru – număr cunoscut de pași

Când știm dinainte de câte ori se repetă pașii, folosim structura pentru (for). Ea are o variabilă de control (contor) care ia pe rând valorile dintr-un interval:

• pentru i de la 1 la 5 execută scrie i

Contorul i ia valorile 1, 2, 3, 4, 5, iar corpul se execută de 5 ori, afișând 1 2 3 4 5. Contorul crește automat cu 1 la fiecare pas (sau cu alt pas dacă se precizează — inclusiv pas negativ pentru numărare descrescătoare: pentru i de la 10 la 1 cu pasul -1).

Calculul numărului de execuții este întrebare de test garantată: pentru i de la a la b (cu pasul 1), corpul se execută de b − a + 1 ori. Deci de la 3 la 8 înseamnă 8 − 3 + 1 = 6 execuții, nu 5 — plus-unu-ul uitat este cea mai răspândită greșeală aritmetică a capitolului.

Exemplu util — suma primelor n numere naturale:

• citește n
• s ← 0
• pentru i de la 1 la n execută s ← s + i
• scrie s

Pentru n = 4: s crește 0 → 1 → 3 → 6 → 10; se afișează 10. Observă inițializarea s ← 0 înaintea buclei — fără ea, suma pornește de la o valoare întâmplătoare. Iar dacă intervalul e gol (de la 5 la 2 cu pas 1), corpul nu se execută niciodată, iar algoritmul afișează 0.

Structura cât timp – test inițial

Când nu știm dinainte de câte ori se repetă pașii, dar știm condiția de continuare, folosim structura cât timp (while):

• cât timp condiție execută instrucțiuni

Mecanismul: condiția se verifică ÎNAINTE de fiecare execuție a corpului. Dacă e adevărată, corpul se execută și se revine la verificare; dacă e falsă, bucla se încheie. Consecința de reținut, punctată în subiecte: dacă la prima verificare condiția e deja falsă, corpul nu se execută deloc — de zero ori.

Exemplu clasic — numărarea cifrelor unui număr:

• citește n (presupunem n = 407)
• c ← 0
• cât timp n > 0 execută: c ← c + 1; n ← [n/10] (câtul împărțirii la 10, care taie ultima cifră)
• scrie c

Urmărire: n=407, c=1, n devine 40; c=2, n devine 4; c=3, n devine 0; condiția 0 > 0 e falsă, stop. Se afișează 3 — numărul are 3 cifre.

De altfel, perechea de operații restul împărțirii la 10 (ultima cifră) și câtul împărțirii la 10 (numărul fără ultima cifră) este motorul aproape tuturor problemelor cu cifre de la această clasă: sumă de cifre, oglinditul (inversul) unui număr, prima cifră.

Greșeala tipică de urmărire: executarea corpului „încă o dată, de siguranță” după ce condiția a devenit falsă. Nu — în clipa în care verificarea eșuează, execuția sare imediat la instrucțiunea de după buclă.

Structura repetă – până când – test final

A treia structură repetitivă verifică condiția la sfârșit:

• repetă instrucțiuni până când condiție

Corpul se execută, apoi se verifică condiția: dacă e falsă, se repetă; dacă e adevărată, bucla se oprește. Două diferențe esențiale față de cât timp — amândouă cerute la examen:

• corpul se execută cel puțin o dată, întotdeauna, pentru că verificarea vine abia după prima execuție;
• condiția este de OPRIRE, nu de continuare: repetă … până când i > 5 înseamnă „oprește-te când i depășește 5”, adică echivalent cu „cât timp i <= 5”.

Această inversare a condiției este capcana numărul unu a capitolului: la transformarea unei bucle cât timp în repetă–până când, condiția se neagă. „Cât timp n > 0” devine „până când n <= 0” — nu „până când n > 0”, cum scriu grăbiții, ceea ce ar opri bucla exact când ar trebui să continue.

Utilizare tipică: validarea datelor citite. Vrem o notă între 1 și 10:

• repetă: citește nota — până când nota >= 1 ȘI nota <= 10

Citirea se face măcar o dată (firesc — nu avem ce valida înainte să citim), și se reia cât timp valoarea e în afara intervalului.

Rezumatul comparativ care trebuie știut pe de rost: pentru — număr cunoscut de repetări; cât timp — test inițial, corpul posibil de 0 ori, condiție de continuare; repetă–până când — test final, corpul minimum o dată, condiție de oprire.

Algoritmi uzuali și trasarea execuției

Algoritmii repetitivi standard ai clasei a VI-a, de recunoscut din prima privire:

• suma/produsul unui șir de numere: acumulator inițializat cu 0 pentru sumă și cu 1 pentru produs (produs pornit de la 0 rămâne 0 pentru totdeauna — greșeală de punctaj clasică);
• numărarea elementelor cu o proprietate: contor pornit de la 0, mărit cu 1 doar când condiția e îndeplinită;
• minimul/maximul unui șir: primul element devine minim/maxim provizoriu, apoi fiecare element nou se compară cu el;
• prelucrarea cifrelor: ultima cifră = restul împărțirii la 10; eliminarea ei = câtul împărțirii la 10;
• afișarea unui șir de valori: contor care parcurge intervalul cerut.

Trasarea execuției se face cu un tabel: câte o coloană pentru fiecare variabilă și câte o linie pentru fiecare pas al buclei. Exemplu:

• s ← 0; pentru i de la 1 la 3 execută s ← s + i * i; scrie s

Tabel: i=1, s=0+1=1; i=2, s=1+4=5; i=3, s=5+9=14. Se afișează 14.

Reguli de aur la trasare, unde se pierd punctele: scrie valorile după FIECARE pas, nu doar la final; verifică de câte ori se execută corpul (b − a + 1 la pentru); nu uita că la cât timp corpul poate rula de 0 ori, iar la repetă–până când rulează minimum o dată; și oprește-te EXACT când condiția o cere — nici un pas mai devreme, nici unul mai târziu.

Test — 6 întrebări ca la examen