Ce vei învăța astăzi?
După această lecție vei învăța să sortezi o listă cu ajutorul unei liste de frecvențe (o listă în care fiecare poziție i arată de câte ori apare valoarea i), o metodă rapidă pentru valori dintr-un interval mic.
Ideea listei de frecvențe
Definiție: O listă de frecvențe reține, pe fiecare poziție i, de câte ori apare valoarea i în șir. Apoi parcurgem pozițiile în ordine și afișăm fiecare valoare de atâtea ori cât arată frecvența ei.
Analogia cu tabelul de note
Este ca un tabel cu notele clasei: o căsuță pentru fiecare notă posibilă (1, 2, ..., 10), în care punem câte o însemnare pentru fiecare elev.
La final, citim căsuțele în ordine și scriem notele: cinci note de 5, trei note de 7, și așa mai departe.
Când este utilă lista de frecvențe
Este utilă când valorile sunt numere întregi dintr-un interval mic (între o valoare minimă și una maximă apropiate), de exemplu note de la 1 la 10 sau punctaje de la 0 la 100.
Dacă valorile sunt foarte mari și diferite, lista de frecvențe ar fi uriașă, așa că folosim alte metode.
| Situație | Metoda recomandată | Motivul |
|---|---|---|
| Note de la 1 la 10 | Lista de frecvențe | Interval mic, rapid și simplu |
| Scoruri de la 0 la 100 | Lista de frecvențe | Interval rezonabil (101 valori) |
| Valori mari, oricât de diferite | Selecția minimului sau bulele | Nu depind de mărimea valorilor |
Implementarea
Pașii sunt: (1) construim lista fr, cu 0 pe fiecare poziție (această pregătire a listei se numește inițializare); (2) pentru fiecare valoare x creștem fr[x] cu 1; (3) parcurgem pozițiile și afișăm fiecare valoare de câte ori apare.
Exemplu: sortarea notelor (1-10)
note = [7, 5, 9, 5, 8, 7, 10, 5]
fr = [0] * 11
for x in note:
fr[x] = fr[x] + 1
for i in range(1, 11):
for _ in range(fr[i]):
print(i, end=" ")
Observă: nota 5 apare de 3 ori, deci 5 este afișat de 3 ori. Rezultatul: 5 5 5 7 7 8 9 10.
Avantajele metodei
Lista de frecvențe este foarte rapidă pentru intervale mici, nu face nicio interschimbare și păstrează valorile identice împreună.
O singură parcurgere pentru frecvențe, apoi o afișare simplă
Nu mutăm elemente, doar numărăm aparițiile
Exercițiu de completare
Completează descrierea sortării cu lista de frecvențe:
Construim o listă de ______ în care fiecare poziție arată de câte ori apare valoarea. Lista se inițializează cu ______. Pentru fiecare valoare x scriem fr[x] ______ 1. La final parcurgem pozițiile cu o buclă ______.
Bancă de cuvinte:
Test de înțelegere
Test rapid - lista de frecvențe:
1. Sortarea cu lista de frecvențe este potrivită când:
2. Lista de frecvențe pentru note de la 1 la 10 are:
3. După sortare, valoarea 5 apare de:
Test suplimentar - verifică ce ai reținut
Test rapid suplimentar - lista de frecvențe:
1. Lista de frecvențe este eficientă când valorile sunt:
2. frecv[x] reține:
3. Complexitatea sortării cu lista de frecvențe este:
[0] * 11), altfel accesul fr[10] iese în afara listei.Aprofundare
Lista de frecvențe nu sortează doar: ea numără aparițiile fiecărei valori, ceea ce o face utilă și pentru alte întrebări, de exemplu „care este valoarea care apare cel mai des?" (moda unui șir de note).
- Valori care nu încep de la 0 sau 1: dacă valorile sunt în intervalul [min, max], folosim un decalaj: frecvența valorii x se ține pe poziția
x - min, iar lista aremax - min + 1elemente. - Valori negative: cu decalajul de mai sus putem sorta și valori negative, pentru că poziția se calculează relativ la minim.
- Memorie: lista de frecvențe consumă memorie proporțională cu intervalul de valori, nu cu numărul de elemente; pentru un interval de un milion de valori, lista devine mare și metoda devine nepotrivită.
- Fără interschimbări: metoda nu mută elementele, ci doar le numără; valorile identice rămân întotdeauna grupate.
- Verificarea corectitudinii: suma tuturor frecvențelor trebuie să fie egală cu numărul total de valori citite; aceasta este o verificare rapidă pe hârtie.
- Complexitate: construirea frecvențelor parcurge lista o singură dată (n operații), iar afișarea parcurge intervalul (max operații); în total O(n + max).
PbInfo - Sortare cu listă de frecvențe
Enunț:
Cerință: Se citesc n note, numere întregi între 1 și 10. Să se afișeze notele sortate crescător, folosind lista de frecvențe.
Date de intrare:
Programul citește de la tastatură numărul n, apoi cele n note.
Date de ieșire:
Programul va afișa notele sortate crescător, separate prin spații.
Restricții și precizări:
n este un număr natural, cu 1 <= n <= 1000, iar elementele sunt numere întregi.
Exemplu:
Intrare:
8 7 5 9 5 8 7 10 5
Ieșire:
5 5 5 7 7 8 9 10
Cum gândim soluția:
- Citim n și vectorul v
- Construim fr = [0] * 11 și incrementăm fr[x] pentru fiecare notă x
- Parcurgem i de la 1 la 10 și afișăm i de fr[i] ori
Scrie soluția în Python:
Soluție corectă:
n = int(input())
v = list(map(int, input().split()))
fr = [0] * 11
for x in v:
fr[x] = fr[x] + 1
for i in range(1, 11):
for _ in range(fr[i]):
print(i, end=" ")
Ce învățăm: construim frecvențele întâi, apoi folosim o buclă dublă pentru a afișa fiecare valoare de câte ori apare.
PbInfo - Frecvența maximă
Enunț:
Cerință: Se citesc n note, numere întregi între 1 și 10. Să se afișeze nota care apare de cele mai multe ori și de câte ori apare.
Date de intrare:
Programul citește de la tastatură numărul n, apoi cele n note.
Date de ieșire:
Programul va afișa valoarea 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 sunt numere întregi.
Exemplu:
Intrare:
8 7 5 9 5 8 7 5 5
Ieșire:
5 4
Cum gândim soluția:
- Construim lista de frecvențe fr
- Calculăm frecvența maximă cu
max(fr) - Găsim valoarea cu
fr.index(m)
Scrie soluția în Python:
Soluție corectă:
n = int(input())
v = list(map(int, input().split()))
fr = [0] * 11
for x in v:
fr[x] = fr[x] + 1
m = max(fr)
print(fr.index(m), m)
Ce învățăm: max() ne dă frecvența cea mai mare, iar index() ne spune care valoare are acea frecvență.
Exercițiul Practic: Sortarea cu lista de frecvențe
Sarcini de lucru
Aplică sortarea cu lista de frecvențe în programe complete și explorează detalii despre note.
Sarcina 1: 10 note descrescător
Cerință: Scrie un program care citește 10 note și le afișează sortate descrescător, folosind lista de frecvențe.
Soluție:
note = []
for i in range(10):
note.append(int(input()))
fr = [0] * 11
for x in note:
fr[x] = fr[x] + 1
for i in range(10, 0, -1):
for _ in range(fr[i]):
print(i, end=" ")
Verifică: pentru notele 7 5 9 5 8 7 10 5 8 6 se afișează 10 9 8 8 7 7 6 5 5 5. Parcurgem pozițiile de la 10 în jos.
Sarcina 2: Câte note de fiecare fel
Cerință: Scrie un program care citește n note și afișează, pentru fiecare notă întâlnită, de câte ori apare.
Soluție:
n = int(input())
v = list(map(int, input().split()))
fr = [0] * 11
for x in v:
fr[x] = fr[x] + 1
for i in range(1, 11):
if fr[i] > 0:
print(i, "apare de", fr[i], "ori")
Verifică: cu notele 7 5 9 5 8 se afișează câte o linie pentru fiecare notă întâlnită, cu frecvența ei.