7.4. Lista de frecvențe

Frecvența unei valori este numărul de apariții ale acelei valori într-o colecție.

O listă de frecvențe păstrează, pentru fiecare valoare dintr-un domeniu, numărul de apariții. Dacă citim valoarea x, incrementăm poziția corespunzătoare: frecventa[x] = frecventa[x] + 1.

Metoda este potrivită în special pentru domenii mici și cunoscute, de exemplu cifrele 0–9 sau notele 1–10. Domeniul trebuie cunoscut pentru dimensionarea structurii.

Valoarea și frecvența

Dacă frecventa[7] = 4, aceasta nu înseamnă că valoarea este 4. Înseamnă că valoarea 7 apare de 4 ori.

Imaginează-ți 10 căsuțe, câte una pentru fiecare cifră. De fiecare dată când apare cifra 7, crești cu 1 căsuța lui 7.

Frecvențele cifrelor 0–9

frecventa = [0] * 10

n = int(input())

for i in range(n):
    x = int(input())
    frecventa[x] = frecventa[x] + 1

for x in range(10):
    print(x, frecventa[x])

Lista are 10 poziții, cu indici 0–9. Toate pozițiile pornesc cu frecvența 0.

Frecvențele notelor 1–10

frecventa = [0] * 11

n = int(input())

for i in range(n):
    nota = int(input())
    frecventa[nota] = frecventa[nota] + 1

for nota in range(1, 11):
    print(nota, frecventa[nota])

ALGORITM FrecventeCifre
    frecventa[0..9] ← 0
    citește n
    pentru i ← 1,n execută
        citește x
        frecventa[x] ← frecventa[x] + 1
    sfârșit pentru

    pentru x ← 0,9 execută
        scrie x, frecventa[x]
    sfârșit pentru
SFÂRȘIT ALGORITM

ALGORITM MaximFrecventa
    maxim ← -1
    valoare ← 0
    pentru x ← 0,9 execută
        dacă frecventa[x] > maxim atunci
            maxim ← frecventa[x]
            valoare ← x
        sfârșit dacă
    sfârșit pentru
    scrie valoare, maxim
SFÂRȘIT ALGORITM

În cazul unei egalități, regula trebuie precizată. Dacă domeniul este parcurs crescător și folosim >, rămâne prima valoare maximă, adică cea mai mică.

Problemă

Se citesc n cifre. Determinați frecvența fiecărei cifre și cifra cu frecvență maximă; la egalitate alegeți cifra cea mai mică.

Analiză

Construim frecvențele într-o singură parcurgere, apoi parcurgem domeniul 0–9. Folosim >, nu >=, astfel prima valoare maximă rămâne răspunsul. Deoarece domeniul este parcurs crescător, ea este cea mai mică.

Algoritm

frecventa[0..9] ← 0
citește n

pentru i ← 1,n execută
    citește x
    frecventa[x] ← frecventa[x] + 1
sfârșit pentru

maxim ← -1
cifra ← 0
pentru x ← 0,9 execută
    dacă frecventa[x] > maxim atunci
        maxim ← frecventa[x]
        cifra ← x
    sfârșit dacă
sfârșit pentru

scrie frecvențele
scrie cifra, maxim

Python

n = int(input())
frecventa = [0] * 10

for i in range(n):
    x = int(input())
    frecventa[x] = frecventa[x] + 1

maxim = -1
cifra = 0

for x in range(10):
    if frecventa[x] > maxim:
        maxim = frecventa[x]
        cifra = x

for x in range(10):
    print(x, frecventa[x])

print("Cifra cu frecvența maximă:", cifra)
print("Frecvență:", maxim)

Urmărirea variabilelor

Pentru 2,5,2,7,5,2,7: f[2]=3, f[5]=2, f[7]=2. Maximul este 3 la cifra 2.

Testare

Caz normal: mai multe cifre, cu frecvențe diferite.

Caz-limită: n=1.

Caz particular: toate cifrele sunt egale; apoi două valori au aceeași frecvență maximă.

Justificarea soluției

După citirea tuturor cifrelor, fiecare poziție frecventa[x] este exact numărul aparițiilor lui x. Parcurgerea crescătoare a domeniului și folosirea lui > selectează cea mai mică valoare în caz de egalitate.

1. Construiți frecvențele pentru 1,2,1,4,2,1.
2. Construiți frecvențele pentru note 1–10.
3. Determinați câte valori au frecvența 0 în 0–9.
4. Determinați cifra cu frecvență maximă.
5. Determinați numărul de valori distincte.

6. Determinați toate valorile cu frecvență maximă.
7. Determinați frecvența minimă strict pozitivă.
8. Explicați de ce metoda este potrivită domeniilor mici.
9. Calculați media notelor folosind frecvențele.
10. Comparați lista de frecvențe cu numărarea prin căutări repetate.