Șiruri de valori

Un șir de valori este o listă în care ordinea contează. Numărul de pași făcuți de Ana de luni până vineri ar putea fi $[4,6,4,8,5]$ mii de pași. Șirul are cinci valori. Prima și a treia sunt egale, dar ocupă locuri diferite. Dacă schimbăm ordinea, povestea zilelor se schimbă, chiar dacă valorile rămân aceleași.

Pentru a lucra cu un șir, hotărâm ce vrem să aflăm: câte valori respectă o regulă, care este suma, care este cea mai mică valoare sau dacă apare măcar o valoare anume. În șirul $[4,6,4,8,5]$, de exemplu, numărul 4 apare de două ori. Pentru a nu omite o zi, citim valorile în ordine și ținem evidența a ceea ce am găsit.

Uneori valorile sosesc pe rând, ca scorurile anunțate în timpul unui joc. Poți calcula suma pe măsură ce le primești, fără să păstrezi toate scorurile. Alteori ai nevoie să revii la o anumită poziție; atunci le păstrezi într-un tablou. Șirul este ideea de valori ordonate, iar tabloul este una dintre formele în care un program le poate memora.

Aceeași idee ajută la citire, parcurgere, numărare, sumă, verificarea unei proprietăți și generarea unui șir după o regulă. La generare cunoști unul sau mai mulți termeni de început și regula pentru termenul următor; termenii se calculează în ordine.

Șirul poate avea un număr de termeni dat la început sau se poate încheia la un marcaj. Dacă prima valoare este $n=3$, următoarele trei valori 4, 5, 6 sunt termenii. Dacă în schimb formatul spune „citește până la 0”, intrarea 4, 5, 6, 0 conține trei termeni, iar 0 marchează sfârșitul și nu se prelucrează. Aceste două convenții nu se amestecă.

Exemplu rezolvat — două formate de intrare. Ana a notat numărul de kilometri parcurși în trei zile: 4, 5 și 6. Aceeași informație poate fi dată în două feluri.

1. Primul format: 3 4 5 6. Prima valoare este $n=3$, numărul de termeni; ea nu face parte din șir. Urmează exact trei valori: 4, 5, 6.
2. Al doilea format: 4 5 6 0. Valoarea 0 este un marcaj de sfârșit; ea anunță că nu mai urmează alte valori și nu se prelucrează.
3. În ambele cazuri șirul are trei termeni, suma lor este $4+5+6=15$, iar ordinea lor este aceeași.

Dacă ai citi marcajul 0 ca pe un termen, ai număra patru valori și ai greși media: $15/4$ în loc de $15/3=5$. De aceea, întâi afli ce format folosește problema, apoi citești.

Un șir de valori este o succesiune de termeni în care contează atât valorile, cât și ordinea lor: $[4,6,4,8,5]$ și $[8,6,5,4,4]$ au aceleași valori, dar sunt șiruri diferite. Termenii se numerotează: primul este $a_1$, al doilea $a_2$ și așa mai departe. Numărul de termeni poate fi dat la început (n, apoi cei n termeni) sau șirul se încheie la un marcaj, o valoare convenită care nu aparține șirului, de pildă 0 sau $-1$. Prelucrările uzuale sunt: citirea, parcurgerea, numărarea elementelor cu o proprietate, suma și produsul, găsirea celui mai mic sau a celui mai mare termen, verificarea unei proprietăți și generarea după o regulă. Unele se fac pe măsură ce valorile sosesc, fără a le memora; altele cer revenirea la termenii citiți, deci memorarea într-un tablou.

Exemplul 1 — generarea după o regulă. Primul termen este 3, iar fiecare termen următor este dublul celui precedent: $a_{k+1}=2a_k$. Pentru cinci termeni se pornește de la 3 și se obține $6$, apoi $12$, apoi $24$, apoi $48$. Șirul este $[3,6,12,24,48]$. Numărul 5 arată câți termeni se afișează, deci 96 nu se mai calculează. Regula se aplică valorii precedente, nu poziției termenului.

termen = 3
for _ in range(5):
    print(termen, end=" ")
    termen = termen * 2

Programul afișează 3 6 12 24 48 . Variabila termen păstrează la fiecare pas termenul curent, iar după ultima afișare ea ajunge la 96, valoare care nu se afișează.

Exemplul 2 — prelucrare pe măsură ce citești. Se citesc valorile 4, 5, 6 și apoi marcajul 0. După primul termen suma este 4, după al doilea este 9, iar după al treilea este 15. Pentru sumă nu trebuie memorat tot șirul: păstrezi totalul curent și adaugi fiecare valoare citită. Valoarea 0 este marcaj, deci nu intră în sumă.

suma = 0
x = int(input())
while x != 0:
    suma += x
    x = int(input())
print(suma)

Pentru intrarea 4, 5, 6, 0 (câte un număr pe linie) programul afișează 15. Dacă problema cere ulterior un termen de la o anumită poziție, sau compararea fiecărui termen cu media, valorile trebuie păstrate în tablou, pentru că suma se cunoaște abia după ce au fost citite toate.

Exemplul 3 — ce se poate afla din același șir. Pentru $[4,6,4,8,5]$ (numărul de mii de pași făcuți de Ana de luni până vineri) se pot pune mai multe întrebări. Suma este $4+6+4+8+5=27$, iar media pe cele 5 zile este $27/5=5,4$. Valoarea 4 apare de două ori, pe pozițiile 1 și 3. Cea mai mică valoare este 4, iar cea mai mare este 8, pe poziția 4. Fiecare întrebare cere o altă prelucrare, dar toate pornesc de la aceeași parcurgere în ordine.

Convenții care nu se amestecă. Dacă prima valoare este $n=3$, următoarele trei valori sunt termenii, iar dacă intrarea mai conține și un marcaj, el nu se numără. În formatul cu marcaj, un șir poate fi gol: intrarea 0 conține zero termeni, iar suma lor este 0.

Greșeli frecvente

• Greșit: $[2,3]$ și $[3,2]$ sunt același șir.
  Corect: au aceleași valori, dar ordinea diferă.
• Greșit: o valoare repetată se numără o singură dată.
  Corect: fiecare apariție ocupă o poziție.
• Greșit: orice șir trebuie memorat integral.
  Corect: unele calcule se fac pe măsură ce valorile sunt citite.

Înainte și după