Repetarea cu contor

Când știi câți pași trebuie să faci, poți folosi o repetare cu contor. Contorul este o variabilă care arată la ce pas ai ajuns. Dacă vrei să bați din palme de patru ori, numeri 1, 2, 3, 4; după pasul 4 te oprești. Nu trebuie să întrebi după fiecare pas câte palme au fost în total: contorul ține evidența.

Imaginează-ți că pui câte 3 pietricele în fiecare dintre patru cutii. Pentru cutia 1 pui 3, pentru cutia 2 încă 3, apoi pentru 3 și 4 la fel. Numărul total crește: 3, 6, 9, 12. Ai executat același pas de patru ori, iar la final ai $4\cdot 3=12$ pietricele. Contorul indică numărul cutiei; totalul este altă variabilă, care ține suma.

La o repetare cu contor trebuie să spui valoarea de început, valoarea de sfârșit și cum se schimbă contorul. Dacă numeri de la 1 la 4 inclusiv, ai patru pași. Dacă numeri de la 0 la 3 inclusiv, tot patru pași. Dar de la 0 la 4 inclusiv ai cinci pași. Limitele sunt la fel de importante ca operația repetată.

Pentru a verifica algoritmul, scrie un tabel cu două coloane: contorul și totalul după pas. Tabelul din exemplu are perechile $(1,3)$, $(2,6)$, $(3,9)$ și $(4,12)$. Nu confunda valoarea contorului cu numărul de pietricele; cele două cresc după reguli diferite.

Exemplu rezolvat — primii cinci multipli ai lui 4. Contorul ia pe rând valorile 1, 2, 3, 4 și 5, iar la fiecare pas se scrie produsul $4\cdot$contor.

1. Contorul este 1: se scrie $4\cdot 1=4$.
2. Contorul este 2: se scrie $4\cdot 2=8$.
3. Contorul este 3: se scrie $4\cdot 3=12$.
4. Contorul este 4: se scrie $4\cdot 4=16$.
5. Contorul este 5: se scrie $4\cdot 5=20$.
6. Contorul ar deveni 6, care depășește limita 5, deci repetarea se oprește.

Rezultatul este lista 4, 8, 12, 16, 20, adică cinci numere pentru cinci pași. Contorul arată al câtelea multiplu scrii, iar produsul este valoarea scrisă; sunt două variabile diferite, deși cresc amândouă.

Repetarea cu număr cunoscut de pași se scrie în C++ cu for (inițializare; condiție; actualizare) corp. Inițializarea se execută o dată, condiția se verifică înaintea fiecărei execuții a corpului, iar actualizarea se face după fiecare execuție. Pentru for (int i = a; i <= b; ++i), corpul se execută de $b-a+1$ ori dacă $a\le b$ și de zero ori dacă $a>b$. Cu pasul $p>0$, în for (int i = a; i <= b; i += p), numărul execuțiilor este $\left[\frac{b-a}{p}\right]+1$ pentru $a\le b$. Contorul poate și descrește: for (int i = 5; i >= 1; --i).

Exemplul 1 — patru cutii. În fiecare dintre patru cutii se pun câte 3 pietricele; contorul numără cutiile, iar total adună pietricelele.

#include <iostream>
using namespace std;
int main() {
    int total = 0;
    for (int cutie = 1; cutie <= 4; ++cutie) {
        total += 3;
    }
    cout << total;
    return 0;
}

Corpul se execută pentru cutie egal cu 1, 2, 3 și 4; valorile lui total sunt 3, 6, 9 și 12, deci ieșirea este 12. Testul la cutie = 5 oprește repetarea.

Exemplul 2 — pas diferit de 1. Pentru for (int i = 2; i <= 20; i += 3), contorul ia valorile 2, 5, 8, 11, 14, 17 și 20. Numărul execuțiilor este $\left[\frac{20-2}{3}\right]+1=7$, iar suma valorilor este 77.

int s = 0, nr = 0;
for (int i = 2; i <= 20; i += 3) {
    s += i;
    nr++;
}
cout << nr << ' ' << s;

Secvența afișează 7 77. Valoarea 23, cu care contorul ajunge după ultima actualizare, nu mai intră în corp, pentru că $23\le 20$ este fals.

Exemplul 3 — contor descrescător și produs. Factorialul $5!=1\cdot 2\cdot 3\cdot 4\cdot 5$ se poate calcula parcurgând contorul de la 5 la 1: p pornește de la 1 și se înmulțește succesiv cu 5, 4, 3, 2 și 1, deci ia valorile 5, 20, 60, 120 și 120. Rezultatul final este 120, același ca la parcurgerea crescătoare, pentru că înmulțirea nu depinde de ordine.

