Sfaturi pentru olimpiadă – o abordarea eficientă a problemelor de informatică

O întrebare pe care o primim destul de des de la studenții noștri este cum abordăm noi, ca profesori, problemele date la concursuri. Intuiția vă spune că noi avem foarte multă experiență și ne bazăm strict pe ea. Este foarte adevărat că munca susținută ajută enorm, însă există mici trucuri de care ne folosim să grăbim procesul de rezolvare. Pentru studenți, acestea alcătuiesc o listă de sfaturi pentru olimpiadă. Și cum OSEPI, etapa națională este foarte aproape, s-ar putea să vă prindă bine să citiți.

Scopul principal al îndemnurilor noastre estă să câștigați timp prețios, atât la scrierea codului cât și la găsirea unei posibile erori. Veți observa că introducerea ordinii în procesul de scriere al codului vă va salva de la multe situații neplăcute.

Problemele de informatică, mai ales cele propuse în concursuri, vor avea enunțuri complexe, uneori foarte lungi. Sarcina voastră este să le deslușiți. Nu puteți programa până când nu înțelegeți ce a vrut autorul problemei de la voi.

Așa că, trageți aer în piept, înarmați-vă cu răbdare și citiți problema de câte ori este nevoie până când totul este clar. Adică până când puteți răspunde la următoarele întrebări corect:

• Am înțeles care sunt datele de intrare și în ce ordine le primesc?
• Îmi este clar la ce trebuie să ajung? Adică, pot să îmi explic singur cerința problemei?
• Am înțeles regulilele de procesare a datelor de intrare pentru a ajunge la rezultat?
• Am verificat ce am înțeles? Am luat exemplul datelor de intrare și le-am trecut prin algoritmul înțeles de mine? Rezultatul obținut este identic cu rezultatul dat ca exemplu?

Dacă aveți dubii la oricare dintre întrebările de mai sus, mai citiți o dată problema. Luați hârtie și pix și începeți să formulați algoritmul vostru folosind datele de intrare date ca exemplu. Verificați și iar verificați până când sunteți siguri că totul este clar. Abia atunci treceți la calculator să codați.

Nu mă refer la tehnica recursivă de programare, ci mai degrabă la concept și cum trebuie abordată problema pe care trebuie să o rezolvăm. După ce ați înțeles ce trebuie făcut, problema trebuie „spartă” în subprobleme clare și cu rezolvare directă.

Pentru o înțelegere mai bună, să luăm o problemă simplă, Cfdist. Problema poate fi împărțită în următoarele subprobleme:

1. declararea variabilelor necesare;
2. citirea datelor de intrare;
3. încărcarea vectorului de frecvență cu valorile necesare;
4. numărarea cifrelor folosind vectorul de frecvență;
5. afișarea rezultatului.

Logic, nu e așa? 3 pași vor fi prezenți întotdeauna, indiferent de problemă. Aceștia sunt pașii 1, 2 și 5. Ceilalți pași sunt dependenți de problema în sine.

Tot la acest pas trebuie să vă gândiți la tehnica de lucru, la ce algoritmi folosiți ca să rezolvați mai eficient problema. Acești algoritmi vă vor indica subproblemele voastre. De exemplu, dacă problema presupune lucrul cu numere prime, cel mai probabil o subproblemă va fi precalcularea ciurului lui Eratostene.

Uneori, veți vedea că unii pași se continuă în alții. De aceea, este bine să folosiți comentarii și să înțelegeți ce vreți să faceți.

Comentariile reprezintă o unealtă importantă în procesul de programare. O mică frază înainte de fiecare subproblemă vă va ajuta să realizați cum este împărțit programul vostru.

Tot comentariile pot fi utile să lăsați scris un exemplu în dreptul unei comenzi. De ce? Pentru că de multe ori veți fi nevoiți să tratați un caz particular și veți uita de ce ați pus o comanda IF într-un anumit loc.

