Definițiile cheie
Generarea sistematică a unei secvențe înseamnă să produci termenii unul câte unul, după o regulă clară, de obicei cu o buclă for. Regula poate fi o formulă (pătrate perfecte: i * i), o condiție (doar valorile pare) sau o recurență. Secvența generată este complet determinată de regulă, deci același program produce mereu aceeași ieșire.
Șir recurent este un șir în care fiecare termen se calculează din termenii anteriori printr-o relație de recurență, pornind de la una sau mai multe condiții inițiale. Exemple: a(n) = a(n-1) + 2 sau a(n) = 2 * a(n-1).
Șirul lui Fibonacci: F1 = 1, F2 = 1, iar Fn = F(n-1) + F(n-2) pentru n > 2. În Python, a, b = b, a + b actualizează simultan ultimele două valori, iar șirul începe 1, 1, 2, 3, 5, 8, ...
Sortarea prin selecția minimului: la fiecare pas căutăm minimul din partea nesortată și îl mutăm pe prima poziție a acelei părți; face întotdeauna aproximativ n(n-1)/2 comparații, adică O(n²), dar cel mult o interschimbare pe pas.
Sortarea cu lista de frecvențe: pe poziția i reținem de câte ori apare valoarea i, apoi parcurgem pozițiile în ordine și afișăm fiecare valoare de câte ori apare; face aproximativ n + max operații, adică O(n + max), și nu face nicio interschimbare. Este potrivită doar pentru valori întregi dintr-un interval mic.
Metoda bulelor: comparăm elemente adiacente și le interschimbăm dacă sunt în ordine greșită; după fiecare parcurgere, cel mai mare element rămas ajunge pe poziția finală. Face tot aproximativ n(n-1)/2 comparații, adică O(n²), dar mult mai multe interschimbări decât selecția.
Eficiența (notația O) descrie cât de repede crește numărul de operații odată cu n: O(n) înseamnă creștere liniară (lista de frecvențe, generarea), iar O(n²) înseamnă creștere pătratică (bulele, selecția minimului). Dublarea lui n înseamnă timp de 2 ori mai mare la O(n) și de 4 ori mai mare la O(n²).
Algoritmul 1: Generarea sistematică (pătrate perfecte)
n = int(input())
for i in range(1, n + 1):
print(i * i, end=" ")
Variantă cu listă: patrate = [i * i for i in range(1, n + 1)] construiește lista într-o singură expresie.
Algoritmul 2: Șirul lui Fibonacci (recurență)
n = int(input())
a = 1
b = 1
for i in range(1, n + 1):
print(a, end=" ")
a, b = b, a + b
Variantă while: pentru „termeni mai mici decât x" folosim while a <= x, pentru că nu știm dinainte câți termeni vom afișa.
x = int(input())
a = 1
b = 1
while a <= x:
print(a, end=" ")
a, b = b, a + b
Algoritmul 3: Sortarea prin selecția minimului
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=" ")
Clasament: pentru ordine descrescătoare, schimbăm comparația în v[j] > v[p] - căutăm maximul.
Algoritmul 4: Sortarea cu lista de frecvențe
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=" ")
Clasament: parcurgem pozițiile în sens invers (range(10, 0, -1)) pentru ordine descrescătoare.
Algoritmul 5: Metoda bulelor
n = int(input())
v = list(map(int, input().split()))
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=" ")
Optimizare: cu o variabilă schimbat verificată la fiecare parcurgere, algoritmul se oprește devreme pe liste deja sortate.
Exemplu complet: generare și sortare împreună
Multe probleme cer întâi să generezi valori după o regulă, apoi să le sortezi și să afișezi rezultatul. Ordinea pașilor este esențială: nu poți sorta valori pe care nu le-ai generat încă.
Exemplu: resturi de pătrate perfecte, generate apoi sortate
n = int(input())
valori = []
for i in range(1, n + 1):
valori.append((i * i) % 100)
for i in range(n - 1):
p = i
for j in range(i + 1, n):
if valori[j] < valori[p]:
p = j
valori[i], valori[p] = valori[p], valori[i]
for x in valori:
print(x, end=" ")
Observă: pentru n = 5 valorile generate sunt 1, 4, 9, 16, 25, deja sortate; pentru n = 20 apar resturi care se repetă, iar sortarea le ordonează corect. Uneori regula de generare produce deja valori ordonate (pătrate perfecte, multipli) - atunci sortarea este de prisos.
Tabel recapitulativ al metodelor
| Metoda | Ideea de bază | Interschimbări | Complexitate | Când o folosim |
|---|---|---|---|---|
| Generarea sistematică | Termenii produși după o regulă | - | O(n) | Pătrate perfecte, pare, termeni ai expresiilor |
| Șiruri recurente | Termenul din termenii anteriori | - | O(n) | Fibonacci, dobânda bancară |
| Selecția minimului | Minimul pus pe poziția corectă | Cel mult una pe pas | O(n²) | Valori oricât de mari, liste de orice tip |
| Metoda bulelor | Vecini comparați și schimbați | Multe | O(n²) | Liste mici, urmărirea evoluției pas cu pas |
| Lista de frecvențe | Aparițiile numărate și afișate în ordine | Niciuna | O(n + max) | Valori întregi într-un interval mic |
| n (elemente) | Comparații ≈ n(n-1)/2 | Observație |
|---|---|---|
| 10 | 45 | Instant |
| 100 | 4950 | Rapid |
| 1000 | 499500 | Acceptabil |
| 100000 | Aproape 5 miliarde | Prea lent pentru O(n²) |
Comparație directă: selecție vs bule vs frecvențe
| Criteriu | Selecția minimului | Metoda bulelor | Lista de frecvențe |
|---|---|---|---|
| Ideea de bază | Minimul pus pe poziția corectă | Vecini comparați și schimbați | Aparițiile numărate și afișate în ordine |
| Număr de comparații | n(n-1)/2, mereu același | n(n-1)/2, mereu (fără optimizare) | Aproape deloc: doar n + max operații |
| Număr de interschimbări | Cel mult una pe pas (max. n-1) | Multe, ori de câte ori vecinii sunt în dezordine | Niciuna |
| Memorie suplimentară | Nicio listă suplimentară | Nicio listă suplimentară | O listă cu max + 1 elemente |
| Complexitate | O(n²) | O(n²) | O(n + max) |
| Când o folosim | Valori oricât de mari, puține interschimbări | Liste mici, urmărirea pașilor pas cu pas | Valori întregi într-un interval mic |
Concluzie: selecția și bulele au aceeași complexitate, dar bulele face mult mai multe interschimbări; lista de frecvențe este de departe cea mai rapidă, însă doar pentru valori într-un interval mic.
Reguli de alegere a metodei
Decizia în trei pași
- Pasul 1: valori întregi într-un interval mic? Da - lista de frecvențe (cea mai rapidă).
- Pasul 2: valori mari sau texte, n rezonabil (până la câteva mii)? Selecția minimului (puține interschimbări).
- Pasul 3: vrem să urmărim pașii sau lista e deja aproape sortată? Metoda bulelor, eventual optimizată.
Regula practică: dublarea lui n înseamnă timp de 4 ori mai mare la O(n²) și doar de 2 ori mai mare la O(n). Restricțiile problemei decid metoda.
Ce trebuie să știi pentru test
Lista de verificare înainte de evaluare
- Definește corect: generare sistematică, șir recurent, șirul lui Fibonacci, sortare prin selecție, bule, frecvențe.
- Scrie din memorie codul pentru: primele n pătrate perfecte, termenii Fibonacci, selecția minimului, metoda bulelor, lista de frecvențe.
- Explică diferența dintre selecție, bule și frecvențe: număr de comparații, interschimbări, complexitate.
- Menționează complexitățile: O(n²) pentru selecție și bule, O(n + max) pentru frecvențe, O(n) pentru generare.
- Spune când alegi fiecare metodă: frecvențe pentru intervale mici, selecție sau bule pentru valori mari.
- Scrie corect capetele buclelor:
range(1, n + 1),range(i + 1, n),range(n - 1 - i). - Rezolvă o problemă combinată: generează datele, sortează-le, afișează rezultatul.
Exerciții de recapitulare și mini-provocări
Recapitulare 1 - numere pare
Cerință: Se citește n. Afișează primele n numere pare, în ordine crescătoare, separate prin spații.
Rezolvare:
n = int(input())
for i in range(1, n + 1):
print(2 * i, end=" ")
Explicație: termenul general al numerelor pare este 2 * i, iar end=" " ține valorile pe aceeași linie.
Recapitulare 2 - note sortate cu frecvențe
Cerință: Se citesc n note (valori între 1 și 10). Afișează notele în ordine crescătoare, separate prin spații, folosind lista de frecvențe.
Rezolvare:
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=" ")
Explicație: lista are 11 poziții (0-10), iar poziția i arată de câte ori apare nota i.
Mini-provocare - cel mai mare număr din cifre
Cerință: Se citește un număr n. Afișează cel mai mare număr care se poate forma cu cifrele lui n. Indicii: extrage cifrele cu % 10 și // 10, sortează-le descrescător, apoi reconstruiește numărul cu rezultat = rezultat * 10 + cifra.
Rezolvare:
n = int(input())
cifre = []
while n > 0:
cifre.append(n % 10)
n = n // 10
for i in range(len(cifre) - 1):
p = i
for j in range(i + 1, len(cifre)):
if cifre[j] > cifre[p]:
p = j
cifre[i], cifre[p] = cifre[p], cifre[i]
rezultat = 0
for c in cifre:
rezultat = rezultat * 10 + c
print(rezultat)
Explicație: pentru n = 25031, cifrele sortate descrescător devin 5, 3, 2, 1, 0, iar reconstrucția dă 53210 - cel mai mare număr posibil.
Greșeli frecvente la test
La generare
- Uitarea lui
int(input()): n rămâne text. range(1, n)în loc derange(1, n + 1): ultimul termen lipsește.- Acumulator neinițializat:
s = 0uitat înainte de buclă.
La recurențe
a = a + bîn loc dea, b = b, a + b: se pierde valoarea veche a lui a.- Condițiile inițiale uitate (F1 = F2 = 1).
- for în loc de while când numărul de termeni nu e cunoscut.
La sortare
- Bucla interioară pornită de la 0 în loc de
i + 1(selecția). - Bucla interioară până la n în loc de
n - 1 - i(bulele). - Lista de frecvențe cu dimensiune greșită: pentru note 1-10 trebuie
[0] * 11. - Interschimbarea cu
a = bfără a salva valoarea veche. - Comparația inversată: clasamentul devine crescător.
La test - format și verificare
- Formatul de ieșire greșit (spații în plus, linii lipsă): citește cu atenție cerința.
- Lipsa testării cazurilor limită: n = 1, lista deja sortată, valori egale.
- Alegerea unei metode ineficiente când restricțiile cer alta, de exemplu bulele pentru n mare cu valori într-un interval mic.
- Predarea unui program netestat pe exemplul dat din enunț.