Structuri repetitive echivalente: cât timp, repetă și pentru

Ultima cerință a itemului II.1 de la BAC informatică sună de obicei așa: „Scrieți în pseudocod un algoritm echivalent cu cel dat, înlocuind structura cât timp…execută cu o structură repetitivă de alt tip.” Cuvântul-cheie este echivalent: noul algoritm trebuie să afișeze exact același lucru ca cel inițial, pentru orice date de intrare valide, nu doar pentru exemplul de la punctul a). Iar diferențele dintre structurile repetitive apar tocmai la cazurile limită.

Cele trei structuri, comparate

Din tabel rezultă cele două reguli de bază: între cât timp și repetă condiția se neagă, iar diferența de „număr minim de execuții” trebuie compensată.

Din pentru în cât timp

Cea mai simplă transformare. Desfaci pentru în cele trei componente ale sale: inițializare, condiție, incrementare.

citește a, b (numere naturale, a ≤ b)
k ← 0
pentru i ← a, b execută
    dacă i % 3 = 0 atunci
        k ← k + 1
scrie k

Devine:

citește a, b (numere naturale, a ≤ b)
k ← 0
i ← a
cât timp i ≤ b execută
    dacă i % 3 = 0 atunci
        k ← k + 1
    i ← i + 1
scrie k

Algoritmul numără multiplii lui 3 din intervalul [a, b]; pentru a = 4, b = 10 afișează 2 (numerele 6 și 9). Atenție la două detalii: i ← i + 1 se pune la sfârșitul corpului, după toate celelalte instrucțiuni, iar pentru un pas negativ (pentru i ← b, a, -1) condiția devine i ≥ a și incrementarea devine i ← i - 1.

Din pentru în repetă: când ai voie

În exemplul de mai sus, enunțul garantează a ≤ b, deci bucla se execută cel puțin o dată. Atunci poți scrie direct:

k ← 0
i ← a
repetă
    dacă i % 3 = 0 atunci
        k ← k + 1
    i ← i + 1
până când i > b
scrie k

Condiția de oprire i > b este negația lui i ≤ b. Dacă restricția a ≤ b nu ar exista, pentru a = 9, b = 5 algoritmul inițial ar afișa 0, iar acesta ar verifica totuși numărul 9 și ar afișa 1. Nu ar mai fi echivalent. Așa că citește restricțiile din paranteza de lângă citește: ele îți spun dacă ai nevoie de protecție suplimentară.

Din cât timp în repetă

Problema: cât timp poate să nu execute nimic, repetă execută sigur o dată. Soluția generală este să pui bucla repetă sub un dacă cu aceeași condiție:

cât timp n > 0 execută
    s ← s + n % 10
    n ← [n/10]

devine:

dacă n > 0 atunci
    repetă
        s ← s + n % 10
        n ← [n/10]
    până când n ≤ 0

Uneori dacă nu e necesar — de exemplu, dacă enunțul spune că n este nenul. Dar dacă n poate fi 0 și nu ești sigur, pune-l: un dacă în plus nu strică echivalența, pe când lipsa lui o poate strica.

Din repetă în cât timp: capcana clasică

Fie algoritmul care numără cifrele unui număr natural:

citește n (număr natural)
k ← 0
repetă
    k ← k + 1
    n ← [n/10]
până când n = 0
scrie k

Pentru n = 507 afișează 3. Pentru n = 0, corpul se execută o dată și afișează 1 — corect, 0 are o cifră. Transformarea „naivă”:

k ← 0
cât timp n ≠ 0 execută
    k ← k + 1
    n ← [n/10]
scrie k

Pentru n = 507 merge, dar pentru n = 0 afișează 0. Algoritmul nu e echivalent. Soluția sigură este să execuți corpul o dată înainte de buclă, exact cum ar face repetă:

k ← 1
n ← [n/10]
cât timp n ≠ 0 execută
    k ← k + 1
    n ← [n/10]
scrie k

Aici am „copiat” corpul (k ← k + 1 cu k pornind de la 0 dă k ← 1) înaintea lui cât timp. Metoda funcționează întotdeauna: după prima execuție, cele două structuri se comportă identic.

Negarea condițiilor compuse

Pentru condiții cu și / sau aplici legile lui De Morgan: negația lui „A și B” este „non-A sau non-B”, iar negația lui „A sau B” este „non-A și non-B”. Concret:

• cât timp x ≠ 0 și y ≠ 0 → până când x = 0 sau y = 0;
• cât timp a < b sau a % 2 = 1 → până când a ≥ b și a % 2 = 0 (pe numere naturale, restul nu poate fi decât 0 sau 1).

Negația lui < este ≥, nu >. E o greșeală mică, dar schimbă rezultatul exact când cele două valori sunt egale.

Pașii de lucru la itemul II.1d

1. Identifică exact structura pe care trebuie s-o înlocuiești — dacă algoritmul are două bucle, enunțul precizează care dintre ele.
2. Copiază neschimbat tot ce e înainte și după acea structură; doar ea se modifică.
3. Scrie noua structură, cu condiția negată dacă treci între cât timp și repetă.
4. Compensează diferența de execuții: dacă în față sau corpul copiat înainte de buclă.
5. Testează ambele variante pe exemplul de la punctul a) și pe cazul limită. Trebuie să obții același rezultat.

Scrie algoritmul complet, de la citește la scrie, nu doar bucla modificată — cerința e „un algoritm echivalent”, nu o secvență.

Din cât timp în pentru

E posibil doar când bucla are un contor care crește sau scade cu un pas fix și nu e modificat în altă parte. O buclă de tipul cât timp n > 0 … n ← [n/10] nu se transformă natural în pentru, pentru că nu știi dinainte câți pași face. De aceea cerința de la BAC îți spune de obicei explicit ce tip de structură să folosești sau îți dă un algoritm unde transformarea e firească.