Exemplul 4 — două contoare imbricate. Pentru fiecare valoare a contorului exterior i, contorul interior j parcurge toate valorile lui. Tabla înmulțirii pentru numerele de la 1 la 3 se scrie astfel:

for (int i = 1; i <= 3; ++i) {
    for (int j = 1; j <= 3; ++j)
        cout << i * j << ' ';
    cout << '\n';
}

Secvența afișează liniile 1 2 3, 2 4 6 și 3 6 9. Corpul interior se execută $3\cdot 3=9$ ori, deoarece pentru fiecare dintre cele 3 valori ale lui i se fac 3 execuții. Dacă limita interioară depinde de i, de exemplu j <= i, numărul execuțiilor este $1+2+3=6$.

Exemplul 5 — numărarea multiplilor. Se numără multiplii lui 3 dintre numerele de la 1 la 20: corpul testează fiecare valoare a contorului și crește un contor separat doar când restul împărțirii la 3 este 0.

int nr = 0;
for (int i = 1; i <= 20; ++i)
    if (i % 3 == 0)
        nr++;
cout << nr;

Testul reușește pentru 3, 6, 9, 12, 15 și 18, deci se afișează 6, adică partea întreagă a lui $20/3$. Ciclul face 20 de execuții, dar variabila nr crește numai de 6 ori: numărul de execuții al corpului și valoarea acumulată sunt lucruri diferite.

Cazuri-limită și capcane. Dacă limita este 0, ciclul for (int i = 1; i <= 0; ++i) nu execută corpul niciodată. Modificarea contorului în corp schimbă și numărul de execuții: în for (int i = 1; i <= 5; ++i) { i++; } corpul se execută pentru $i=1$, $i=3$ și $i=5$, deci de 3 ori, nu de 5. În sfârșit, un contor real nu se folosește pentru a număra: în for (double x = 0; x != 1; x += 0.1) suma celor zece adunări de 0,1 nu este exact 1, ci aproximativ 0,9999999999999999, deci testul x != 1 rămâne adevărat și ciclul nu se oprește.

Numără execuțiile din valorile atinse efectiv de contor, nu doar din diferența capetelor. Pentru for (int i = 2; i <= 8; i += 2) corpul se execută la 2, 4, 6 și 8: de patru ori. Dacă limita devine i < 8, corpul se execută de trei ori. La urmărire notează și valoarea care face testul fals, pentru că dacă variabila contor este declarată în afara ciclului, ea păstrează această valoare după ciclu. Forma de Bac este „pentru i←a,b[,pas] execută …”: cu pasul 1, $i$ ia valorile $a,a+1,\dots ,b$ dacă $a\le b$. Pentru $a=5$ și $b=3$ corpul nu se execută. Un for cu actualizare greșită, precum for (int i = 1; i <= 5; --i), nu se termină niciodată, deoarece $i$ se îndepărtează de limită.

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

int i, s = 0;
for (i = 1; i <= 10; i += 3)
    s += i;
cout << s << ' ' << i;

• a) 22 10
• b) 22 13
• c) 18 13
• d) 22 12

Răspunsul corect este b). Contorul ia valorile 1, 4, 7 și 10, iar suma lor este $1+4+7+10=22$. După ultima execuție, actualizarea i += 3 duce contorul la 13; testul $13\le 10$ este fals și ciclul se oprește, deci i rămâne 13. Varianta a) uită ultima actualizare, iar varianta c) omite valoarea 10 din sumă.

Aceeași numărare se face și când contorul scade: pentru for (i = 10; i > 0; i -= 4) corpul se execută la 10, 6 și 2, deci de trei ori, iar suma valorilor este 18. După ultima actualizare variabila $i$ are valoarea $-2$, pentru că testul $-2>0$ este fals.

Verifică numărul de execuții scăzând pas cu pas din 10 cât timp valoarea rămâne pozitivă: se obțin trei valori, nu două și nu patru.

Greșeli frecvente

• Greșit: de la 0 la 4 inclusiv sunt patru pași.
  Corect: valorile 0, 1, 2, 3, 4 dau cinci pași.
• Greșit: contorul și suma acumulată sunt aceeași variabilă.
  Corect: contorul arată pasul, iar acumulatorul păstrează totalul.
• Greșit: i < 4 și i <= 4 includ aceleași valori.
  Corect: a doua condiție include și valoarea 4.

Înainte și după