clasa a IX-a · Python · Principii de elaborare a unui program · lecția 3
Testare, depanare și eficiența algoritmilor
100 minmate-info · Python
Înainte de lecția asta: IX.1 Gândire computațională și etapele unui program, IX.2 De la pseudocod (sau C++) la Python
Ce vei ști după lecție
- Construiești un set de teste: cazuri obișnuite, cazuri limită, date nevalide și câte un test pentru fiecare ramură.
- Urmărești valorile variabilelor într-un tabel de trasare și găsești rândul unde programul o ia razna.
- Încadrezi o eroare în categoria corectă: de sintaxă, de execuție sau de logică.
- Estimezi numărul de operații al unui algoritm și îl scrii în notația O: O(1), O(√n), O(n), O(n²).
Lecția are și o fișă de lucru, de rezolvat după ce o citești. Mergi la fișă ↓
Clasa a IX-aLecția 3 din 21 · mai sunt 18Urmează: IX.4 · Cifrele unui numărVezi toate lecțiile
Fișiere PDF și de lucru
- Lecția în PDF
versiunea de printat
- Fișa de lucru: Testare, depanare și eficiența algoritmilor
6 pagini · 100 min
1. Cum alegi testele
Un program care merge pe exemplul din enunț nu este neapărat corect (ai văzut asta în lecția py9- 01, la autobuze). Testele bune nu se aleg la întâmplare, ci după criterii.
Problema: biletul la muzeu costă 0 lei pentru copiii sub 7 ani și pentru cei de cel puțin 65 de ani, 5 lei pentru vârstele 7–18 și 15 lei în rest. Vârsta trebuie să fie între 0 și 120.
v = int(input())
if v < 0 or v > 120: # validarea datelor
print("vârstă invalidă")
elif v < 7 or v >= 65:
print(0)
elif v <= 18:
print(5)
else:
print(15)| Criteriu | Ce verifici | Teste (intrare → ieșire) |
|---|---|---|
| caz obișnuit | programul face ce trebuie, în mare | 30 → 15 |
| fiecare ramură | fiecare if / elif / else se execută măcar o dată |
3 → 0, 12 → 5, 30 → 15, -3 → vârstă invalidă |
| cazuri limită | valorile de pe granițe și vecinii lor | 6 → 0, 7 → 5, 18 → 5, 19 → 15, 64 → 15, 65 → 0 |
| extremele intervalului | cea mai mică și cea mai mare valoare permisă | 0 → 0, 120 → 0 |
| date nevalide | programul nu acceptă orice | -3, 121 → vârstă invalidă |
Sfat
Majoritatea greșelilor stau pe granițe: < în loc de <=, range(1, n) în loc de range(1, n + 1). Pentru fiecare comparație din program, testează valoarea de pe graniță și pe cea imediat de lângă ea.
Validarea datelor înseamnă că programul verifică datele înainte să le folosească. Mai sus, -3 este respins. Dacă însă utilizatorul scrie abc, programul se oprește chiar la int(input()) cu ValueError. Cum previi și asta vom vedea mai târziu; deocamdată, notează în analiză ce date sunt acceptate.
2. Trasarea: urmărești valorile variabilelor
Când un program dă rezultate greșite, nu ghici: urmărește valorile. Programul de mai jos află cea mai mare putere a lui 2 care nu-l depășește pe n.
n = int(input())
p = 1
k = 0
while p * 2 <= n:
p *= 2
k += 1
print(k, p) # pentru 20 afișează 4 16Tabelul de trasare pentru n = 20 are câte o coloană pentru fiecare variabilă și pentru condiție:
| pas | p |
k |
p * 2 <= n? |
|---|---|---|---|
| început | 1 | 0 | 2 ≤ 20, da |
| după pasul 1 | 2 | 1 | 4 ≤ 20, da |
| după pasul 2 | 4 | 2 | 8 ≤ 20, da |
| după pasul 3 | 8 | 3 | 16 ≤ 20, da |
| după pasul 4 | 16 | 4 | 32 ≤ 20, nu: ieșire |
Trei feluri de a urmări valorile pe calculator:
- un
printtemporar în buclă, de exempluprint("DEBUG", k, p), pe care îl ștergi apoi; - depanatorul din mediul de lucru (în Thonny: Debug, apoi pas cu pas cu F7);
- Python Tutor (pythontutor.com), care desenează variabilele la fiecare pas.
3. Trei tipuri de erori
| Tip | Când apare | Exemplu | Mesajul Python |
|---|---|---|---|
| de sintaxă | înainte de rulare: programul nu pornește deloc | if x > 3 (lipsește :) |
SyntaxError: expected ':' |
| de execuție | în timpul rulării, la un anumit rând; programul se oprește | print(10 // 0) "a" + 5 int("abc") |
ZeroDivisionError: integer division or modulo by zero TypeError: can only concatenate str (not "int") to str ValueError: invalid literal for int() with base 10: 'abc' |
| de logică | programul rulează până la capăt, dar rezultatul e greșit | range(1, n) în loc de range(1, n + 1) |
niciun mesaj |
Erorile de logică sunt cele mai periculoase, pentru că Python nu te anunță. Doar testele bune și trasarea le găsesc.
De știut
Ce faci, în ordine, când un program nu merge: 1) citești mesajul de eroare (tipul și rândul); 2) găsești cel mai mic test pe care greșește; 3) faci trasarea pe acel test; 4) repari; 5) rulezi din nou toate testele, nu doar pe cel reparat.
4. Eficiența: timp și memorie
Două programe corecte pot fi foarte diferite ca resurse:
- timpul de executare: câte operații face programul, în funcție de mărimea datelor (
n); - memoria: câte valori trebuie să țină minte în același timp.
Exemplu: suma 1 + 2 + … + n, calculată în două feluri.
s = 0
for i in range(1, n + 1): # n adunări
s += is = n * (n + 1) // 2 # câteva operații, oricât de mare e nPentru n = 10 000 000, pe calculatorul pe care am testat, bucla a durat aproximativ 1,3 secunde, iar formula a dat rezultatul instantaneu. Timpul exact depinde de calculator, dar raportul dintre ele, nu.
Ambele variante folosesc puține variabile (n, s, i), deci memorie constantă. Dacă ai memora toate cele n numere ca să le aduni la final, ai avea nevoie de memorie proporțională cu n. Pentru multe probleme nu e nevoie să păstrezi datele: le prelucrezi pe măsură ce le citești.
5. Notația O
Nu numărăm exact operațiile, ci cum crește numărul lor când crește n. Păstrăm doar termenul dominant și renunțăm la constante: 3n + 5 operații înseamnă O(n), iar n(n − 1) / 2 înseamnă O(n²).
| Ordin | Exemplu tipic | Operații pentru n = 10⁶ |
|---|---|---|
| O(1), constant | formula lui Gauss; ultima cifră n % 10 |
câteva |
| O(√n) | căutarea divizorilor cu d * d <= n (lecția py9-05) |
aproximativ 1000 |
| O(n) | o buclă for i in range(n) |
10⁶ (sub o secundă) |
| O(n²) | două bucle una în alta, fiecare până la n |
10¹² (peste o zi!) |
Orientativ, Python face câteva milioane până la zece milioane de pași simpli pe secundă; de aici estimările din tabel.
Cum determini ordinul:
| Structură | Regula | Exemplu |
|---|---|---|
| instrucțiuni fără bucle | O(1) | a = n // 10 % 10 |
o buclă care face n pași |
O(n) | for i in range(n): … |
| bucle una după alta | se adună, deci contează cea mai mare | O(n) + O(n²) = O(n²) |
| bucle una în alta | se înmulțesc | n pași × n pași = O(n²) |
buclă până la √n |
O(√n) | while d * d <= n: d += 1 |
Exemplu: câte perechi (i, j) cu i < j putem forma din n elevi?
c = 0
for i in range(n):
for j in range(i + 1, n):
c += 1
print(c) # pentru n = 10 afișează 45Bucla interioară face n − 1, apoi n − 2, …, apoi 0 pași: în total n(n − 1) / 2, deci O(n²). Același rezultat îl dă formula n * (n - 1) // 2, în O(1).
La BAC
La Bac apar des cerințe de tipul „algoritm eficient din punctul de vedere al timpului de executare”. Înainte să scrii codul, întreabă-te: pot evita o buclă printr-o formulă? Pot opri bucla mai devreme (de exemplu la √n)? Pot prelucra datele fără să le memorez pe toate?
6. Verifică-te
- Programul verifică dacă o notă
xeste de trecere (x >= 5). Ce trei valori testezi pe graniță? - Ce tip de eroare este fiecare: a)
prinț(x); b)print(x; c) media calculată cu(a + b) / 3în loc de/ 2? - Fă trasarea programului din secțiunea 2 pentru
n = 1. Ce afișează? - Care este ordinul de complexitate pentru
5n + 100operații? Dar pentrun² + 1000n? - Un algoritm O(n) și unul O(n²) rezolvă aceeași problemă. Pentru
n = 1000, de aproximativ câte ori face mai multe operații al doilea? - Ce ordin are o buclă
for i in range(1, n + 1)urmată de o altă buclăfor j in range(1, n + 1)(nu una în alta)?
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 · 6 pagini · 100 min
Testare, depanare și eficiența algoritmilor
- Construiești teste care ating fiecare ramură și fiecare graniță a unui program.
- Găsești erori prin trasare și le încadrezi corect: sintaxă, execuție, logică.
- Compari doi algoritmi după numărul de operații și după ordinul de complexitate.
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.
- ușoară
suma-gauss#1360
https://www.pbinfo.ro/probleme/1360/suma-gauss
lipsa#1255
https://www.pbinfo.ro/probleme/1255/lipsa
Temă
Rezolvă-le singur și bifează ce ai terminat. Bifele rămân salvate în acest browser.
- medie
countmod10#3609
https://www.pbinfo.ro/probleme/3609/countmod10
sabc#3978
https://www.pbinfo.ro/probleme/3978/sabc
Te-ai blocat la lecția asta?
Scrie-mi ce nu iese și vedem împreună de unde se blochează.
Răspunsuri
4,5și6(granița și cei doi vecini); plus extremele, de exemplu1și10.- Prima este de execuție (
NameError:prințnu există, iar asta se descoperă abia când se ajunge la acel rând); a doua, de sintaxă (paranteză neînchisă); a treia, de logică. - Condiția
2 <= 1este falsă de la început, deci bucla nu se execută: afișează0 1. - O(n), respectiv O(n²).
- De aproximativ 1000 de ori (n² / n = n).
- O(n):
n + n = 2npași.