Numărarea valorilor

Când vrem să aflăm câte valori respectă o regulă, folosim un contor. De pildă, din scorurile $[3,4,6,9]$, două sunt pare: 4 și 6. Întrebarea nu cere suma lor, ci numărul lor, adică 2.

Pornim contorul de la zero, pentru că înainte de a examina vreun scor nu am găsit nimic. Citim prima valoare, 3: nu este pară, deci contorul rămâne 0. Citim 4: este pară, deci contorul devine 1. Citim 6: devine 2. Citim 9: rămâne 2. Acesta este rezultatul după ce am verificat toate cele patru valori.

Regula poate fi alta: „mai mare decât 5”, „egal cu 4” sau „negativ”. Pentru șirul $[3,4,6,9]$, valorile mai mari decât 5 sunt 6 și 9, deci tot două; valoarea 4 apare o singură dată. Refolosim aceeași metodă, dar schimbăm testul. Dacă nicio valoare nu respectă regula, răspunsul este zero.

Este util să scrii un mic tabel cu două coloane: valoarea citită și contorul după citire. Astfel vezi exact când contorul crește. Nu îl mărești la fiecare pas, ci numai când valoarea curentă trece testul. Într-un program, această operație are loc în interiorul unei parcurgeri; valorile pot fi procesate imediat ce sunt citite.

Exemplu rezolvat — câte note sunt cel puțin 5. Notele unui elev sunt $[7,5,9,4,10]$ și vrei să știi câte dintre ele sunt promovate, adică cel puțin 5. Folosești un contor care pornește de la 0 și îl crești numai când nota trece testul.

1. Nota 7: este cel puțin 5, deci contorul devine 1.
2. Nota 5: este cel puțin 5 (testul include egalitatea), deci contorul devine 2.
3. Nota 9: contorul devine 3.
4. Nota 4: este sub 5, deci contorul rămâne 3.
5. Nota 10: contorul devine 4.

Rezultatul este 4. Dacă ai fi scris testul „mai mare decât 5”, nota 5 nu ar fi fost numărată și ai fi obținut 3, un răspuns greșit pentru întrebarea pusă. Dacă nicio notă nu ar fi trecut testul, contorul ar fi rămas 0, iar „zero” este un răspuns valid, nu o lipsă de răspuns.

Numărarea elementelor care au o proprietate folosește un contor inițializat cu 0, care crește cu 1 de fiecare dată când elementul curent îndeplinește condiția. La sfârșitul parcurgerii, contorul este numărul căutat. Condiția poate fi simplă (x % 2 == 0, x > 5, x == k) sau compusă (x > 0 && x % 2 == 0). Dacă nicio valoare nu o îndeplinește, rezultatul este 0. Algoritmul parcurge șirul o singură dată, deci timpul este proporțional cu numărul $n$ de termeni, iar memoria auxiliară este constantă. Invariantul este: după prelucrarea primelor $k$ valori, contorul este numărul valorilor dintre ele care respectă condiția.

Exemplul 1 — valorile pozitive dintr-un șir cu marcaj.

cnt = 0
x = int(input())
while x != 0:
    if x > 0:
        cnt += 1
    x = int(input())
print(cnt)

Intrarea se dă câte un număr pe linie: 3, -2, 5, 0. După citirea lui 3, cnt = 1; după $-2$ rămâne 1; după 5 devine 2. Ultima citire dă marcajul 0, condiția x != 0 este falsă și se afișează 2. Dacă prima valoare este 0, corpul nu se execută și ieșirea este 0.

Exemplul 2 — mai multe întrebări despre aceeași listă. Pentru lista $[3,4,6,9,2,8]$:

v = [3, 4, 6, 9, 2, 8]
pare = 0
egale_cu_4 = 0
for x in v:
    if x % 2 == 0:
        pare += 1
    if x == 4:
        egale_cu_4 += 1
maxim = max(v)
egale_cu_maxim = 0
for x in v:
    if x == maxim:
        egale_cu_maxim += 1
print(pare, egale_cu_4, egale_cu_maxim)

Valorile pare sunt 4, 6, 2 și 8, deci pare este 4; valoarea 4 apare o dată; maximul este 9 și apare o dată. Programul afișează 4 1 1. Cele două condiții din corp sunt independente, deci se scriu ca două instrucțiuni if separate, nu if și elif: valoarea 4 este și pară, și egală cu 4, deci mărește ambele contoare, iar cu elif al doilea contor nu ar fi crescut. Numărul aparițiilor maximului cere două parcurgeri: întâi se află maximul, apoi se numără valorile egale cu el. O singură parcurgere nu ajunge decât dacă se actualizează contorul de fiecare dată când apare un maxim nou.

Exemplul 3 — numărarea perechilor de vecini. Pentru $[3,5,4,7,9]$ se numără câte creșteri apar între termeni consecutivi: $(3;5)$ crește, $(5;4)$ scade, $(4;7)$ crește, $(7;9)$ crește. Sunt 3 creșteri. Un șir cu $n$ termeni are $n-1$ perechi de vecini, deci ciclul compară v[i] cu v[i + 1] pentru $i$ de la 0 la $n-2$; dacă ar merge până la $n-1$, ar citi în afara șirului. În același fel, pentru a număra perechile de valori egale învecinate se compară v[i] cu v[i + 1] și se mărește contorul când sunt egale; în $[2,2,2,5]$ sunt două astfel de perechi.

Exemplul 4 — condiție compusă pe un interval. Se numără câte valori din lista $[12,7,20,25,10,10,31]$ aparțin intervalului $[10;20]$. Condiția are două părți, iar ambele trebuie să fie adevărate.

v = [12, 7, 20, 25, 10, 10, 31]
cnt = 0
for x in v:
    if 10 <= x and x <= 20:
        cnt += 1
print(cnt)

Contorul după fiecare valoare citită este 1, 1, 2, 2, 3, 4, 4, deci programul afișează 4. Capetele intervalului, 10 și 20, aparțin lui, iar valoarea 10 apare de două ori și se numără de fiecare dată. Dacă în loc de and s-ar scrie or, orice număr ar trece testul, pentru că fiecare valoare este fie cel puțin 10, fie cel mult 20, iar rezultatul ar fi 7, adică toate valorile.

Greșeli frecvente

• Greșit: contorul se mărește la fiecare valoare citită.
  Corect: se mărește numai când valoarea respectă condiția.
• Greșit: dacă nicio valoare nu respectă regula, nu există răspuns.
  Corect: răspunsul este 0.
• Greșit: „cel puțin 5” se verifică cu x > 5.
  Corect: se verifică cu x >= 5.

Înainte și după