Ce vei învăța astăzi?
După această lecție vei avea imaginea completă a modulului: tabelul rezumativ al metodelor, criteriile de alegere și pașii de rezolvare a unei probleme complete.
Tabel rezumativ: generare și cele trei sortări
Toate tehnicile modulului, comparate într-un singur tabel. Reține ideea de bază, complexitatea și situația în care folosim fiecare metodă:
| Tehnica | Ideea de bază | Complexitate | Când o folosim |
|---|---|---|---|
| Generarea sistematică | Producem termenii unul câte unul, după o regulă | O(n) | Pătrate perfecte, pare, termeni ai expresiilor |
| Șiruri recurente | Fiecare termen se calculează din anteriori | O(n) | Fibonacci, dobândă, orice recurență |
| Selecția minimului | Căutăm minimul și îl punem la locul lui | O(n²) | Valori oricât de mari, puține interschimbări |
| Metoda bulelor | Comparăm vecini și îi schimbăm | O(n²) | Liste mici, urmărirea pașilor |
| Lista de frecvențe | Numărăm aparițiile și afișăm în ordine | O(n + max) | Valori întregi într-un interval mic (între o valoare minimă și una maximă apropiate) |
Reține: generarea produce datele, recurențele produc șiruri după o regulă pas cu pas, iar sortarea ordonează datele existente. Cele trei se combină liber într-o problemă.
Reguli de alegere a metodei de sortare
Înainte de a scrie codul, răspunde la trei întrebări: Ce tip de date am? (numere mici, numere mari, texte), Ce ordine se cere? (crescătoare, descrescătoare) și Ce restricții are problema? (limitele impuse datelor de intrare, de exemplu n ≤ 10000 - mare sau mic).
| Datele problemei | Metoda aleasă | Motivul |
|---|---|---|
| Valori întregi într-un interval mic (între o valoare minimă și una maximă apropiate) | Lista de frecvențe | Cea mai rapidă: O(n + max) |
| Valori mari sau texte, n mic (până la câteva mii) | Selecția minimului | Simplă, puține interschimbări |
| Valori mari, n foarte mare | Selecția minimului sau bulele, doar dacă restricțiile permit | O(n²) devine lent la n mare |
| Clasament (ordine descrescătoare) | Selecția cu maxim sau frecvențe invers | Se schimbă doar comparația / parcurgerea |
De ce ne folosim?
Este ca alegerea unui instrument: pentru a măsura o foaie folosești rigla, nu cântarul. Fiecare metodă are punctul ei forte; profesionistul îl cunoaște pe fiecare și îl folosește la momentul potrivit.
Pașii unei probleme complete
Definiție: Orice problemă din acest modul se rezolvă în patru etape: 1. citirea datelor, 2. generarea sau prelucrarea (sortare), 3. afișarea în formatul cerut, 4. verificarea pe exemple mici.
Exemplu complet: generăm termenii Fibonacci mai mici decât x, apoi îi afișăm descrescător - recurență + sortare într-o singură problemă.
Exemplu: Fibonacci mai mici decât x, descrescător
x = int(input())
termeni = []
a = 1
b = 1
while a <= x:
termeni.append(a)
a, b = b, a + b
for i in range(len(termeni) - 1):
p = i
for j in range(i + 1, len(termeni)):
if termeni[j] > termeni[p]:
p = j
termeni[i], termeni[p] = termeni[p], termeni[i]
for t in termeni:
print(t, end=" ")
Observă: pentru x = 50, termenii generați sunt 1 1 2 3 5 8 13 21 34, iar după sortarea descrescătoare: 34 21 13 8 5 3 2 1 1.
Exercițiu de completare
Completează tabelul rezumativ:
Selecția minimului și metoda bulelor au complexitatea O(______). Lista de frecvențe are complexitatea O(n + ______). Șirul lui Fibonacci este o ______. Valorile dintr-un interval mic se sortează cel mai repede cu ______.
Bancă de cuvinte:
Exercițiu de completare
Completează pașii unei probleme:
Prima etapă a unei probleme este ______ datelor. A doua este generarea sau ______. A treia este afișarea în ______ cerut. La final verificăm pe exemple ______.
Bancă de cuvinte:
Test de înțelegere
Test rapid - recapitulare generală:
1. Pentru note de la 1 la 10, cea mai rapidă sortare este:
2. Selecția minimului și metoda bulelor au complexitatea:
3. Șirul lui Fibonacci se generează:
Aprofundare
La problemele compuse, strategia învingătoare este recunoașterea tipului din primul paragraf al enunțului: cuvinte ca „se ordonează", „clasament", „crescător" indică sortare; „se generează", „termenii șirului", „după regula" indică generare; „mai mici decât x" indică o buclă while.
- Verificarea prin control invers: după sortare, lista trebuie să respecte ordinea cerută; parcurge-o și confirmă că v[i] <= v[i+1] (sau >= pentru descrescător).
- Bilanțul valorilor: după orice prelucrare, numărul de valori trebuie să rămână același - dacă lipsește un element, interschimbarea sau generarea este greșită.
- Alegerea eficientă: dacă problema combină generare și sortare, întreabă-te dacă regula de generare produce deja valori ordonate (pătrate perfecte, multipli) - atunci sortarea este redundantă.
- Restricțiile dictează metoda: un enunț cu n <= 100000 și valori între 1 și 1000 îți spune direct: frecvențe. Un enunț cu valori mari și n <= 100 îți permite O(n²).
- Testează cazurile limită: lista cu un singur element, lista deja sortată, lista invers sortată, valori egale - un program corect le tratează pe toate fără erori.
PbInfo - Recapitulare: Primele k punctaje
Enunț:
Cerință: Se citesc n punctaje și un număr k. Să se afișeze primele k punctaje din clasament, adică cele mai mari k valori, în ordine descrescătoare.
Date de intrare:
Programul citește de la tastatură numărul natural n, apoi n numere naturale, apoi numărul natural k.
Date de ieșire:
Programul va afișa pe o singură linie primele k punctaje din clasament, în ordine descrescătoare.
Restricții și precizări:
1 <= k <= n <= 100, iar punctajele sunt numere naturale mai mici sau egale cu 100.
Exemplu:
Intrare:
5 42 78 55 78 90 2
Ieșire:
90 78
Cum gândim soluția:
- Citim n, punctajele și k
- Sortăm descrescător prin selecția minimului cu maxim
- Afișăm doar primele k valori cu
end=" "
Scrie soluția în Python:
Soluție corectă:
n = int(input())
punctaje = list(map(int, input().split()))
k = int(input())
for i in range(n - 1):
p = i
for j in range(i + 1, n):
if punctaje[j] > punctaje[p]:
p = j
punctaje[i], punctaje[p] = punctaje[p], punctaje[i]
for i in range(k):
print(punctaje[i], end=" ")
Ce învățăm: sortarea descrescătoare pune primele k cele mai mari valori chiar la începutul listei - afișarea lor este imediată.
PbInfo - Recapitulare: Termeni Fibonacci sortați
Enunț:
Cerință: Se citește numărul natural x. Să se afișeze în ordine descrescătoare toți termenii șirului lui Fibonacci mai mici sau egali cu x, separați prin spații.
Date de intrare:
Programul citește de la tastatură numărul natural x.
Date de ieșire:
Programul va afișa pe o singură linie termenii Fibonacci mai mici sau egali cu x, în ordine descrescătoare.
Restricții și precizări:
1 <= x <= 1000000, iar termenii șirului sunt definiți prin F1 = F2 = 1.
Exemplu:
Intrare:
50
Ieșire:
34 21 13 8 5 3 2 1 1
Cum gândim soluția:
- Generăm termenii Fibonacci cu bucla while, cât timp termenul curent este mai mic sau egal cu x
- Îi păstrăm într-o listă
- Sortăm lista descrescător prin selecția minimului cu maxim
- Afișăm termenii pe o singură linie
Scrie soluția în Python:
Soluție corectă:
x = int(input())
termeni = []
a = 1
b = 1
while a <= x:
termeni.append(a)
a, b = b, a + b
for i in range(len(termeni) - 1):
p = i
for j in range(i + 1, len(termeni)):
if termeni[j] > termeni[p]:
p = j
termeni[i], termeni[p] = termeni[p], termeni[i]
for t in termeni:
print(t, end=" ")
Ce învățăm: această problemă îmbină recurența (generare cu while), sortarea descrescătoare și afișarea formatată - un rezumat perfect al modulului.
Exercițiul Practic: Recapitulare generală
Sarcini de lucru
Recapitulează toate metodele modulului prin două programe complete.
Sarcina 1: Notele clasei cu frecvențe
Cerință: Scrie un program care citește n note (1-10) și le afișează crescător folosind lista de frecvențe, apoi pe o a doua linie afișează și nota care apare cel mai des.
Soluție:
n = int(input())
note = list(map(int, input().split()))
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=" ")
print()
moda = 1
for i in range(2, 11):
if fr[i] > fr[moda]:
moda = i
print("Moda:", moda)
Verifică: pentru notele 7 5 9 5 8 7 10 5, lista sortată este 5 5 5 7 7 8 9 10, iar moda este 5 (apare de 3 ori).
Sarcina 2: Bule optimizate pe o listă citită
Cerință: Scrie un program care citește n și o listă de n valori, o sortează crescător cu metoda bulelor optimizată (se oprește devreme dacă nu mai sunt interschimbări) și afișează lista.
Soluție:
n = int(input())
v = list(map(int, input().split()))
for i in range(n - 1):
schimbat = False
for j in range(n - 1 - i):
if v[j] > v[j + 1]:
v[j], v[j + 1] = v[j + 1], v[j]
schimbat = True
if not schimbat:
break
for x in v:
print(x, end=" ")
Verifică: dacă lista este deja sortată, variabila schimbat rămâne False după prima parcurgere, iar programul se oprește imediat - eficiență maximă.