Repetarea cu test inițial

Când nu știi dinainte de câte ori trebuie să faci un pas, poți folosi o repetare cu test inițial. Întâi verifici o condiție. Dacă este adevărată, faci pașii din interior și revii la verificare. Dacă este falsă, ieși din repetare. Expresia „cât timp” spune că pașii se fac numai cât timp condiția rămâne adevărată.

Imaginează-ți că aduni jetoane până ajungi la 3. Pornești cu 0 jetoane. Întrebi „am mai puțin de 3?”: da, adaugi unul și ai 1. Întrebi din nou: da, ajungi la 2. Încă o dată: da, ajungi la 3. Acum răspunsul este „nu”, deci te oprești. Numărul final este 3, iar adăugarea s-a făcut de trei ori.

Testul este înainte de primul pas. Dacă începi deja cu 3 jetoane, condiția „mai puțin de 3” este falsă de la început și nu adaugi niciun jeton. Acesta este un lucru important: corpul unei repetări cu test inițial se poate executa de zero ori.

O repetare trebuie să se apropie de oprire. Dacă verifici mereu „mai puțin de 3”, dar nu schimbi niciodată numărul de jetoane, aceeași întrebare primește mereu același răspuns. Vei repeta la nesfârșit. Când desenezi sau urmărești algoritmul, notează atât valoarea de la fiecare verificare, cât și pasul care o modifică.

Exemplu rezolvat — câte zile până la 20 de lei. Dora pune în pușculiță câte 6 lei pe zi și vrea să strângă cel puțin 20 de lei. Pornește de la 0 lei. Condiția de continuare este „am mai puțin de 20 de lei”.

1. Testul: $0<20$ este adevărat, deci pune 6 lei; are 6 lei, ziua 1.
2. Testul: $6<20$ este adevărat; are 12 lei, ziua 2.
3. Testul: $12<20$ este adevărat; are 18 lei, ziua 3.
4. Testul: $18<20$ este adevărat; are 24 de lei, ziua 4.
5. Testul: $24<20$ este fals, deci repetarea se oprește.

Dora a pus bani de 4 ori și a făcut 5 teste. Ultimul test este fals și hotărăște oprirea. Suma finală, 24 de lei, depășește 20: nu se oprește exact la 20, pentru că suma crește din 6 în 6.

În C++, while (conditie) corp; este repetarea cu test inițial: condiția se evaluează înaintea fiecărei execuții a corpului, iar ciclul se încheie la prima evaluare falsă. Numărul de execuții ale corpului poate fi 0. O variabilă care apare în condiție trebuie să aibă valoare înainte de primul test și trebuie modificată în corp (sau prin citire), altfel condiția își păstrează valoarea și ciclul nu se mai termină. Numărul de teste este cu unul mai mare decât numărul de execuții ale corpului.

Exemplul 1 — jetoane până la 3. Se pornește de la 0 jetoane și se adaugă câte unul cât timp numărul lor este mai mic decât 3.

#include <iostream>
using namespace std;
int main() {
    int jetoane = 0;
    while (jetoane < 3) {
        ++jetoane;
    }
    cout << jetoane;
    return 0;
}

Testele se fac pentru 0, 1, 2 și 3; corpul se execută numai pentru primele trei valori, deci sunt 4 teste și 3 execuții. Ieșirea este 3. Dacă începi cu jetoane = 3, primul test este fals și corpul nu se execută deloc.

Exemplul 2 — primul moment în care suma depășește o limită. Se adună pe rând numerele 1, 2, 3, ... cât timp suma este cel mult 20. Cerința este ultimul număr adunat.

1. Inițial $s=0$ și $k=0$; testul $0\le 20$ este adevărat.
2. $k=1$, $s=1$; apoi $k=2$, $s=3$; $k=3$, $s=6$; $k=4$, $s=10$; $k=5$, $s=15$ (testele $1,3,6,10,15\le 20$ sunt adevărate).
3. $k=6$, $s=21$; testul $21\le 20$ este fals și ciclul se oprește.

int s = 0, k = 0;
while (s <= 20) {
    k++;
    s += k;
}
cout << k << ' ' << s;

Secvența afișează 6 21: ultimul număr adunat este 6, iar suma 21 este prima care depășește 20.

