Ce vei învăța astăzi?
După această lecție vei construi o listă de frecvențe, vei interpreta rezultatele ei și vei rezolva probleme de voturi, note și ordonare.
Ce este o listă de frecvențe?
Definiție: O listă de frecvențe este o listă în care pe poziția i se află numărul de apariții ale valorii i într-o anumită colecție de valori.
Este ca la numărarea voturilor: pentru fiecare candidat ținem un număr de voturi, iar la final citim cine a câștigat.
Unde întâlnim frecvențele în viața reală?
- Voturi: de câte ori a fost ales fiecare candidat
- Notele de la 1 la 10: câți elevi au luat nota 8, nota 9 etc.
- Răspunsuri cu stele (1-5): câte recenzii au primit 5 stele
- Tabelul de frecvențe de la matematică: aceeași idee, doar că în program o implementăm cu o listă
Cum construim o listă de frecvențe?
Construim o listă de frecvențe în doi pași:
- Inițializare: creăm lista cu toate pozițiile egale cu
0, pentru fiecare valoare posibilă - Incrementare: la fiecare apariție a valorii x, mărim cu 1:
fr[x] += 1
Exemplu: frecvența notelor de la 1 la 10
note = [7, 9, 7, 10, 8, 7, 9]
fr = [0] * 11
for x in note:
fr[x] += 1
for nota in range(1, 11):
print(nota, ":", fr[nota])
Observă: fr[7] = 3, pentru că nota 7 apare de 3 ori. Lista are 11 poziții (0-10), iar fr[0] nu se folosește.
Cum interpretăm o listă de frecvențe?
Odată construită, lista de frecvențe ne răspunde imediat la întrebări:
| Întrebare | Răspuns în cod |
|---|---|
| De câte ori apare valoarea x? | fr[x] |
| Care valoare apare cel mai des? | Poziția maximului din fr |
| Câte valori distincte există? | Numărăm pozițiile cu fr[i] > 0 |
| Cum ordonăm valorile? | Afișăm poziția i de fr[i] ori, pentru i crescător |
Ordonarea cu listă de frecvențe
Dacă valorile sunt dintr-un interval mic (de exemplu note 1-10), le putem afișa sortate foarte simplu: pentru fiecare valoare i, o afișăm de fr[i] ori, în ordine crescătoare.
Exercițiu de completare
Completează enunțul cu cuvintele și simbolurile potrivite:
O listă de ______ numără de câte ori apare fiecare valoare. O inițializăm cu valoarea ______ pe fiecare poziție. La fiecare apariție a valorii x, executăm fr[x] ______ ______, adică mărim numărul de apariții.
Bancă de cuvinte:
Test de înțelegere
Test rapid - lista de frecvențe:
1. O listă de frecvențe numără:
2. Cu ce valoare inițializăm lista de frecvențe?
3. Pentru note întregi de la 1 la 10, lista de frecvențe are:
fr[x] += 1, nu fr[x] = 1, altfel suprascrii numărul existent la fiecare apariție. Totodată, dimensiunea listei trebuie să acopere toate valorile: pentru note de la 1 la 10 folosește [0] * 11.Aprofundare
Dimensiunea listei de frecvențe. Lista de frecvențe trebuie să acopere toate valorile posibile. Pentru note de la 1 la 10 folosim [0] * 11 (indicii 0-10), pentru valori de la 0 la 100 folosim [0] * 101. Poziția 0 rămâne adesea nefolosită, dar o păstrăm pentru ca valoarea x să corespundă exact indexului x.
Valori în afara intervalului. Dacă citim o valoare mai mare decât ultimul index (de exemplu nota 12 pe o listă de 11 poziții), obținem IndexError. Înainte de a construi lista de frecvențe, trebuie să cunoaștem intervalul valorilor, fie din enunț („note de la 1 la 10"), fie căutând maximul valorilor citite.
Frecvența caracterelor. Lista de frecvențe se aplică și la caractere: fiecare literă are un cod numeric (codul ASCII), deci putem număra aparițiile literelor dintr-un text folosind fr[ord(caracter)]. Aceasta este tehnica de bază în problemele de analiză a textelor.
Valoarea cu frecvență maximă. Pentru a afla valoarea care apare cel mai des, căutăm maximul din lista de frecvențe: parcurgem pozițiile și reținem poziția cu cea mai mare valoare fr[i]. La egalitate, enunțul precizează dacă se afișează prima sau ultima valoare întâlnită.
Ordonarea cu frecvențe este liniară. Spre deosebire de sortare, afișarea valorilor în ordine crescătoare cu ajutorul frecvențelor (afișăm i de fr[i] ori) durează proporțional cu intervalul de valori, fiind foarte rapidă pentru intervale mici.
Quiz de consolidare
Quiz de consolidare - lista de frecvențe:
1. Pentru valori întregi de la 0 la 100, lista de frecvențe se inițializează cu:
2. La fiecare apariție a valorii x incrementăm frecvența astfel:
3. După construirea listei de frecvențe, valoarea fr[7] reprezintă:
PbInfo - Frecvența numerelor
Enunț:
Cerință: Se citește numărul natural n, apoi n numere între 1 și 100. Să se afișeze, pentru fiecare valoare care apare cel puțin o dată, valoarea și de câte ori apare.
Date de intrare:
Programul citește de la tastatură numărul n, apoi pe linia următoare cele n numere, separate prin spații.
Date de ieșire:
Programul va afișa, în ordine crescătoare, valoarea și frecvența ei, pentru fiecare valoare care apare.
Restricții și precizări:
n este un număr natural, cu 1 <= n <= 1000, iar elementele listei sunt numere întregi.
Exemplu:
Intrare:
7 5 3 5 5 8 3 3
Ieșire:
3 3 5 3 8 1
Cum gândim soluția:
- Citim n și numerele în lista v
- Creăm lista de frecvențe cu 101 poziții:
fr = [0] * 101 - Pentru fiecare x din v, executăm
fr[x] += 1 - Parcurgem fr de la 1 la 100 și afișăm valorile care apar
Scrie soluția în Python:
Soluție corectă:
n = int(input())
v = list(map(int, input().split()))
fr = [0] * 101
for x in v:
fr[x] += 1
for i in range(1, 101):
if fr[i] > 0:
print(i, fr[i])
Ce învățăm: lista de frecvențe numără aparițiile fiecărei valori, iar apoi afișăm doar valorile care apar cel puțin o dată.
PbInfo - Nota maximă și frecvența ei
Enunț:
Cerință: Se citește o listă de note întregi de la 1 la 10. Să se afișeze nota care apare cel mai des (frecvența maximă) și de câte ori apare.
Date de intrare:
Programul citește de la tastatură notele, separate prin spații.
Date de ieșire:
Programul va afișa nota cu frecvența maximă și frecvența ei.
Restricții și precizări:
n este un număr natural, cu 1 <= n <= 1000, iar elementele listei sunt numere întregi.
Exemplu:
Intrare:
7 9 7 10 8 7 9
Ieșire:
7 3
Cum gândim soluția:
- Creăm lista de frecvențe cu 11 poziții:
fr = [0] * 11 - Pentru fiecare notă x, executăm
fr[x] += 1 - Găsim maximul din fr și poziția lui cu
max()șiindex()
Scrie soluția în Python:
Soluție corectă:
v = list(map(int, input().split()))
fr = [0] * 11
for x in v:
fr[x] += 1
m = max(fr)
print(fr.index(m), m)
Ce învățăm: max(fr) ne dă cea mai mare frecvență, iar fr.index(m) ne spune pe ce poziție se află, adică nota căutată.
Exercițiul Practic: Frecvențe în aplicații
Sarcini de lucru
Completează următoarele sarcini pentru a folosi lista de frecvențe în probleme practice
Sarcina 1: Numărarea voturilor
Cerință: Scrie un program care citește voturile a 10 elevi (fiecare vot este un număr de la 1 la 5, reprezentând candidatul ales) și afișează candidatul câștigător, adică cel cu cele mai multe voturi.
Soluție pentru Sarcina 1:
voturi = list(map(int, input().split()))
fr = [0] * 6
for x in voturi:
fr[x] += 1
m = max(fr)
print("Castigator:", fr.index(m), "cu", m, "voturi")
Verifică: lista de frecvențe are 6 poziții (0-5), iar câștigătorul este poziția cu frecvența maximă.
Sarcina 2: Sortarea notelor cu frecvențe
Cerință: Scrie un program care citește note întregi de la 1 la 10 și le afișează în ordine crescătoare, folosind lista de frecvențe (fără sort()): pentru fiecare notă i, o afișăm de fr[i] ori.
Soluție pentru Sarcina 2:
note = list(map(int, input().split()))
fr = [0] * 11
for x in note:
fr[x] += 1
for nota in range(1, 11):
for i in range(fr[nota]):
print(nota, end=" ")
Verifică: afișăm nota de fr[nota] ori, în ordine crescătoare. Rezultatul este lista sortată!