Metode de programare – introducere

Prezentarea unor metode elementare de rezolvare a problemelor: metoda forței brute și metoda greedy la nivel introductiv.

De la problemă la metodă: de ce nu ajunge o singură rețetă

Până acum ai scris algoritmi punctuali: suma cifrelor, minimul unui vector. O metodă de programare este un nivel deasupra: o strategie generală de atac, aplicabilă unei familii întregi de probleme. Când primești o problemă nouă, întrebarea corectă nu este „ce instrucțiuni scriu?”, ci „ce tip de strategie se potrivește?”.

Cele trei strategii studiate în clasa a IX-a, la nivel introductiv:

• forța brută – generezi toate variantele posibile și le verifici pe fiecare;
• greedy – construiești soluția pas cu pas, alegând de fiecare dată varianta care pare cea mai bună acum;
• divide et impera – spargi problema în subprobleme de același fel, mai mici, le rezolvi și combini rezultatele.

Diferența dintre ele nu este de sintaxă, ci de garanții și cost: forța brută găsește sigur soluția, dar poate dura enorm; greedy este rapid, dar nu întotdeauna corect; divide et impera este rapid și corect, dar se aplică doar problemelor care se lasă sparte natural în bucăți.

La examen, recunoașterea metodei dintr-un algoritm dat este o cerință în sine — de aceea merită să reții pentru fiecare metodă tiparul ei, nu doar un exemplu memorizat.

Metoda forței brute: generează și verifică

Forța brută (căutarea exhaustivă) parcurge tot spațiul soluțiilor posibile și testează fiecare candidat. Schema generală: pentru fiecare candidat posibil, dacă îndeplinește condițiile problemei, îl reții sau îl afișezi.

Exemple tipice pentru clasa a IX-a:

• divizorii unui număr n: verifici pe rând toate numerele de la 1 la n;
• verificarea primalității: testezi dacă vreun d între 2 și n-1 divide n (rafinare: e suficient până la radical din n — dacă n are un divizor propriu, are unul cel mult egal cu radicalul său);
• toate perechile (a, b) cu o proprietate: două bucle imbricate care generează fiecare combinație;
• căutarea secvențială într-un vector — cea mai simplă formă de forță brută.

Avantajele: corectitudine garantată (nu ai cum să ratezi soluția dacă verifici tot) și simplitate — algoritmul se scrie ușor și e ușor de demonstrat.

Dezavantajul decisiv: explozia numărului de candidați. Pentru perechi ai n la pătrat candidați, pentru triplete n la cub; la n = 1000, tripletele înseamnă deja un miliard de verificări. De aceea forța brută este mereu punctul de plecare — soluția de siguranță — iar restul metodelor există tocmai ca să evite parcurgerea întregului spațiu atunci când se poate.

Metoda Greedy: alege mereu ce pare cel mai bun acum

Greedy (lacom) construiește soluția pas cu pas: la fiecare pas alege varianta care aduce câștigul maxim în acel moment, iar alegerea făcută nu se mai revizuiește niciodată. De aici vin și viteza, și riscul metodei.

Exemplul clasic: plata unei sume cu număr minim de bancnote din sistemul 1, 5, 10, 50, 100. Strategia: ia mereu cea mai mare bancnotă care încape în suma rămasă. Pentru 130 alegi 100, apoi 10, 10, 10 — patru bancnote, optim.

Alte aplicații standard: problema spectacolelor (alegerea numărului maxim de spectacole care nu se suprapun, ordonându-le după ora de încheiere) și amestecuri de tip maximizarea sumei: alegi cele mai mari k elemente dintr-un vector sortat.

Partea critică, cerută explicit la teorie: greedy nu garantează întotdeauna optimul. Alegerea local optimă poate bloca soluția global optimă. Contraexemplul canonic: cu bancnote de 1, 3 și 4, pentru suma 6 greedy alege 4 + 1 + 1 (trei bancnote), deși optimul este 3 + 3 (două). Metoda dă optimul doar pentru probleme cu o anumită structură — iar la nivelul clasei a IX-a reții că fiecare aplicare greedy trebuie justificată, nu presupusă corectă.

Tiparul recunoscut la examen: sortare după un criteriu + parcurgere cu alegeri definitive = aproape sigur greedy.

Divide et Impera: împarte și stăpânește

Divide et impera rezolvă o problemă în trei timpi:

• împarte problema în două sau mai multe subprobleme de același tip, dar de dimensiuni mai mici;
• stăpânește: rezolvă subproblemele — de regulă recursiv, până ajung atât de mici încât se rezolvă direct (cazul de bază);
• combină rezultatele subproblemelor în rezultatul problemei inițiale.

Exemplul emblematic la acest nivel: căutarea binară într-un vector sortat. Compari valoarea căutată cu elementul din mijloc: dacă e egală, ai terminat; dacă e mai mică, repeți căutarea doar în jumătatea stângă; altfel doar în dreapta. La fiecare pas dimensiunea se înjumătățește, deci într-un vector cu un milion de elemente ajung circa 20 de comparații — față de un milion la căutarea secvențială. Condiția de aplicare este esențială și des uitată: vectorul trebuie să fie sortat; pe un vector neordonat căutarea binară dă rezultate greșite.

Alte exemple pe același schelet: minimul/maximul unui vector determinat prin împărțirea în două jumătăți, iar în clasele următoare sortările rapide (MergeSort, QuickSort).

Recunoașterea la examen: funcție recursivă cu parametrii stânga și dreapta (capetele unei porțiuni), care calculează mijlocul și se autoapelează pe jumătăți — acesta e tiparul divide et impera.

Cât de repede merge? Primele noțiuni de eficiență

Doi algoritmi corecți pot diferi enorm în timpul de execuție. Eficiența se estimează numărând operațiile dominante (comparații, atribuiri repetate) în funcție de dimensiunea datelor n — nu cronometrând pe un calculator anume.

Ordinele de mărime pe care trebuie să le recunoști:

• liniar – o singură parcurgere: suma elementelor, căutarea secvențială; timpul crește proporțional cu n;
• pătratic – două bucle imbricate care parcurg fiecare pereche: sortările elementare (selecție, bubble sort); la dublarea lui n, timpul crește de patru ori;
• logaritmic – dimensiunea se înjumătățește la fiecare pas: căutarea binară; chiar și pentru n uriaș, numărul de pași rămâne mic (log în baza 2 din 1.000.000 este circa 20).

Două comparații care fixează intuiția: căutarea binară (logaritmică) bate zdrobitor căutarea secvențială (liniară), dar cere vector sortat; iar un algoritm liniar isteț bate unul pătratic naiv de îndată ce n depășește câteva mii.

Morala practică, în spiritul subiectelor de examen care cer „algoritm eficient”: eficiența se câștigă din idee (alt algoritm, altă metodă), nu din cosmetizarea codului. A muta o instrucțiune sau a redenumi variabile nu schimbă ordinul de mărime; a înlocui generarea tuturor perechilor cu o parcurgere unică, da.

Test — 6 întrebări ca la examen