Structuri repetitive în C++

Calculatorul nu se plictisește niciodată: poate repeta aceeași operație de un miliard de ori fără să greșească. Ca să profiți de asta, ai nevoie de structuri repetitive (bucle). Cu ele aduni cifrele unui număr, cauți divizori, verifici dacă un număr este prim sau prelucrezi un șir întreg de valori. La BAC, aproape fiecare subiect de informatică conține cel puțin o buclă de urmărit „pe hârtie” sau de scris.

Instrucțiunea while

while (conditie)
{
    instructiuni;
}

Se evaluează condiția; dacă este adevărată, se execută corpul și se revine la testare. Bucla se oprește când condiția devine falsă. Este o structură cu test inițial: dacă de la început condiția este falsă, corpul nu se execută deloc.

Corpul trebuie să modifice ceva din condiție. Altfel obții o buclă infinită.

Instrucțiunea do-while

do
{
    instructiuni;
} while (conditie);

Este o structură cu test final: corpul se execută o dată, apoi se testează condiția. Prin urmare, corpul se execută cel puțin o dată. Atenție la ; după while (conditie).

Instrucțiunea for

for (int i = 1; i <= n; i++)
{
    instructiuni;
}

Are trei părți: inițializarea (int i = 1, o singură dată), condiția (testată înainte de fiecare pas) și actualizarea (i++, după fiecare pas). Se folosește când știi de câte ori repeți: bucla de mai sus are exact $n$ pași. Orice for se poate rescrie cu while.

Algoritmi cu cifrele unui număr

Toți folosesc aceeași idee: iei ultima cifră cu n % 10 și o elimini cu n / 10, până când n devine $0$.

Pentru numărul de cifre folosește do-while, ca $n = 0$ să fie numărat corect ca număr cu o cifră.

Divizori, numere prime și cmmdc

Divizorii lui $n$: d este divizor dacă n % d == 0. Divizorii vin în perechi $(d, \frac{n}{d})$, de aceea este suficient să parcurgi d cât timp d * d <= n.

Număr prim: are exact doi divizori, pe $1$ și pe el însuși. Numerele $0$ și $1$ nu sunt prime.

Algoritmul lui Euclid pentru $\text{cmmdc}(a, b)$, prin împărțiri repetate:

while (b != 0)
{
    int r = a % b;
    a = b;
    b = r;
}
// acum a este cmmdc-ul

Apoi $\text{cmmmc}(a, b) = \frac{a \cdot b}{\text{cmmdc}(a, b)}$, calculat cu valorile inițiale ale lui $a$ și $b$.

Exemple rezolvate

Exemplul 1: oglinditul unui număr

Pentru n = 1203, urmărim secvența inv = 0; while (n > 0) { inv = inv * 10 + n % 10; n = n / 10; }:

Rezultatul este $3021$. Un număr este palindrom dacă este egal cu oglinditul lui, de exemplu $1221$; pentru test, păstrează valoarea inițială într-o copie, pentru că bucla îl aduce pe n la $0$.

Exemplul 2: verificarea unui număr prim

int n, prim = 1;
cin >> n;
if (n < 2) prim = 0;
for (int d = 2; d * d <= n; d++)
    if (n % d == 0) prim = 0;
cout << (prim ? "DA" : "NU");

Pentru $n = 91$ se găsește divizorul $7$ ($91 = 7 \cdot 13$), deci se afișează NU. Pentru $n = 97$ se testează $d = 2, 3, \ldots, 9$ (pentru că $10 \cdot 10 > 97$), niciun $d$ nu îl divide, deci se afișează DA.

Exemplul 3: cmmdc și cmmmc

Pentru $a = 18$ și $b = 30$, algoritmul lui Euclid dă perechile

$$(18, 30) \to (30, 18) \to (18, 12) \to (12, 6) \to (6, 0),$$

deci $\text{cmmdc} = 6$ și $\text{cmmmc} = \frac{18 \cdot 30}{6} = 90$. Observă că, dacă $a < b$, primul pas doar interschimbă numerele.

Greșeli frecvente

• Bucla infinită. În while (n > 0) { s = s + n % 10; } lipsește n = n / 10;, deci n nu scade niciodată.
• ; după for sau while. for (i = 1; i <= n; i++); are corpul vid: instrucțiunea următoare se execută o singură dată, după buclă.
• Numărul $0$ la cifre. Cu while (n > 0), numărul $0$ pare să aibă $0$ cifre. Folosește do-while pentru numărarea cifrelor.
• Valoarea inițială pierdută. După o buclă care împarte n la $10$, n este $0$. Dacă îți mai trebuie, salvează-l înainte.
• $1$ considerat prim. Un număr prim are exact doi divizori distincți; $1$ are unul singur.
• Numărarea pașilor. for (i = 1; i < n; i++) are $n - 1$ pași, nu $n$. Verifică mereu prima și ultima valoare a contorului.

Pe scurt

• while testează condiția înainte de corp, do-while după corp (corpul rulează cel puțin o dată), iar for este potrivit când știi numărul de pași.
• Cifrele unui număr se prelucrează cu n % 10 (ultima cifră) și n / 10 (eliminarea ei), până la $n = 0$.
• d divide n dacă n % d == 0; pentru numere prime este suficient să testezi divizorii cu d * d <= n.
• Algoritmul lui Euclid calculează cmmdc-ul prin resturi repetate; cmmmc-ul este produsul împărțit la cmmdc.