Ce vei învăța astăzi?
Aceasta este lecția de recapitulare și evaluare. Vei integra tot ce ai învățat despre generarea secvențelor și sortare, apoi vei rezolva un test final.
Tabel rezumativ al metodelor de sortare
Recapitulăm cele trei metode de sortare învățate și le comparăm printr-un singur tabel:
| Metoda | Ideea de bază | Complexitate | Când o folosim |
|---|---|---|---|
| Selecția minimului | Căutăm minimul și îl punem la locul lui | O(n²) | Liste de orice valori, puține interschimbări |
| Metoda bulelor | Comparăm vecini și îi schimbăm | O(n²) | Liste mici, când vrem să urmărim pașii |
| Lista de frecvențe | Numărăm aparițiile și le afișăm în ordine | O(n + max) | Valori întregi într-un interval mic |
Reține: pentru valori într-un interval mic, lista de frecvențe este de departe cea mai rapidă.
Generarea secvențelor recurente
Am învățat să generăm termenii unui șir recurent (un șir în care fiecare termen se calculează din termenii anteriori) folosind valorile anterioare. Cel mai cunoscut exemplu este șirul lui Fibonacci, dar recurențele pot avea orice regulă.
Recapitulare: termenii Fibonacci mai mici decât x
x = int(input())
a = 1
b = 1
while a <= x:
print(a, end=" ")
a, b = b, a + b
Observă: aici nu știm dinainte câți termeni vom afișa, așa că folosim o buclă while cu o condiție clară.
Problemă combinată (care cere atât generarea datelor, cât și sortarea lor)
Multe probleme combină generarea datelor cu sortarea. Iată un exemplu complet: citim n numere și le sortăm crescător.
Exemplu: citire și sortare
n = int(input())
v = list(map(int, input().split()))
for i in range(n - 1):
p = i
for j in range(i + 1, n):
if v[j] < v[p]:
p = j
v[i], v[p] = v[p], v[i]
for x in v:
print(x, end=" ")
Observă: același program poate fi scris și cu metoda bulelor sau cu lista de frecvențe, dacă valorile sunt într-un interval mic.
Recapitulare rapidă
Înainte de test, verifică-te: știi să generezi pătrate perfecte? Știi regula lui Fibonacci? Știi să scrii selecția minimului, metoda bulelor și lista de frecvențe? Știi când folosești fiecare metodă?
Pătrate perfecte, pare, Fibonacci, șiruri recurente
Selecția minimului, bulele, lista de frecvențe
O(n²) vs O(n), când folosim fiecare metodă
Exercițiu de completare
Completează recapitularea modulului:
Pentru a sorta prin ______ minimului căutăm minimul la fiecare pas. Cu lista de ______ sortăm rapid valori dintr-un interval mic. Prin metoda ______ comparăm elemente adiacente. Un șir recurent foarte cunoscut este șirul lui ______.
Bancă de cuvinte:
Test de înțelegere
Test rapid - recapitulare:
1. Care metodă compară elemente adiacente?
2. Șirul lui Fibonacci este definit:
3. Pentru valori într-un interval mic, cea mai rapidă sortare este:
Test suplimentar - verifică ce ai reținut
Test rapid suplimentar - recapitulare:
1. Pentru a genera termenii Fibonacci mai mici decât x folosim:
2. Șirul recurent a(n) = a(n-1) + 2 cu a(0) = 0 are termenul general:
3. Înainte de a considera un program corect, cel mai bine îl verificăm:
Aprofundare
În problemele combinate, recunoașterea tipului de problemă este jumătate din rezolvare: dacă enunțul cere „să se afișeze termenii șirului", generăm; dacă cere „să se ordoneze", sortăm; dacă cere ambele, le combinăm în ordinea logică: întâi generăm sau citim datele, apoi le sortăm, apoi afișăm.
- Verificarea prin inversare: după sortare, lista trebuie să fie crescătoare; poți verifica parcurgând-o și confirmând că fiecare element este mai mic sau egal cu următorul.
- Alegerea metodei de sortare: dacă valorile generate sunt într-un interval mic (de exemplu note), lista de frecvențe este cea mai rapidă; dacă sunt oricât de mari, folosim selecția minimului sau bulele.
- Generarea direct în ordine: uneori putem evita sortarea completă: de exemplu, pătratele perfecte cresc odată cu indicele, deci șirul generat este deja sortat.
- Bucla while pentru număr necunoscut de termeni: când generăm „toți termenii mai mici decât x", nu știm dinainte câți sunt; folosim while, nu for.
- Corectitudinea datelor: verifică întotdeauna că lista citită are exact n elemente și că nu au apărut valori neașteptate (de exemplu note peste 10).
PbInfo - Termenii Fibonacci mai mici decât x
Enunț:
Cerință: Se citește numărul natural x. Să se afișeze toți termenii șirului lui Fibonacci mai mici sau egali cu x.
Date de intrare:
Programul citește de la tastatură numărul natural x.
Date de ieșire:
Programul va afișa termenii Fibonacci mai mici sau egali cu x, separați 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:
20
Ieșire:
1 1 2 3 5 8 13
Cum gândim soluția:
- Citim x și pornim cu a = 1, b = 1
- Folosim o buclă while cât timp a <= x
- Afișăm a, apoi actualizăm: a, b = b, a + b
Scrie soluția în Python:
Soluție corectă:
x = int(input())
a = 1
b = 1
while a <= x:
print(a, end=" ")
a, b = b, a + b
Ce învățăm: folosim o buclă while, pentru că numărul de termeni nu este cunoscut dinainte - el depinde de condiția a <= x.
PbInfo - A doua valoare minimă
Enunț:
Cerință: Se citesc n numere întregi distincte. Să se afișeze a doua cea mai mică valoare.
Date de intrare:
Programul citește de la tastatură numărul n, apoi n numere întregi distincte.
Date de ieșire:
Programul va afișa a doua valoare minimă din vector.
Restricții și precizări:
n este un număr natural, cu 1 <= n <= 1000, iar elementele sunt numere întregi.
Exemplu:
Intrare:
5 7 3 9 1 5
Ieșire:
3
Cum gândim soluția:
- Citim n și vectorul v
- Sortăm vectorul (de exemplu cu sort())
- A doua valoare minimă este v[1]
Scrie soluția în Python:
Soluție corectă:
n = int(input()) v = list(map(int, input().split())) v.sort() print(v[1])
Ce învățăm: sortarea ne așază valorile în ordine, iar a doua cea mai mică se află pe indexul 1.
Exercițiul Practic: Recapitulare și test
Sarcini de lucru
Rezolvă sarcinile de recapitulare, apoi dă testul final cu încredere.
Sarcina 1: Selecția minimului cu numărul de comparații
Cerință: Scrie un program complet care citește n numere, le sortează prin selecția minimului și afișează și numărul de comparații efectuate.
Soluție:
n = int(input())
v = list(map(int, input().split()))
nr = 0
for i in range(n - 1):
p = i
for j in range(i + 1, n):
nr = nr + 1
if v[j] < v[p]:
p = j
v[i], v[p] = v[p], v[i]
print("Numar comparatii:", nr)
for x in v:
print(x, end=" ")
Verifică: contorul nr crește la fiecare comparație din bucla interioară, deci ar trebui să fie aproape n(n-1)/2.
Sarcina 2 (TEST): Minim, maxim și sortare prin bule
Cerință: TEST: Scrie un program care citește n numere și afișează minimul, maximul și lista sortată prin metoda bulelor.
Soluție:
n = int(input())
v = list(map(int, input().split()))
print("Minimul:", min(v))
print("Maximul:", max(v))
for i in range(n - 1):
for j in range(n - 1 - i):
if v[j] > v[j + 1]:
v[j], v[j + 1] = v[j + 1], v[j]
for x in v:
print(x, end=" ")
Test: pentru 5 1 3 5 7 9, minimul este 1, maximul este 9, iar lista sortată este 1 3 5 7 9.