7.1. Lista ca model conceptual

O structură liniară descrie date așezate într-o succesiune: primul element, al doilea, al treilea și așa mai departe. Ordinea elementelor face parte din model.

În acest capitol folosim modelul conceptual liniar pentru a înțelege algoritmi de prelucrare a datelor. Operațiile specifice clasei list din Python vor fi dezvoltate sistematic în Capitolul 8.

Accesul direct

La acces direct, poziția elementului ne permite să ajungem direct la acesta. În Python, indexarea începe de la 0. Pentru șirul [4, 7, 2, 9, 5], valoarea de la indexul 2 este 2.

Accesul secvențial

La acces secvențial, elementele sunt analizate în ordine, unul după altul. Este natural atunci când vrem să verificăm sau să prelucrăm toate valorile.

Parcurgerea liniară

O parcurgere liniară vizitează fiecare element o singură dată. În timpul parcurgerii putem actualiza o sumă, un contor, un minim, un maxim sau o variabilă logică. Pentru n elemente, timpul de lucru este, în general, proporțional cu n, adică O(n).

Imaginează-ți un rând de cutii numerotate. Dacă vrei să verifici toate cutiile, le examinezi de la prima la ultima. Dacă știi numărul unei cutii și modelul permite accesul direct, poți ajunge la poziția respectivă fără să verifici toate cutiile dinainte.

Parcurgere folosind indexul

valori = [4, 7, 2, 9, 5]
suma = 0

for i in range(len(valori)):
    suma = suma + valori[i]

print(suma)

Variabila i reprezintă indexul curent. Pentru această secvență, valorile lui i sunt 0, 1, 2, 3 și 4.

Prelucrare fără memorarea întregului șir

n = int(input())
suma = 0

for i in range(n):
    x = int(input())
    suma = suma + x

print(suma)

A doua variantă citește fiecare valoare și o prelucrează imediat. Nu este necesară memorarea tuturor valorilor.

ALGORITM SumaSir
    citește n
    suma ← 0
    pentru i ← 1,n execută
        citește x
        suma ← suma + x
    sfârșit pentru
    scrie suma
SFÂRȘIT ALGORITM

Același model de parcurgere poate fi adaptat pentru numărare, minim, maxim sau alte prelucrări.

Problemă

Se citesc n numere întregi. Determinați suma lor, numărul valorilor pare, minimul și maximul.

Analiză

Datele de intrare sunt n și cele n valori. Toate cele patru rezultate pot fi actualizate în aceeași parcurgere. Nu este necesară o a doua parcurgere.

Algoritm

citește n
citește primul x
suma ← x
minim ← x
maxim ← x
pare ← 0
dacă x mod 2 = 0 atunci
    pare ← 1
sfârșit dacă

pentru restul valorilor execută
    citește x
    suma ← suma + x
    dacă x < minim atunci minim ← x
    dacă x > maxim atunci maxim ← x
    dacă x mod 2 = 0 atunci pare ← pare + 1
sfârșit pentru

scrie suma, pare, minim, maxim

Python

n = int(input())
x = int(input())

suma = x
minim = x
maxim = x
pare = 0

if x % 2 == 0:
    pare = 1

for i in range(1, n):
    x = int(input())
    suma = suma + x

    if x < minim:
        minim = x
    if x > maxim:
        maxim = x
    if x % 2 == 0:
        pare = pare + 1

print("Suma:", suma)
print("Pare:", pare)
print("Minim:", minim)
print("Maxim:", maxim)

Urmărirea variabilelor

Testare

Caz normal: 4, 7, 2, 9, 5 → suma 27, două valori pare, minim 2, maxim 9.

Caz-limită: n=1, x=8 → suma 8, o valoare pară, minim=8, maxim=8.

Caz particular: toate valorile impare → numărul valorilor pare este 0.

Justificarea soluției

După fiecare pas, suma reprezintă suma valorilor deja citite, minim și maxim sunt extremele acestora, iar pare este numărul valorilor pare întâlnite. Prin urmare, după ultima valoare, rezultatele sunt cele cerute.

1. Se citesc n numere. Determinați suma.
2. Determinați numărul valorilor negative.
3. Determinați minimul și maximul.
4. Determinați suma valorilor divizibile cu 3.
5. Determinați numărul valorilor egale cu 0 și al celor diferite de 0.

6. Determinați suma valorilor pozitive și suma valorilor negative într-o singură parcurgere.
7. Pentru n temperaturi determinați amplitudinea: maxim − minim.
8. Explicați de ce două rezultate independente pot fi calculate în aceeași parcurgere.
9. Pentru 3,-2,8,0,-5,4 determinați suma pozitivă și numărul negativelor.