Suma și produsul valorilor

Pentru a aduna valorile unui șir, folosim o sumă care se schimbă pe măsură ce citim fiecare valoare. La început suma este 0. Pentru șirul $[2,3,4]$, după prima valoare suma devine 2, după a doua devine 5, iar după a treia devine 9. Așadar $2+3+4=9$.

Pentru produs pornim de la 1. În același șir, produsul devine 2, apoi 6, apoi 24. Pornirea de la 0 ar strica rezultatul, deoarece orice număr înmulțit cu 0 dă 0. Numerele 0 pentru sumă și 1 pentru produs se numesc elemente neutre: dacă le folosim la început, nu schimbă rezultatul valorilor adăugate sau înmulțite ulterior.

Poți calcula ambele rezultate în aceeași parcurgere, dar păstrezi două valori separate: suma și produsul. Când citești un nou număr, îl adaugi la sumă și înmulțești produsul cu el. La șirul $[2,0,4]$, suma este 6, iar produsul este 0. Acest exemplu arată de ce nu trebuie să deduci unul dintre rezultate din celălalt.

Uneori problema cere doar suma valorilor care respectă o condiție, de exemplu doar a celor pare. Atunci verifici condiția înainte de a adăuga. Pentru $[2,3,4]$, suma valorilor pare este $2+4=6$, nu 9. Citește cu grijă întrebarea: „toate valorile” și „valorile pare” cer calcule diferite.

Exemplu rezolvat — suma și produsul unui șir cu o condiție. Pentru șirul $[2,3,4,5]$ vrei suma tuturor valorilor și produsul numai al celor impare. Folosești două variabile separate: suma pornește de la 0, iar produs de la 1.

1. Valoarea 2: suma devine 2; 2 este pară, deci produsul rămâne 1.
2. Valoarea 3: suma devine 5; 3 este impară, deci produsul devine 3.
3. Valoarea 4: suma devine 9; produsul rămâne 3.
4. Valoarea 5: suma devine 14; 5 este impară, deci produsul devine 15.

Rezultatul este suma 14 și produsul valorilor impare 15. Dacă produsul ar fi pornit de la 0, ar fi rămas 0 pe tot parcursul. Dacă șirul nu ar fi avut nicio valoare impară, produsul ar fi rămas 1, valoarea de pornire; de aceea problema precizează ce se afișează în acest caz.

O acumulare combină valorile șirului într-un singur rezultat, actualizat la fiecare termen. Suma pornește de la 0, elementul neutru al adunării, iar produsul de la 1, elementul neutru al înmulțirii: pornirea de la 0 ar anula orice produs. Dacă problema cere numai valorile care respectă o condiție, testul se face înainte de actualizare. Pentru un șir cu $n$ termeni se fac $n$ pași, deci timpul este proporțional cu $n$, iar memoria auxiliară este constantă. Dacă șirul este gol sau nicio valoare nu respectă condiția, acumulatorii rămân la valorile de pornire, 0 și 1.

Exemplul 1 — suma și produsul tuturor valorilor.

v = [2, 3, 4]
suma = 0
produs = 1
for x in v:
    suma += x
    produs *= x
print(suma, produs)

Perechile (sumă, produs) după fiecare termen sunt $(2;2)$, $(5;6)$ și $(9;24)$. Programul afișează 9 24. Pentru lista $[2,0,4]$ perechea finală este $(6;0)$: un factor 0 anulează produsul, dar nu și suma.

Exemplul 2 — acumulare condiționată. Pentru $[2,3,4,5,7]$ se cere suma valorilor pare și produsul celor impare:

v = [2, 3, 4, 5, 7]
suma_pare = 0
prod_impare = 1
for x in v:
    if x % 2 == 0:
        suma_pare += x
    else:
        prod_impare *= x
print(suma_pare, prod_impare)

Valorile pare sunt 2 și 4, cu suma 6; valorile impare sunt 3, 5 și 7, cu produsul $3\cdot 5\cdot 7=105$. Programul afișează 6 105.

Exemplul 3 — limitele tipului. Suma numerelor de la 1 la 100000 este $\frac{100000\cdot 100001}{2}=5000050000$, mai mare decât $2147483647$, valoarea maximă a tipului int. Acumulatorul trebuie declarat long long:

long long s = 0;
for (int i = 1; i <= 100000; ++i)
    s += i;
cout << s;

Secvența afișează 5000050000. Cu un acumulator int, rezultatul ar depăși domeniul și nu ar fi corect. Dacă problema cere produsul modulo $M$, actualizarea este $p\leftarrow (p\cdot x)\mathrm{mod}M$, ca valorile să rămână mici; media aritmetică se obține împărțind suma la numărul de termeni, cu un operand real.

Exemplul 4 — suma alternantă. Suma $1-2+3-4+5$ are semnele alternate. Se păstrează o variabilă semn, inițial $+1$, pe care o schimbi la fiecare termen: la termenul $k$ se adună semn * k, apoi semn = -semn. Termenii adunați sunt $+1,-2,+3,-4,+5$, iar sumele parțiale sunt $1,-1,2,-2,3$. Rezultatul final este 3.

semn = 1
s = 0
for k in range(1, 6):
    s += semn * k
    semn = -semn
print(s)

Programul afișează 3. Dacă schimbarea semnului ar fi făcută înaintea adunării, primul termen ar fi adunat cu minus și toate semnele ar fi inversate: s-ar obține $-3$.

Exemplul 5 — suma și produsul cifrelor. Cifrele unui număr se extrag cu n % 10, apoi se elimină prin n /= 10:

int n = 2305, s = 0, p = 1;
while (n > 0) {
    int c = n % 10;
    s += c;
    p *= c;
    n /= 10;
}
cout << s << ' ' << p;

Cifrele extrase sunt 5, 0, 3, 2, iar perechile (sumă, produs) sunt $(5;5)$, $(5;0)$, $(8;0)$ și $(10;0)$. Programul afișează 10 0. Cifra 0 anulează produsul din momentul în care apare, dar suma continuă să crească.

Exemplul 6 — produsul depășește repede tipul. Factorialul $12!=479001600$ încape în int, dar $13!=6227020800$ depășește $2147483647$. Un acumulator long long ajunge până la $20!=2432902008176640000$, iar $21!$ depășește și acest tip. La produse mari se folosește fie long long, fie rezultatul modulo un număr dat.

Media aritmetică și numărul de termeni. Media valorilor pozitive din șirul $2,-1,4,3$ se obține împărțind suma lor, $2+4+3=9$, la numărul lor, 3: media este $9/3=3$. Împărțirea se face doar dacă numărul termenilor este diferit de 0.

Greșeli frecvente

• Greșit: produsul pornește de la 0.
  Corect: pornește de la 1, elementul neutru al înmulțirii.
• Greșit: dintr-un produs 0 se deduce că și suma este 0.
  Corect: cele două rezultate sunt independente; la $[2,0,4]$ suma este 6, iar produsul 0.
• Greșit: la o sumă condiționată se adună toate valorile și apoi se scad cele care nu respectă condiția.
  Corect: se testează condiția înainte de a adăuga.

Înainte și după