Ele devin și mai importante dacă programul vostru nu rulează corect și trebuie să faceți verificări. Puteți câștiga timp prin o navigare mai ușoară prin cod.

Suntem la un nivel destul de înalt. Problemele pe care trebuie să le rezolvați necesită multe variabile, mulți vectori și, uneori, multe matrici. Codul poate fi foarte lung. Dacă ne uităm la problemele OSEPI 2021, etapa județeană, aveați destul de mult de scris la ele.

Să luăm următoarea bucată de cod:

fscanf( fin, "%d%d%d", &p, &r, &k );
for ( l = 0; l <= r+1; l++ )
    per[l][0] = per[0][l] = per[l][r+1] = per[r+1][l] = B;
for ( i = 0; i < k; i++ ) {
    fscanf( fin, "%d%d ", &l, &c );
    tab[l][c] = fgetc( fin );
}

Plecăm de la premiza că acest cod este corect, ca și logică. Este un cod destul de curat, pe care îl veți întâlni adesea. Dar cât de ușor este de înțeles la prima vedere? Mai ales dacă această secvență este scoasă din contextul programului principal. Dacă ar fi greșită, cât de ușor ar fi să ne dăm seama de ce se întâmplă?

Dar dacă l-am scrie astfel?

fscanf( fin, "%d%d%d", &cerinta, &dimensiune_matrice, &casute_semnalizare );
  for ( linie = 0; linie  <= dimensiune_matrice+1; linie ++ ) 
    perechi[l][0] = perechi[0][l] = perechi[l][dimensiune_matrice+1] = perechi[dimensiune_matrice+1][l] = BORDARE;
  for ( pas = 0; pas < casute_semnalizare; pas++ ) {
    fscanf( fin, "%d%d ", &linie, &coloana ); 
    tabla[linie][coloana] = fgetc( fin );      
  }

Deja schimbarea este evidentă. Putem identifica datele problemei mai ușor și pot urmări ce se întâmplă cu variabilele din program. Prin denumirea clară a lor, pot face verificări rapid în cod pentru depanare.

Înainte să scrieți mult la rezolvarea problemei, misiunea voastră este una scurtă și simplă: să fiți siguri că citiți datele de intrare corect. Trebuie să puteți să citiți fișierul de intrare corect și să îl afișați identic în fișierul de ieșire. Nu treceți mai departe la rezolvarea problemei dacă nu ați îndeplinit acest pas.

Dacă nu aveți datele de intrare corecte, problema va arunca doar rezultate greșite și veți pierde timp prețios căutând greșeala.

Este la fel ca așezarea în pagină a temei la limba română, când scriem o compunere. Programul are secțiuni clar definite. Comenzile imbricate trebuie să fie clare, la rândul lor. Această claritate se obține prin indentarea corectă.

Să studiem următoarea bucată de cod:

for(i=1; i<=9; i+=2) while(v[i]>0){
b=b*10+i;
v[i]--;
}
for(i=8; i>=0; i-=2)
while(v[i]>0){
b=b*10+i;
v[i]--;
}

Prima comandă FOR are pe aceeași linie comanda WHILE. Folosirea acoladelor lasă senzația că instrucțiunile aparțin comenzii FOR. Dacă nu suntem atenți, putem cădea în această capcană lejer.

A doua comandă FOR este scrisă puțin mai bine, în sensul în care comanda WHILE este pe rândul propriu următor. Însă în ambele structuri repetitive, lipsa indentării duce la o urmărire greoaie. Nici nu vreau să mă gândesc cum trebuie să verific codul în cazul de erori…

Iată o scriere lizibilă, indentată a codului anterior:

for(i=1; i<=9; i+=2) 
   while(v[i]>0){
      b=b*10+i;
      v[i]--;
   }

for(i=8; i>=0; i-=2)
    while(v[i]>0){
      b=b*10+i;
      v[i]--;
    }

De remarcat:

