clasa a IX-a · Python · Organizarea conceptuală a datelor · lecția 14
Modelul liniar: listă, stivă, coadă, listă de frecvențe
150 minmate-info · Python
Înainte de lecția asta: IX.2 De la pseudocod (sau C++) la Python, IX.9 Subprograme (2): variabile locale și globale, funcții predefinite
Ce vei ști după lecție
- Recunoști o listă (model liniar) și explici ce înseamnă primul, ultimul, predecesorul și succesorul unui element.
- Deosebești accesul direct de accesul secvențial și stiva (LIFO) de coadă (FIFO), cu exemple din viața reală.
- Construiești și interpretezi o listă de frecvențe.
- Alegi între parcurgerea fără memorare și parcurgerea cu memorare, după ce cere problema.
Lecția are și o fișă de lucru, de rezolvat după ce o citești. Mergi la fișă ↓
Clasa a IX-aLecția 14 din 21 · mai sunt 7Urmează: IX.15 · Clasa list din PythonVezi toate lecțiile
Fișiere PDF și de lucru
- Lecția în PDF
versiunea de printat
- Fișa de lucru: Modelul liniar: listă, stivă, coadă, listă de frecvențe
7 pagini · 150 min
1. Lista: date așezate „la rând”
Gândește-te la mașinile oprite la semafor pe o stradă cu sens unic. Există o primă mașină și o ultimă mașină, iar fiecare dintre celelalte are exact o mașină în fața ei (predecesor) și exact una în spatele ei (succesor). Asta este o listă: un șir de elemente așezate liniar, în care contează ordinea.
În Python, modelul se scrie direct cu list. Pozițiile (indicii) încep de la 0.
masini = ["Dacia", "Ford", "BMW", "Opel", "Skoda"]
print(masini[0], masini[-1], len(masini)) # Dacia Skoda 5
i = 2
print("înainte de", masini[i], "e", masini[i - 1], "; după e", masini[i + 1])
# înainte de BMW e Ford ; după e Opel| Noțiune | În listă | În Python, pentru lista a cu n elemente |
|---|---|---|
| primul element | nu are predecesor | a[0] |
| ultimul element | nu are succesor | a[n - 1] sau a[-1] |
predecesorul lui a[i] |
există pentru i ≥ 1 |
a[i - 1] |
succesorul lui a[i] |
există pentru i ≤ n − 2 |
a[i + 1] |
| lista vidă | niciun element | [], len(a) == 0 |
Citirea unei liste de pe un rând o știi deja: a = list(map(int, input().split())).
2. Acces direct și acces secvențial
Diferența dintre modelele liniare este cum ajungi la un element.
- Acces direct: ajungi imediat la elementul de pe o poziție dată. Profesorul îl strigă pe al cincilea elev din catalog fără să-i citească pe primii patru:
catalog[4]. - Acces secvențial: ca să ajungi la un element, treci pe rând prin cele dinaintea lui. Așa cauți o melodie pe o casetă sau un nume pe o listă nesortată.
catalog = ["Ana", "Bogdan", "Carla", "Dan", "Elena", "Filip"]
print(catalog[4]) # Elena: acces direct, un singur pasLista Python permite acces direct, dar multe prelucrări sunt totuși parcurgeri secvențiale: verifici fiecare element, de la primul la ultimul. Exemplu: câte perechi de zile consecutive au avut aceeași temperatură?
temperaturi = [3, 5, 5, 2, 7, 7, 7, 1]
c = 0
for i in range(len(temperaturi) - 1): # i merge până la penultimul
if temperaturi[i] == temperaturi[i + 1]:
c += 1
print(c) # 3: (5,5), (7,7), (7,7)Atenție — greșeli frecvente
La perechile consecutive, i merge până la n − 2, adică range(len(a) - 1). Cu range(len(a)), ultimul pas cere a[n], care nu există: IndexError. Testează mereu și o pereche aflată la capătul listei.
3. Stiva: ultimul venit, primul servit (LIFO)
O stivă de farfurii: pui farfuria nouă deasupra și tot de deasupra o iei. Elementul scos este mereu ultimul adăugat: LIFO (Last In, First Out). Ai acces doar la un capăt, numit vârf.
În Python, vârful stivei este sfârșitul listei: append(x) pune, pop() scoate, s[-1] doar se uită.
sarcini = []
sarcini.append("teme la mate")
sarcini.append("sună bunica")
sarcini.append("udă florile")
print(sarcini.pop()) # udă florile (ultima adăugată)
print(sarcini.pop()) # sună bunica
print(sarcini) # ['teme la mate']
print(sarcini[-1]) # teme la mate (vârful, fără să-l scoatem)Unde apare: butonul Anulează (undo) dintr-un editor, butonul Înapoi din browser, farfuriile, cărțile puse una peste alta.
4. Coada: primul venit, primul servit (FIFO)
La coada de la casa de bilete a cinematografului, oamenii intră la sfârșit și sunt serviți de la început. Primul sosit pleacă primul: FIFO (First In, First Out).
În Python: append(x) adaugă la sfârșit, pop(0) scoate de la început. Aceleași trei sarcini, puse într-o coadă, ies în altă ordine:
coada = []
coada.append("teme la mate")
coada.append("sună bunica")
coada.append("udă florile")
print(coada.pop(0)) # teme la mate (prima adăugată)
print(coada.pop(0)) # sună bunica
print(coada) # ['udă florile']| Stivă | Coadă | |
|---|---|---|
| regula | LIFO | FIFO |
| adaugi | la vârf: s.append(x) |
la sfârșit: q.append(x) |
| scoți | de la vârf: s.pop() |
de la început: q.pop(0) |
| exemple | undo, farfurii, „Înapoi” | apeluri la un call-center, imprimantă, rândul la ghișeu |
De știut
Stiva și coada nu sunt tipuri noi de date, ci reguli de acces puse peste o listă. Tu respecți regula: la o stivă nu iei elemente din mijloc. Pentru cozi foarte lungi, Python are collections.deque, mai rapid la scoaterea din față; pentru problemele noastre, pop(0) este suficient.
pop() pe o listă vidă dă eroare: IndexError: pop from empty list. Înainte să scoți, verifici if s: (o listă nevidă este „adevărată”).
5. Lista de frecvențe: numeri, nu memorezi
Un magazin cere clienților o notă de la 1 la 5 stele. Nu ne interesează cine a dat ce notă, ci de câte ori apare fiecare notă. Pentru asta folosim o listă de frecvențe: poziția este valoarea, iar elementul este numărul de apariții.
raspunsuri = [5, 4, 5, 3, 5, 1, 4, 5, 2, 4, 5, 3]
fr = [0] * 6 # pozițiile 0..5; poziția 0 nu se folosește
for r in raspunsuri:
fr[r] += 1 # încă o apariție a valorii r
print(fr) # [0, 1, 1, 2, 3, 5]
print(fr.index(max(fr))) # 5: nota cea mai frecventăCitire: fr[4] = 3 înseamnă „trei clienți au dat 4 stele”. Suma frecvențelor (sum(fr) = 12) este numărul de răspunsuri. Aceeași idee centralizează voturile la alegeri sau numără erorile zilnice de fiecare tip.
La BAC
Lista de frecvențe funcționează când valorile sunt numere întregi dintr-un interval mic și cunoscut (cifre, note 1–10, stele 1–5, coduri 1–8). Dimensiunea ei este valoarea maximă + 1. Pentru valori de până la un miliard nu are sens: ai avea nevoie de un miliard de contoare.
6. Parcurgere cu sau fără memorare
Întrebarea-cheie: am nevoie de valori după ce le-am citit?
Fără memorare. Verifici facturile lunare: pentru fiecare citești suma și dacă e plătită (1) sau nu (0), și numeri facturile restante. Fiecare factură se prelucrează imediat și apoi poate fi „uitată”.
n = int(input())
restante = total = 0
for _ in range(n):
suma, platit = map(int, input().split())
if platit == 0:
restante += 1
total += suma
print(restante, total) # pentru 4 / 120 0 / 85 1 / 230 0 / 60 1: 2 350Cu memorare. Vrei notele peste media clasei. Media o afli abia după ce ai văzut toate notele, deci trebuie să le păstrezi și să le parcurgi a doua oară.
note = [7, 9, 5, 10, 8, 6]
media = sum(note) / len(note)
peste = []
for x in note:
if x > media:
peste.append(x)
print(f"{media:.2f}", peste) # 7.50 [9, 10, 8]| Cerința | Memorare? | De ce |
|---|---|---|
| suma, numărul, maximul unor valori | nu | se actualizează la fiecare valoare |
| valorile peste medie | da | media se știe abia la final |
| zilele cu numărul minim de clienți | da | minimul se știe abia la final, apoi cauți zilele |
| valorile în ordine inversă | da | ultima citită se afișează prima |
| perechi consecutive cu o proprietate | nu (ajunge valoarea anterioară) | compari doar cu precedenta |
7. Cum alegi modelul
| Situația | Model | Argument |
|---|---|---|
| cereri la suportul tehnic | coadă | cine a sunat primul este servit primul (corect față de clienți) |
| „anulează ultima acțiune” | stivă | se anulează mereu cea mai recentă |
| catalogul clasei | listă cu acces direct | vrei imediat elevul de pe poziția k |
| câte voturi a primit fiecare candidat (1–8) | listă de frecvențe | interval mic de coduri, contează doar numărul |
| registru de intrări din care numeri vizitatorii de sâmbătă | parcurgere fără memorare | o singură trecere, un contor |
Testele tipice pentru toate: lista vidă, un singur element, elementul căutat la început și la sfârșit.
8. Verifică-te
- La semafor sunt 6 mașini. Câte dintre ele au și predecesor, și succesor?
- Ce conține
sla final?s = [],s.append(1),s.append(2),s.pop(),s.append(3). - Ce valoare întoarce al doilea
pop(0)și ce rămâne înq?q = [1],q.append(2),q.pop(0),q.append(3),q.append(4),q.pop(0). - Vrei frecvențele notelor de la 1 la 10. Ce lungime are lista
frși ce înseamnăfr[7] == 3? - Care cerință are nevoie de memorare: (a) cea mai mare temperatură dintr-o lună; (b) zilele în care temperatura a depășit media lunii?
- Butonul „Înapoi” din browser: stivă sau coadă? Dar ordinea în care imprimanta tipărește documentele trimise?
- Ce se întâmplă la
[].pop()și cum previi situația?
Fișa de lucru
Ai citit lecția? Printează fișa sau deschide-o pe ecran și rezolvă exercițiile în ordine.
Fișă de lucru · 7 pagini · 150 min
Modelul liniar: listă, stivă, coadă, listă de frecvențe
- Urmărești pas cu pas operațiile pe o stivă și pe o coadă și prezici ce rămâne în ele.
- Construiești și citești o listă de frecvențe.
- Alegi modelul potrivit (stivă, coadă, acces direct, frecvențe) și parcurgerea potrivită (cu sau fără memorare).
Te-ai blocat la un exercițiu?
Probleme de lucru
Începe cu acestea, în ordine. Problemele se deschid pe pbinfo.ro, unde trimiți soluția și primești punctajul.
Temă
Rezolvă-le singur și bifează ce ai terminat. Bifele rămân salvate în acest browser.
Te-ai blocat la lecția asta?
Scrie-mi ce nu iese și vedem împreună de unde se blochează.
Răspunsuri
- 4 (toate, în afară de prima și ultima).
[1, 3].- Întoarce
2; înqrămâne[3, 4]. - Lungime 11 (pozițiile 0–10, poziția 0 nefolosită); trei elevi au luat nota 7.
- (b): media se cunoaște abia după toate valorile. La (a) ajunge un maxim actualizat pe parcurs.
- „Înapoi”: stivă (revii la ultima pagină vizitată). Imprimanta: coadă.
IndexError: pop from empty list. Verifici înainte:if s: s.pop().