Tehnici de programare
Dincolo de a cunoaște un limbaj de programare, un programator bun știe cum să abordeze o problemă: cum să o descompună, ce strategie să aleagă și cum să ajungă la o soluție corectă și eficientă. Aceste strategii generale de rezolvare, care nu depind de o anumită problemă, ci se pot aplica unei clase întregi de probleme, se numesc tehnici de programare.
O tehnică de programare nu este o rețetă fixă, ci un mod de a gândi soluția. Aceeași idee, odată înțeleasă, poate fi folosită la zeci de probleme diferite. Tocmai de aceea aceste metode sunt apreciate la examenul de Bacalaureat și la concursurile de informatică: ele arată că elevul înțelege raționamentul din spatele codului, nu doar sintaxa.
În acest capitol studiem două tehnici clasice și des întâlnite:
- Divide et Impera, o metodă recursivă prin care o problemă este spartă în subprobleme mai mici de același tip, rezolvate separat și apoi combinate;
- Backtracking, o metodă prin care construim soluția pas cu pas și revenim asupra alegerilor greșite, folosită atunci când căutăm toate variantele posibile.
Pentru backtracking detaliem și algoritmul general, un tipar care poate fi adaptat la majoritatea problemelor de acest fel.
Metoda Divide et Impera este un procedeu recursiv, specific problemelor care pot fi împărțite în probleme mai mici de același tip. Căutarea binară recursivă se rezolvă cu Divide et Impera.
Citește totMetoda backtracking generează sistematic toate soluțiile unei probleme, construind soluția pas cu pas și revenind atunci când o alegere nu mai poate fi continuată.
Citește totImplementarea recursivă a metodei backtracking în C++: structura generală cu valori candidate, condiție de validare și pasul înapoi, plus un exemplu complet. Material suplimentar.
Citește tot