Clasa a IX-a lecția 20 - 27 mar 2020

Concurs

Ați participat la un concurs de acasă.

Problemele din concurs

Problema Țări
Problema Merele lui Gary
Problema Triple Trouble

Soluții aici [1]

Parsare

La primele lecții am povestit despre cum calculăm câte operații execută un program și despre faptul că unele operații au o "greutate" mai mare asupra timpului de execuție pe care îl are programul în practică (exemplu: operațiile modulo sunt mai lente). Deși nu este prea băgată în seamă și citirea unui număr din fișier este considerată "o operație", deși nu este întocmai o singură operație. Ce este important de reținut este că citirea este o operație lentă.

Să zicem că avem de citit multe numere naturale, cum putem optimiza acest proces? Ne vom construi o funcție care citește și returnează următorul număr din fișier:

// citire numar natural
int readInt() {
  char ch;
  int res = 0;

  // eliminam caracterele de dinaintea numarului (spatiu, rand nou, orice caracter care nu este cifra)
  while (!isdigit(ch = fgetc(fin)));

  // adaugam cifrele la numar pana cand caracterul citit nu mai este cifra
  do {
    res = 10 * res + ch - '0';
  } while (isdigit(ch = fgetc(fin)));

  return res;
}
...
int main() {
...
  // citire n si apoi n numere naturale
  n = readInt();
  for (i = 0; i < n; ++i)
    a[i] = readInt();
}

Odată ce avem deja funcția de citire scrisă, parcă e și mai ușor de folosit și mai puțin de scris decât folosind scanf!

Utilități

Parsarea îmbunătățește timpul de execuție în cazul în care este necesar să citim multe numere dintr-un fișier, indiferent dacă suntem sau nu la vreun concurs, olimpiadă sau dacă lucrăm la un proiect personal.

Legat strict de concursuri, deși majoritatea problemelor au timp de execuție suficient încât o soluție bună să treacă testele și fără parsare, este posibil ca alte probleme să aibă timpul de execuție mai strict, pentru a diferenția soluții ineficiente sau mici neatenții în scrierea codului. Parsare este deci o practică bună și destul de simplă încât să o putem folosi pe viitor, unde este cazul.

În cazul concursului de astăzi, cred ca unii dintre voi ați fi beneficiat de folosirea acestei tehnici, în special în rezolvarea problemei Triple Trouble. Se putea totuși lua 100 puncte și fără, sursa oficială nefolosindu-se de parsare.