Citirea și parcurgerea șirurilor

A citi un șir înseamnă să primești valorile sale. A-l parcurge înseamnă să le examinezi, una câte una, într-o ordine stabilită. Dacă ai notat temperaturile de la patru ore: $[18,20,21,19]$, o parcurgere de la stânga la dreapta vede întâi 18, apoi 20, apoi 21 și, la urmă, 19.

Adesea prima informație este numărul valorilor, numit $n$. Dacă $n=4$, trebuie să citești exact patru valori. Un contor te ajută: pornește de la 1, citește câte o valoare și crește după fiecare citire; te oprești după a patra. Pentru intrarea 4 18 20 21 19, numărul 4 arată câte temperaturi urmează; nu este el însuși o temperatură.

La fiecare pas poți face o acțiune: să afișezi valoarea, să o aduni sau să verifici o condiție. O singură parcurgere poate fi suficientă dacă nu ai nevoie să revii la valorile vechi. Dacă vrei să afișezi mai întâi toate temperaturile și apoi să le compari cu media, le poți memora pentru a le reciti.

Nu confunda poziția cu valoarea. În exemplu, a treia poziție conține 21; „3” arată locul, nu temperatura. Într-un program, convenția pozițiilor poate începe de la 0 sau de la 1, dar trebuie păstrată consecvent. Încearcă să urmărești cu degetul șirul în timp ce rostești poziția și valoarea fiecărui element.

Exemplu rezolvat — temperaturile de la patru ore. Intrarea este 4 18 20 21 19: prima valoare, 4, spune câte temperaturi urmează, iar restul sunt temperaturile. Vrei temperatura cea mai mare și media.

1. Citești $n=4$ și pregătești un contor care pornește de la 0, o sumă 0 și un maxim provizoriu.
2. Citești 18: suma devine 18, maximul 18, contorul 1.
3. Citești 20: suma devine 38, maximul 20, contorul 2.
4. Citești 21: suma devine 59, maximul 21, contorul 3.
5. Citești 19: suma devine 78, maximul rămâne 21, contorul 4; ai citit exact $n$ valori și te oprești.
6. Media este $78:4=19,5$, iar cea mai mare temperatură este 21.

Ai folosit o singură parcurgere, fără să revii la valorile vechi. Dacă ai fi vrut să afișezi pe urmă temperaturile mai mari decât media, ar fi trebuit să le păstrezi, pentru că media se cunoaște abia după ultima citire.

Citirea aduce valorile șirului în program; parcurgerea le examinează pe rând, într-o ordine fixată, de obicei de la primul la ultimul. Intrarea poate fi dată în trei feluri: cu numărul de termeni înaintea lor (n urmat de $n$ valori), cu un marcaj la sfârșit, sau fără marcaj, până la sfârșitul datelor. Când parcurgerea trebuie făcută o singură dată, valorile se prelucrează imediat ce sunt citite și nu se memorează; memorarea într-un tablou este necesară dacă ai de comparat fiecare valoare cu un rezultat care se află abia la sfârșit (media, maximul) sau dacă o parcurgi de mai multe ori. Poziția unui element nu se confundă cu valoarea lui, iar numerotarea pozițiilor (de la 0 sau de la 1) se precizează.

Exemplul 1 — suma fără memorare (Python). Se cunoaște numărul de valori, $n=3$, iar valorile sunt 4, 1, 5.

n = 3
valori = [4, 1, 5]
suma = 0
for x in valori:
    suma += x
print(suma)

Sumele parțiale sunt 4, 5 și 10, deci se afișează 10. La citirea de la tastatură lista se construiește cu [int(input()) for _ in range(n)], dar pentru o singură sumă bucla poate citi și aduna direct, fără listă.

Exemplul 2 — două parcurgeri (C++). Se citesc $n$ valori și se afișează câte dintre ele sunt strict mai mari decât media. Media se cunoaște după prima parcurgere, deci valorile se memorează.

#include <iostream>
using namespace std;
int main() {
    int n, v[100], suma = 0, cnt = 0;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
        suma += v[i];
    }
    double media = (double)suma / n;
    for (int i = 0; i < n; ++i)
        if (v[i] > media) ++cnt;
    cout << media << ' ' << cnt;
    return 0;
}

Pentru intrarea 4 18 20 21 19 suma este 78 și media este 19,5. Valorile strict mai mari decât media sunt 20 și 21, deci programul afișează 19.5 2. Valoarea 19 este sub medie, iar 18 de asemenea. Fără memorarea valorilor, a doua parcurgere nu ar fi posibilă.

Exemplul 3 — citirea până la sfârșitul datelor. Dacă numărul de valori nu este cunoscut și nu există marcaj, se citește cât timp citirea reușește: în C++ while (cin >> x), în Python for linie in sys.stdin. Pentru valorile 2 5 3 ciclul rulează de trei ori, iar suma ia valorile 2, 7 și 10.

Exemplul 4 — citirea cu marcaj la sfârșit (C++). Valorile sunt pozitive, iar un 0 încheie datele; marcajul nu face parte din șir.

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

Pentru intrarea 7 3 9 0 urmărirea este: se citește 7, suma 7, contorul 1; se citește 3, suma 10, contorul 2; se citește 9, suma 19, contorul 3; se citește 0 și condiția $x\ne 0$ devine falsă. Rezultatul este suma 19 pe 3 termeni, deci media $19:3\approx 6,33$. Prima citire se face înaintea ciclului, iar cea de după prelucrare pregătește următoarea verificare; fără a doua citire din corp, ciclul ar prelucra la nesfârșit aceeași valoare, 7.

Înainte de a împărți la $n$ se verifică dacă $n=0$: un șir fără termeni nu are medie, deci programul trebuie să afișeze un mesaj sau să ocolească împărțirea. La fel, dacă $n$ este mai mare decât capacitatea tabloului (100 în exemplul de mai sus), citirea ar scrie în afara lui; limita din enunț decide dimensiunea declarată.

Greșeli frecvente

• Greșit: prima valoare din intrare face întotdeauna parte din șir.
  Corect: dacă formatul spune că primul număr este $n$, el arată câte valori urmează și nu se prelucrează ca termen.
• Greșit: pentru orice problemă pe șiruri trebuie memorate toate valorile.
  Corect: suma, numărarea și extremele se pot calcula pe măsură ce valorile sunt citite.
• Greșit: poziția unui element este aceeași cu valoarea lui.
  Corect: poziția spune locul, iar valoarea spune ce este memorat acolo.

Înainte și după