Algoritmi în Python pentru liceu: de la cerință la verificare
Un algoritm descrie pașii prin care rezolvi o problemă pentru datele acceptate. Codul Python este o modalitate de a scrie acești pași. Începe prin a preciza intrarea, ieșirea și regulile; astfel poți verifica soluția înainte să te preocupi de cât de scurtă este.
Definește problema înainte să scrii bucla
Să presupunem că primești o listă și cauți prima poziție a unei valori. Pozițiile încep de la zero. Dacă valoarea apare de mai multe ori, întorci poziția primei apariții; dacă lipsește, întorci None. Aceste reguli fac diferența dintre o soluție verificabilă și una care pare să funcționeze pentru un singur exemplu.
Pentru lista [4, 9, 4], căutarea lui 4 trebuie să întoarcă 0, iar căutarea lui 9 trebuie să întoarcă 1. Căutarea lui 8 și orice căutare în lista goală întorc None. Scrie aceste rezultate așteptate înainte de implementare.
Căutarea liniară: verifică fiecare poziție în ordine
enumerate oferă simultan poziția și valoarea fiecărui element. Dacă găsești ținta, return oprește imediat funcția. Poți întoarce prima apariție deoarece toate pozițiile anterioare au fost deja verificate. Dacă bucla se termină, niciun element nu a fost egal cu ținta.
Exemplul afișează 0. Nu verifica rezultatul prin if rezultat, deoarece poziția 0 este o valoare validă și este falsă în context boolean. Folosește rezultat is not None când vrei să separi «găsit la poziția zero» de «negăsit».
def cauta_prima(valori, tinta):
for pozitie, valoare in enumerate(valori):
if valoare == tinta:
return pozitie
return None
rezultat = cauta_prima([4, 9, 4], 4)
if rezultat is not None:
print(rezultat)Numărarea: când nu te oprești la prima potrivire
Dacă problema cere numărul de apariții, trebuie să continui până la finalul listei. Contorul începe de la zero, crește numai la egalitate și descrie după fiecare pas câte potriviri ai văzut până atunci. Această proprietate te ajută să justifici rezultatul, nu doar să urmărești codul.
Pentru [4, 9, 4] și ținta 4, funcția întoarce 2. Pentru lista goală întoarce 0. Un return plasat în interiorul buclei ar opri funcția prea devreme; indentarea schimbă aici algoritmul, chiar dacă programul rămâne valid sintactic.
def numara_aparitii(valori, tinta):
total = 0
for valoare in valori:
if valoare == tinta:
total += 1
return total
print(numara_aparitii([4, 9, 4], 4))Cum estimezi timpul și memoria
Pentru n numere obișnuite, căutarea liniară face cel mult n comparații, iar numărarea parcurge întotdeauna cele n elemente. Spunem că timpul este O(n), considerând comparația dintre valorile noastre o operație de cost constant. Funcțiile păstrează un număr constant de variabile suplimentare, deci folosesc O(1) memorie auxiliară, fără a număra lista de intrare.
Căutarea binară poate reduce numărul comparațiilor pe date ordonate, dar ordonarea este o condiție necesară. Nu aplica automat un algoritm mai rapid fără să verifici ce presupune. Pentru început, o soluție liniară corectă și explicată este o bază bună pentru comparații ulterioare.
Întrebări frecvente
Care este diferența dintre algoritm și program?
Algoritmul descrie pașii și regulile soluției. Programul îi exprimă într-un limbaj concret, precum Python, cu instrucțiunile și tipurile acelui limbaj.
Căutarea liniară cere o listă sortată?
Nu. Ea verifică elementele în ordine și funcționează și pe o listă nesortată. Căutarea binară are nevoie de date ordonate potrivit comparației folosite.
Este poziția zero un rezultat valid?
Da. Primul element al unei liste Python se află la poziția 0. În exemplul acestui ghid, absența valorii este reprezentată separat prin None.
Surse și lectură suplimentară
Ghid editorial AiLaBac. Citește ghidurile în format text.