• fiecare comandă stă pe propriul său rând;
• folosirea acoladelor este prezentă atunci când structura deține o singură instrucțiune. În cazul curent, structura repetitivă WHILE este considerată o singură instrucțiune subordonată comenzii FOR. Deci, comanda WHILE este indentată.
• comanda WHILE are în subordine mai multe instrucțiuni, care vor fi indentate mai adânc (adică mai departe de marginea din stânga).
• Acolada de închidere a comenzii WHILE este indentată la același nivel cu comanda WHILE.

Cel mai probabil nu veți putea rezolva problema perfect din prima. Va trebui să reveniți asupra codului, să identificați unde programul nu funcționează corect. Dacă ați respectat sfaturile de mai sus, atunci verificarea se poate face rapid, sau cum spun unii, chirurgical 🙂 .

Niciodată nu vom folosi debugger-ul. Sunt mai multe motive de ce insist să nu o faceți, însă iată 3 dintre ele care ar trebui să fie mai mult decât convingătoare:

• La concursuri fizice, nu toate calculatoarele vor avea aplicații cu debugger instalat. Ce veți face atunci? Nu veți mai știi să vă corectați codul?
• Am avut experiențe în care debuggerul greșea în propriile calcule. Până la urmă, debuggerul este un program care se imbrică între comenzile programului vostru pentru a studia variabile și altele. Este scris de un om. Deci, iată rețeta perfectă pentru greșeli.
• Multe limbaje de programare nu au debugger. Veți rămâne blocați la C sau C++ pentru tot restul vieții?

Voi prezenta metodele pe care le folosesc eu, în peste 10 ani de experiență în programare.

Metoda utilizării comentariilor

O metodă foarte utilă atunci când consola nu returnează mesajul „Process returned 0”. Înseamnă că programul s-a blocat undeva înainte de ultima linie din programul principal (main).

Vom comenta secțiuni din program, pornind de la sfârșit către început. Cu fiecare secțiune comentată, vom rula programul și vom urmări mesajul din consolă, până când primim mesajul corect, „Process returned 0”. Astfel, vom identifica până unde programul rulează corect.

Apoi, vom comenta de sus în jos, începând cu prima secțiune de sub locul identificat anterior. Vom merge în jos până când programul nu mai rulează corect. În acest fel, am izolat secțiunea defectă.

Prin secțiune, mă refer la părți de cod, pe care voi le apreciați. De exemplu, o structură repetitivă FOR sau WHILE. Dacă acestea au subordonate mai multe comenzi, pot comenta dintre comenzile subordonate.

Metoda afișării în consolă

Dacă problema se rezolvă cu fișiere, nu înseamnă că nu vom mai folosi consola. Consola va servi afișărilor intermediare, menite să ne ajute să descoperim greșeli. Ceea ce este afișat în consolă trebuie comparat cu rezultatele calculelor noastre, pe care le-am făcut independent de program (probabil pe hârtie, pentru că este cel mai rapid). Practic, ne construim propriul debugger, lucru posibil în orice limbaj de programare și în orice situație.

Afișările le vom face înainte și după testarea unor condiții. Acolo este cel mai important. Vedem ce valori aveau toate variabilele implicate în test sau înainte de test. Astfel, înțelegem cum am depășit condiția. Vom avea răspuns la următoarele întrebări:

• Am intrat în structura IF / WHILE / FOR?
• Ce valori au variabilele intrate în structură?
• Ce valori au variabilele la sfârșitul structurii în cauză?

Elucidarea acestor întrebări vor conduce cu siguranță la concluzia căutată: aici este sau nu greșeala? Dacă da, atunci, cum se produce ea?

După cum ați putut citi, toate indicațiile de mai sus, aceste sfaturi pentru olimpiadă vă pot câștiga mult timp atunci când aveți de revizuit codul. Metodele de redactare ale codului și cele de depanare sunt universale, pentru orice limbaj de programare. Tot ce trebuie să faceți este să le aplicați pas cu pas.

Articol scris de către Mihai Tuțu.