8.5. Parcurgerea și prelucrarea listelor – algoritmi de bază și aplicații

Am învățat să memorăm, să accesăm, să căutăm și să modificăm liste. Acum reunim aceste operații cu structurile repetitive studiate anterior.

Ce înseamnă parcurgerea?

Parcurgerea unei liste înseamnă examinarea elementelor sale, unul câte unul, pentru a realiza o prelucrare. Parcurgerea secvențială examinează fiecare element într-o ordine stabilită, de regulă de la primul la ultimul.

Două forme utile

Forma for x in L este potrivită când ne interesează valorile. Forma for i in range(len(L)) este potrivită când avem nevoie și de indice.

Modele de prelucrare

Pentru sumă folosim un acumulator inițializat cu 0. Pentru produs folosim un acumulator inițializat cu 1. Pentru minim și maxim este sigur să folosim primul element drept valoare inițială, apoi să comparăm restul elementelor.

Pentru numărare folosim un contor inițializat cu 0 și îl incrementăm atunci când condiția este adevărată. Pentru selecție construim o listă nouă și adăugăm elementele care respectă o condiție, folosind append().

Suma

L = [4, 7, 2, 9]
s = 0
for x in L:
    s = s + x
print(s)

Numărare

L = [3, 5, 8, 10, 7]
numar = 0
for x in L:
    if x >= 8:
        numar = numar + 1
print(numar)

Selectare

L = [8, 3, 10, 5, 12]
selectate = []
for x in L:
    if x % 2 == 0:
        selectate.append(x)
print(selectate)

Minim și maxim cu indici

L = [7, 4, 12, 3]
minim = L[0]
maxim = L[0]
for i in range(1, len(L)):
    if L[i] < minim:
        minim = L[i]
    if L[i] > maxim:
        maxim = L[i]
print(minim, maxim)

ALGORITM Suma
    suma ← 0
    pentru fiecare x din L execută
        suma ← suma + x
    sfârșit pentru
    afișează suma
SFÂRȘIT ALGORITM

ALGORITM Numărare
    numar ← 0
    pentru fiecare x din L execută
        dacă x îndeplinește condiția atunci
            numar ← numar + 1
        sfârșit dacă
    sfârșit pentru
    afișează numar
SFÂRȘIT ALGORITM

ALGORITM Selectare
    S ← listă vidă
    pentru fiecare x din L execută
        dacă x îndeplinește condiția atunci
            adaugă x în S
        sfârșit dacă
    sfârșit pentru
    afișează S
SFÂRȘIT ALGORITM

• Nu inițializa produsul cu 0.
• Pentru minim și maxim, inițializarea cu 0 poate fi greșită când toate valorile sunt pozitive sau toate sunt negative.
• Pentru o listă vidă nu putem folosi direct L[0]. Problemele care cer primul element trebuie să precizeze n>0 sau să trateze lista vidă.
• Nu modifica lista în timp ce o parcurgi fără un motiv clar; pentru selecție este mai sigur să construiești o listă nouă.
• Testarea trebuie să includă valori normale, caz-limită și cazuri particulare relevante.

1. Calculează suma elementelor din [2,4,6,8].
2. Calculează produsul elementelor din [2,3,4].
3. Numără elementele pare din [1,2,4,7,8].
4. Determină minimul și maximul din [9,3,12,5].
5. Construiește lista numerelor pozitive din [-3,5,0,7,-2].

1. Determină suma elementelor divizibile cu 3 dintr-o listă.
2. Construiește lista valorilor mai mari decât media aritmetică.
3. Determină câte elemente au doi vecini și sunt pare, folosind indicii; tratează corect extremitățile.
4. Pentru o listă de note, determină media, numărul notelor cel puțin egale cu 9 și lista notelor sub 5.
5. Compară o soluție care face două parcurgeri cu una care acumulează toate informațiile posibile într-o singură parcurgere.