Exemplul 3 — împărțiri repetate. Câte împărțiri la 2 trebuie făcute pentru ca numărul 100 să ajungă sub 1? Se împarte întreg: 100, 50, 25, 12, 6, 3, 1, 0. Ciclul while (n > 0) { n /= 2; pasi++; } face 7 execuții și se oprește când $n=0$. Rezultatul 7 este $[{\log }_{2}100]+1$, adică numărul de cifre binare ale lui 100. Fiecare execuție înjumătățește valoarea, de aceea ciclul se termină repede chiar pentru valori mari.

Ciclul care nu se oprește și ciclul care nu începe. Dacă în corp nu se schimbă nimic din condiție, de pildă while (jetoane < 3) { cout << 'x'; }, condiția rămâne adevărată la infinit. Invers, while (n > 0) cu $n=0$ nu execută corpul, iar while (n > 0) cu $n=-4$ nu îl execută nici el. Un ciclu cu test inițial este potrivit când nu se știe dinainte dacă trebuie făcut vreun pas.

Exemplul 4 — citirea până la o valoare-santinelă. Se citesc numere până apare 0, iar programul afișează suma lor. Prima valoare se citește înainte de ciclu, ca primul test să aibă ce compara, iar următoarea se citește la sfârșitul corpului, ca fiecare test să primească o valoare nouă.

int x, s = 0;
cin >> x;
while (x != 0) {
    s += x;
    cin >> x;
}
cout << s;

Pentru intrarea 4 7 0 testele sunt $4\ne 0$, $7\ne 0$ și $0\ne 0$; primele două sunt adevărate, deci $s=4+7=11$ și se afișează 11. Dacă prima valoare citită este 0, corpul nu se execută și se afișează 0. Dacă lipsește citirea de la sfârșitul corpului, $x$ rămâne 4 și ciclul nu se mai oprește.

La o urmărire, numără testele separat de execuțiile corpului: exemplul cu jetoane are patru teste și trei execuții. Dacă valoarea de control crește cu 2 pornind de la 0 și condiția este „mai mic decât 5”, corpul se execută pentru 0, 2 și 4, apoi se oprește la 6: valoarea de după ultima modificare este 6, deși nu mai intră în corp. Forma de pseudocod de la Bac este „cât timp condiție execută …”. Pentru x←1; cât timp x<4 execută scrie x; x←x+1 se afișează 1, 2, 3, iar ultimul test, la $x=4$, este fals. Dacă enunțul întreabă „de câte ori se execută corpul”, nu număra testul final; dacă întreabă „de câte ori se evaluează condiția”, adaugă-l.

Atenție la pasul de modificare: pentru n = 5 și ciclul while (n != 0) n -= 2; valorile sunt 5, 3, 1, $-1$, $-3$, ... și condiția $n\ne 0$ rămâne mereu adevărată, pentru că $n$ sare peste 0, deci ciclul nu se termină. Cu testul n > 0 ciclul s-ar fi oprit după trei execuții.

Exemplu în formatul examenului. Ce se afișează în urma executării secvenței de mai jos?

int x = 1, k = 0;
while (x < 100) {
    x = x * 3;
    k++;
}
cout << x << ' ' << k;

• a) 81 4
• b) 243 5
• c) 243 4
• d) 100 5

Răspunsul corect este b). Valorile lui $x$ după fiecare execuție sunt 3, 9, 27, 81, 243, iar $k$ crește de la 1 la 5. Testul $81<100$ este adevărat, deci corpul se execută încă o dată; testul $243<100$ este fals. Varianta a) se oprește prea devreme, la 81, care este încă mai mic decât 100, iar varianta d) presupune că ciclul se oprește exact la prag.

Greșeli frecvente

• Greșit: corpul lui while se execută obligatoriu măcar o dată.
  Corect: dacă primul test este fals, nu se execută deloc.
• Greșit: ultimul test, cel care dă fals, nu contează la urmărire.
  Corect: el explică oprirea și poate schimba numărul total de teste.
• Greșit: condiția va deveni falsă fără ca algoritmul să schimbe ceva relevant.
  Corect: este necesar un progres spre oprire.

Înainte și după