Difference between revisions of "Clasa a 7-a lecția 15 - 17 dec 2015"

From Algopedia
Jump to navigationJump to search
 
Line 199: Line 199:
 
:''Int -> ['0'..'9']+''
 
:''Int -> ['0'..'9']+''
  
 +
==== Implementare 1 ====
 
Vă recomand să citiţi cu atenţie soluţia prezentată mai jos. Ea urmează toate aceste idei, clasice şi este comentată pentru a fi înţeleasă uşor. Din această problemă învăţăm ceva foarte general şi anume cum se face parsing. Această metodă se foloseşte în multe alte situaţii, cum ar fi analiza expresiilor numerice.
 
Vă recomand să citiţi cu atenţie soluţia prezentată mai jos. Ea urmează toate aceste idei, clasice şi este comentată pentru a fi înţeleasă uşor. Din această problemă învăţăm ceva foarte general şi anume cum se face parsing. Această metodă se foloseşte în multe alte situaţii, cum ar fi analiza expresiilor numerice.
  
<syntaxhighlight>#include <stdio.h>
+
<syntaxhighlight>
 +
#include <stdio.h>
 
#include <ctype.h> // pentru isdigit() si isalpha()
 
#include <ctype.h> // pentru isdigit() si isalpha()
  
Line 337: Line 339:
  
 
   return 0;
 
   return 0;
}</syntaxhighlight>
+
}
 +
</syntaxhighlight>
 +
 
 +
==== Implementare 2 ====
 +
O altă implementare găsiți și mai jos:
 +
 
 +
<syntaxhighlight>
 +
#include <stdio.h>
 +
#include <string.h>
 +
 
 +
int zileLuna[] = {0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365};
 +
char mat[][11] = {
 +
  "ianuarie",
 +
  "februarie",
 +
  "martie",
 +
  "aprilie",
 +
  "mai",
 +
  "iunie",
 +
  "iulie",
 +
  "august",
 +
  "septembrie",
 +
  "octombrie",
 +
  "noiembrie",
 +
  "decembrie",
 +
};
 +
 
 +
FILE *fin,*fout;
 +
 
 +
char c;
 +
 
 +
int n;
 +
struct Date {
 +
  int in, sf;
 +
} v[1001];
 +
 
 +
#define SHM_MAX (365 * 24 * 60)
 +
short int shm[SHM_MAX];
 +
 
 +
void advance() {
 +
  do {
 +
    c = fgetc(fin);
 +
  } while(c == ' ');
 +
}
 +
 
 +
int numar() {
 +
  int nr = 0;
 +
  while ('0' <= c && c <= '9') {
 +
    nr = nr * 10 + (c - '0');
 +
    advance();
 +
  }
 +
  return nr;
 +
}
 +
 
 +
int luna() {
 +
  char s[11];
 +
  int i=0;
 +
  while((c>='a' && c<='z') || (c>='A' && c<='Z')){
 +
    if(c>='A' && c<='Z')
 +
      c=c-'A'+'a';
 +
    s[i++]=c;
 +
    advance();
 +
  }
 +
  s[i] = 0;
 +
  i = 0;
 +
  while (strcmp(s, mat[i]) != 0)
 +
    i++;
 +
  return i;
 +
}
 +
 
 +
int data() {
 +
  int zi = numar();
 +
  int lun = luna();
 +
  int ora = numar();
 +
  advance(); // '.'
 +
  int minut = numar();
 +
  //printf("%d %d %d %d\n", zi, lun + 1, ora, minut);
 +
  return ((zileLuna[lun] + (zi - 1)) * 24 + ora) * 60 + minut;
 +
}
 +
 
 +
Date inregistrare() {
 +
  Date raspuns;
 +
  raspuns.in = data();
 +
  advance(); // '-'
 +
  raspuns.sf = data();
 +
  while(c != '\n' && c != EOF) {
 +
    advance();
 +
  }
 +
  while(c == '\n') {
 +
    advance();
 +
  }
 +
  return raspuns;
 +
}
 +
 
 +
void afisare(int minute) {
 +
  fprintf(fout, "%d %d %d", minute / 1440, minute % 1440 / 60, minute % 60);
 +
}
 +
 
 +
int main() {
 +
  fin = fopen("agenda.in", "r");
 +
  fout = fopen("agenda.out", "w");
 +
 
 +
  int i;
 +
  int cer;
 +
  fscanf(fin, "%d\n", &cer);
 +
  n = 0;
 +
  advance();
 +
  while (c != EOF) {
 +
    v[n++] = inregistrare();
 +
  }
 +
 
 +
  int max;
 +
  if (cer == 1) {
 +
    max = 0;
 +
    for (i = 0; i < n; i++)
 +
      if (v[i].sf - v[i].in > max)
 +
        max = v[i].sf - v[i].in;
 +
    afisare(max);
 +
  } else { // if (cer == 2 || cer == 3) {
 +
    int simultane;
 +
    for (i = 0; i < n; i++) {
 +
      shm[v[i].in]++;
 +
      shm[v[i].sf]--;
 +
    }
 +
    simultane = shm[0];
 +
    for (i = 1; i < SHM_MAX; i++) {
 +
      shm[i] += shm[i - 1];
 +
      if (shm[i] > simultane)
 +
        simultane = shm[i];
 +
    }
 +
    if (cer == 2) {
 +
      fprintf(fout, "%d", simultane);
 +
    } else { // if (cer == 3) {
 +
      int inceput, sfarsit, degeaba;
 +
      degeaba = 0;
 +
      inceput = SHM_MAX;
 +
      for (i = 1; i < SHM_MAX; i++) {
 +
        if (shm[i] == 0 && shm[i - 1] > 0) {
 +
          inceput = i;
 +
        } else if (shm[i] > 0 && shm[i - 1] == 0) {
 +
          sfarsit = i;
 +
          if (sfarsit - inceput > degeaba) {
 +
            degeaba = sfarsit - inceput;
 +
          }
 +
        }
 +
      }
 +
      afisare(degeaba);
 +
    }
 +
  }
 +
  return 0;
 +
}
 +
</syntaxhighlight>
  
 
= Lecție =
 
= Lecție =

Latest revision as of 12:16, 27 January 2016

Tema - rezolvări

Tema 13 clasa a 7-a

Rezolvări aici [1]

Paranteze 3

Problema paranteze 3 este una introductivă în analiza sintactică. Aceasta nu înseamnă că este uşoară! Analiza sintactică necesită stăpînirea bună a recursivităţii şi gramaticilor, ambele materii avansate.

Precum am menţionat data trecută o gramatică simplă pentru acest limbaj este:

E ⇾ ('('E')'|'{'E'}')*

Programul care rezultă este destul de direct. Vom face o singură modificare analizorului recursiv cu proceduri şi anume convenim ca E() să returneze factorul maxim de imbricare din subexpresia recunoscută de E().

#include <stdio.h>

FILE *fin, *fout;
int first;

int E() {
  int imb, maximb = 0;

  while ( first == '(' || first == '{' ) {
    imb = 0;
    switch ( first ) {
    case '{': // expresie { E }
      first = fgetc( fin );
      imb = E() + 1;
      if ( imb <= 0 || first != '}' )
        return -1;
      first = fgetc( fin );
      break;
    case '(': // expresie ( E )
      first = fgetc( fin );
      imb = E() + 1;
      if ( imb <= 0 || first != ')' )
        return -1;
      first = fgetc( fin );
      break;
    }
    if ( imb > maximb )
      maximb = imb;
  }
  return maximb;
}

int main() {
  int i;

  fin = fopen( "paranteze3.in", "r" );
  first = fgetc( fin );
  i = E();
  if ( first != '\n' )
    i = -1;
  fclose( fin );

  fout = fopen( "paranteze3.out", "w" );
  fprintf( fout, "%d\n", i );
  fclose( fout );

  return 0;
}

Expr

Problema expr cere să evaluăm o expresie. Pentru aceasta să găsim mai întîi gramatica care descrie limbajul expresiilor aritmetice din problemă. Pentru aceasta să definim următorii termeni:

  • Termen: Un termen este o subexpresie care nu conţine adunări sau scăderi. Astfel, o expresie este formată dintr-o înşiruire de termeni care sînt despărţiţi de operatori plus sau minus. Un termen va fi format din factori care se înmulţesc sau împart.
  • Factor: Un factor este o subexpresie care nu conţine adunări, scăderi, înmulţiri sau împărţiri. El este, în principiu, un număr, în faţa căruia putem avea semne, operatori unari plus sau minus. Tot un factor este şi o expresie între paranteze.

Putem acum introduce gramatica:

Expr ⇾ Term (('+'|'-')Term)*
Term ⇾ Fact (('*'|'/')Fact)*
Fact ⇾ Int | ('+'|'-')Fact|'('Expr')' 
Int ⇾ ('0'|'1'|'2'|...|'9')+

Să generăm de exemplu expresia 2+3*4:

Expr ⇾ Term + Term ⇾ Fact + Term ⇾ Int + Term ⇾ 2 + Term ⇾ 2 + Fact * Fact ⇾ 
⇾ 2 + Int * Fact ⇾ 2 + Int * Int ⇾ 2 + 3 * Int ⇾ 2 + 3 * 4

În continuare vom scrie analizorul recursiv cu proceduri, cu o mică adăugire: fiecare funcţie asociată lui Expr, Term şi Fact va returna valoarea subexpresiei analizate de acel neterminal. Astfel, în final, vom avea valoarea întregii expresii.

Iată programul care rezultă:

#include <stdio.h>

char f;
FILE *fin;

int expr();

int fact() {
  char first;
  int e;
  switch ( f ) {
  case '+':
  case '-':
    first = f;
    f = fgetc( fin );
    e = fact() * ((first == '+') ? 1 : -1);
    break;
  case '(':
    f = fgetc( fin );
    e = expr();
    f = fgetc( fin );
    break;
  default:
    e = 0;
    do {
      e = e * 10 + f - '0';
      f = fgetc( fin );
    } while ( f >= '0' && f <= '9' );
  }
  return e;
}

int term() {
  char first;
  int p = fact();
  while ( f == '*' || f == '/' ) {
    first = f;
    f = fgetc( fin );
    if ( first == '*' )
      p *= fact();
    else
      p /= fact();
  }
  return p;
}

int expr() {
  char first;
  int s = term();
  while ( f == '+' || f == '-' ) {
    first = f;
    f = fgetc( fin );
    s += term() * ((first == '+') ? 1 : -1);
  }
  return s;
}

int main() {
  FILE *fout;

  fin = fopen( "expr.in", "r" );
  f = fgetc( fin );
  fout = fopen( "expr.out", "w" );
  fprintf( fout, "%d\n", expr() );
  fclose( fout );
  fclose( fin );

  return 0;
}

Problema agenda

Problema agenda a fost dată la ONI 2014 baraj gimnaziu.

Tradusă în limbaj informatic problema este una clasică: date n intervale pe o dreapta, intervale ce se pot suprapune, să se găsească numarul maxim de suprapuneri, precum si cel mai mare interval pe dreapta unde nu se suprapune nici unul din intervalele originale.

Greutatea problemei constă în analiza intrării şi extragerea datelor. Acest gen de problemă este clasic în teoria compilării şi poartă numele de parsing. În general nu este genul de problemă de rezolvat într-o oră şi 20 de minute. În continuare vom descrie, pe rînd, soluţiile la cele două părţi ale problemei.

Calcul

Să presupunem că pentru fiecare linie am reuşit să extragem cele două date sub forma Z L H M. Desigur că pentru fiecare dată vom calcula un număr de minute echivalent, care reprezintă numărul de minute scurse de la începutul anului. Acum problema devine clasică şi avem două soluţii posibile:

Sortare şi scanare

Putem sorta capetele de intervale, ţinînd minte tipul capului, început sau sfîrşit de interval. Apoi vom parcurge în ordine aceste capete adunînd unu cînd începe un interval, sau scăzînd unu cînd se termină. Valoarea maximă a acestui număr de-a lungul parcurgerii ne va da maximul de intersecţii, adică punctul b. De asemenea, lungimea maximă pentru care acest număr este zero ne va da intervalul cerut la punctul c. Această soluţie este O(n log n) pentru sortare şi O(n) pentru scanare. Necesarul de memorie este O(n), mai exact vom avea nevoie de patru vectori, doi care ţin minte capetele şi doi care ţin minte tipul de capăt.

Calcul sume intervale

Care este scara de valori în care se încadrează capetele de interval? Ele sînt maxim numărul de minute într-un an, -adică 365 * 24 * 60 = 525600. Precum ştim deja, în situaţiile cînd valorile capetelor de interval sînt rezonabil de mici putem folosi precalcularea pentru a calcula suma acestor intervale în fiecare punct pe axă, sau, aşa cum îi spuneţi voi, şmenul lui Mars. Vom folosi un singur vector de 525600 elemente, iniţial zero. Pentru fiecare interval vom marca pe vector elementul de la care vom aduna 1 pîna la finalul vectorului, adică începînd cu capătul din stînga. Totodată vom marca şi elementul de la care vom scădea 1 pînă la finalul vectorului, adică începînd cu capătul din dreapta. După ce am "aşezat" astfel toate intervalele pe vector vom calcula pur şi simplu sumele parţiale de la 0 la i, pentru fiecare element v[i]. Pentru aceasta vom folosi acelaşi vector. După această prelucrare vom şti pentru fiecare minut al anului cîte activităţi de petrec în acel minut.

Punctul b se rezolvă găsind maximul în acest vector. Punctul c se rezolvă găsind cea mai lungă secvenţă de zerouri încadrată de elemente diferite de zero.

Această soluţie are avantajul simplităţii, neavînd nevoie de sortare. Complexitatea ei este O(n + m) unde m este valoarea maximă a capătului de interval. Memoria ocupată este de asemenea O(n + m). Deoarece avem maxim 1000 de activităţi rezultă nu putem avea mai mult de 1000 de intervale suprapuse într-un punct. De aceea vom declara un vector de elemente short folosind circa 1MB de memorie.

Parsing

Cum spuneam, această problemă este clasică în compilare. Pentru rezolvare vom folosi, deci, metode clasice. Din pacate acestea se predau abia în facultate. Să vedem.

Observaţii

  • Putem ignora spaţiile. De aceea o funcţie necesară este cea care ne dă următorul caracter diferit de spaţiu. O vom denumi nextChar();
  • Pentru a delimita cuvintele (numere, luni) vom avea nevoie să ne oprim cînd dăm de un caracter care nu se potriveşte (non-cifra sau non-litera). Dar, acel caracter va trebui folosit pentru cuvîntul următor, de exemplu după lună urmează ora. De aceea vom memora primul caracter citit dar nefolosit într-o variabilă globală first. Funcţia nextChar() va citi din fişier primul caracter non-spaţiu şi-l va depozita în first.
  • Vom scrie funcţii pentru a parsa un întreg, un cuvînt format numai din litere, o dată completă, precum şi o întreagă linie.
  • Traducerea de la numele unei luni la numărul ei se poate face eficient astfel: observăm că primele trei litere identifică unic luna. Deoarece avem numai 26·26·26 combinaţii putem folosi un vector de frecvenţă pentru a stoca numărul de lună pentru fiecare din combinaţii. Sau, şi mai bine, o matrice tridimensională de frecvenţă:
ind_luna[luna[0]-'a'][luna[1]-'a'][luna[2]-'a']
este chiar numărul lunii din variabila luna[].

Gramatica

Putem scrie o gramatică pentru fiecare linie, de exemplu:

Dates -> Date '-' Date Any*
Date -> Int Word Int '.' Int
Word -> Alpha+
Alpha -> ['a'..'z'] | ['A'..'Z']
Int -> ['0'..'9']+

Implementare 1

Vă recomand să citiţi cu atenţie soluţia prezentată mai jos. Ea urmează toate aceste idei, clasice şi este comentată pentru a fi înţeleasă uşor. Din această problemă învăţăm ceva foarte general şi anume cum se face parsing. Această metodă se foloseşte în multe alte situaţii, cum ar fi analiza expresiilor numerice.

#include <stdio.h>
#include <ctype.h> // pentru isdigit() si isalpha()

#define NR_LUNI 12
#define MIN_PER_AN (365*24*60)
#define NL 26

short minute[MIN_PER_AN+2];
int zile_pina[NR_LUNI] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30 };
char nume[NR_LUNI][4] = { "ian", "feb", "mar", "apr", "mai", "iun", "iul",
                          "aug", "sep", "oct", "noi", "dec" };
char ind_luna[NL][NL][NL]; // folosit pentru calcul numar luna din numele ei
int first; // primul caracter ne-spatiu din fisierul de la intrare
FILE *fin, *fout;

// Initializeaza tabelul de indici ai unei luni. Data o luna calculam
// rapid indicele ei uitindu-ne la primele trei litere, cu care mergem
// intr-un tabel de 26*26*26 elemente
void calcTabelIndiciLuni() {
  int i;
  for ( i = 1; i < NR_LUNI; i++ )
    ind_luna[nume[i][0] - 'a'][nume[i][1] - 'a'][nume[i][2] - 'a'] = i;
}

// Dat numele unei luni returneaza numarul ei
inline int indice( char *luna ) {
  return ind_luna[luna[0] - 'a'][luna[1] - 'a'][luna[2] - 'a'];
}

// Citeste un singur caracter non-whitespace de la intrare
inline void nextChar() {
  while ( (first = fgetc( fin )) == ' ' ); // sari peste spatii
}

// Citeste un intreg de la intrare
int getInt() {
  int n = 0;
  while ( isdigit( first ) ) {
    n = n * 10 + first - '0';
    nextChar();
  }
  return n;
}

// Citeste un cuvint format numai din litere de la intrare
void getWord( char *cuv ) {
  int i = 0;
  while( isalpha( first ) ) {
    cuv[i++] = tolower( first );
    nextChar();
  }
  cuv[i] = 0;
}

// Citeste o data calendaristica si returneaza numarul de minute scurse de la
// inceputul anului pina la aceasta data
int getDate() {
  int zi, ora, min;
  char luna[11];

  zi = getInt();   // ziua
  getWord( luna ); // luna
  ora = getInt();  // ora
  nextChar();      // ignora punctul
  min = getInt();  // minutul

  return (zile_pina[indice( luna )] + (zi-1)) * 24 * 60 + ora * 60 + min;
}

// Citeste o linie si calculeaza numarul de minute a primei date si al ultimei
// date.
void getDates( int *pprimul, int *pultimul ) {
  (*pprimul) = getDate();  // prima data a liniei
  nextChar();              // ignora caracterul '-'
  (*pultimul) = getDate(); // a doua data a liniei
  while ( (first = fgetc( fin )) != '\n' ); // cauta finalul de linie
  nextChar(); // treci la primul caracter pe linia urmatoare (sau EOF)
}

int main() {
  int cerinta, i, lun_max, max_simultan, pauza, pauza_max, primul, ultimul,
    final_min, inceput_max;

  for ( i = 1; i < NR_LUNI; i++ ) // calculeaza nr. zile pina la luna curenta
    zile_pina[i] += zile_pina[i-1];

  calcTabelIndiciLuni(); // initializeaza tabelul conversie nume luna -> numar

  fin = fopen( "agenda.in", "r" );
  fscanf( fin, "%d ", &cerinta );
  nextChar(); // avanseaza pe primul caracter diferit de spatiu
  inceput_max = lun_max = 0;
  final_min = MIN_PER_AN;
  while ( first != EOF ) {            // cita vreme nu e final de fisier
    getDates( &primul, &ultimul );    // citeste o linie
    if ( ultimul < final_min )        // cel mai mic final de activitate
      final_min = ultimul;
    if ( primul > inceput_max )       // cel mai mare inceput de activitate
      inceput_max = primul;
    if ( ultimul - primul > lun_max ) // cerinta 1, lungimea maxima
      lun_max = ultimul - primul;
    minute[primul]++;
    minute[ultimul]--;
  }
  fclose( fin );

  fout = fopen( "agenda.out", "w" );
  switch ( cerinta ) {
  case 1:
    fprintf( fout, "%d %d %d\n", lun_max/(24*60), lun_max/60%24, lun_max%60 );
    break;
  case 2:
    // calcul sume intervale suprapuse
    // cerinta 2, numarul maxim de activitati simultane
    max_simultan = 0;
    for ( i = 1; i <= MIN_PER_AN; i++ )
      if ( (minute[i] += minute[i-1]) > max_simultan )
        max_simultan = minute[i];
    fprintf( fout, "%d\n", max_simultan );
    break;
  case 3:
    // cerinta 3, pauza maxima fara nici o activitate
    for ( i = 1; i <= MIN_PER_AN; i++ )
      minute[i] += minute[i-1];
    pauza_max = pauza = 0;
    for ( i = final_min; i < inceput_max; i++ )
      if ( minute[i] == 0 ) {
        if( ++pauza > pauza_max )
          pauza_max = pauza;
      } else
        pauza = 0;
    fprintf( fout, "%d %d %d\n", pauza_max/(24*60), pauza_max/60%24, pauza_max%60 );
  }
  fclose( fout );

  return 0;
}

Implementare 2

O altă implementare găsiți și mai jos:

#include <stdio.h>
#include <string.h>

int zileLuna[] = {0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365};
char mat[][11] = {
  "ianuarie",
  "februarie",
  "martie",
  "aprilie",
  "mai",
  "iunie",
  "iulie",
  "august",
  "septembrie",
  "octombrie",
  "noiembrie",
  "decembrie",
};

FILE *fin,*fout;

char c;

int n;
struct Date {
  int in, sf;
} v[1001];

#define SHM_MAX (365 * 24 * 60)
short int shm[SHM_MAX];

void advance() {
  do {
    c = fgetc(fin);
  } while(c == ' ');
}

int numar() {
  int nr = 0;
  while ('0' <= c && c <= '9') {
    nr = nr * 10 + (c - '0');
    advance();
  }
  return nr;
}

int luna() {
  char s[11];
  int i=0;
  while((c>='a' && c<='z') || (c>='A' && c<='Z')){
    if(c>='A' && c<='Z')
      c=c-'A'+'a';
    s[i++]=c;
    advance();
  }
  s[i] = 0;
  i = 0;
  while (strcmp(s, mat[i]) != 0)
    i++;
  return i;
}

int data() {
  int zi = numar();
  int lun = luna();
  int ora = numar();
  advance(); // '.'
  int minut = numar();
  //printf("%d %d %d %d\n", zi, lun + 1, ora, minut);
  return ((zileLuna[lun] + (zi - 1)) * 24 + ora) * 60 + minut;
}

Date inregistrare() {
  Date raspuns;
  raspuns.in = data();
  advance(); // '-'
  raspuns.sf = data();
  while(c != '\n' && c != EOF) {
    advance();
  }
  while(c == '\n') {
    advance();
  }
  return raspuns;
}

void afisare(int minute) {
  fprintf(fout, "%d %d %d", minute / 1440, minute % 1440 / 60, minute % 60);
}

int main() {
  fin = fopen("agenda.in", "r");
  fout = fopen("agenda.out", "w");

  int i;
  int cer;
  fscanf(fin, "%d\n", &cer);
  n = 0;
  advance();
  while (c != EOF) {
    v[n++] = inregistrare();
  }

  int max;
  if (cer == 1) {
    max = 0;
    for (i = 0; i < n; i++)
      if (v[i].sf - v[i].in > max)
        max = v[i].sf - v[i].in;
    afisare(max);
  } else { // if (cer == 2 || cer == 3) {
    int simultane;
    for (i = 0; i < n; i++) {
      shm[v[i].in]++;
      shm[v[i].sf]--;
    }
    simultane = shm[0];
    for (i = 1; i < SHM_MAX; i++) {
      shm[i] += shm[i - 1];
      if (shm[i] > simultane)
        simultane = shm[i];
    }
    if (cer == 2) {
      fprintf(fout, "%d", simultane);
    } else { // if (cer == 3) {
      int inceput, sfarsit, degeaba;
      degeaba = 0;
      inceput = SHM_MAX;
      for (i = 1; i < SHM_MAX; i++) {
        if (shm[i] == 0 && shm[i - 1] > 0) {
          inceput = i;
        } else if (shm[i] > 0 && shm[i - 1] == 0) {
          sfarsit = i;
          if (sfarsit - inceput > degeaba) {
            degeaba = sfarsit - inceput;
          }
        }
      }
      afisare(degeaba);
    }
  }
  return 0;
}

Lecție

Precalculare

Precalcularea este un termen general pentru folosirea unor structuri auxiliare de date, fără o legătură directă cu problema de rezolvat, care ne ajută în rezolvarea problemei. Aceste structuri de date sînt calculate la început, ceea ce duce la denumire: precalculare.

În continuare vom vorbi despre cîteva exemple clasice de precalculare.

Ciurul lui Eratostene

V-aţi gîndit vreodată că ciurul lui Eratostene este de fapt o precalculare a unui vector de frecvenţă f[], care, pentru fiecare număr p, calculează f[p] care ne spune dacă p este prim? Avem cele doua variante, cea originală:

for ( d = 2; d < n; d++ )
  if ( ciur[d] == 0 ) // daca d este prim
    for ( i = d + d; i <= n; i = i + d ) // vom marca numerele din d in d
      ciur[i] = 1;

Există desigur şi varianta cu două optimizări:

  1. În a doua buclă for variabila i ia valorile 2∙d, 3∙d, 4∙d, ..., k∙d. Pentru k < d toate valorile de forma k∙d au fost deja tăiate de valorile k anterioare, drept pentru care nu are rost să le mai parcurgem. Putem să pornim cu i de la d∙d.
  2. Conform observației anterioare i pornește de la d∙d. De aceea nu are rost să mergem cu d mai departe de sqrt(n), deoarece nu vom mai găsi i astfel încît i ≤ n.

Implementarea optimizată:

for ( d = 2; d * d <= n; d++ )
  if ( ciur[d] == 0 ) // daca d este prim
    for ( i = d * d; i <= n; i = i + d ) // vom marca numerele din d in d
      ciur[i] = 1;

Şi acum surpriza: complexitatea ciurului lui Eratostene este O(n log log n) în ambele variante. Optimizările nu schimbă complexitatea algoritmului. Desigur că ele schimbă constanta, motiv pentru care le şi facem.

Numărul de divizori primi ai numerelor pînă la n

Ciurul lui Eratostene poate fi extins să calculeze numărul de divizori primi ai fiecărui număr din vectorul de frecvență. Modificarea este uşoară: vom folosi prima variantă, neoptimizată, şi în loc să marcăm cu 1 numerele neprime, vom aduna 1, marcînd faptul că acel număr prim divide numărul neprim.

Suma între i şi j

În multe probleme apare următoarea subproblemă: avem un vector de n elemente întregi, să se răspundă la multe întrebări de forma care este suma elementelor vectorului între poziţiile i şi j?. În acest caz vom precalcula o structură de date auxiliară, şi anume un vector s, astfel încît s[i] este suma elementelor de la 0 pînă la i. El se mai numeşte şi vectorul sumei prefixelor lui v. Construcția acestui vector se poate face liniar deoarece avem relaţia s[i] = s[i-1] + v[i].

Odată calculat acest vector putem răspunde în timp constant la întrebări. Suma elementelor între i şi j este s[j] - s[i-1]. Memoria folosită este O(n).

Suma între (i, j) şi (ii, jj)

Este problema anterioară extinsă la matrice: avem o matrice de numere întregi şi întrebări de forma: care este suma elementelor matricei în dreptunghiul care are drept colţuri opuse (i1, j1) şi (i2, j2)?. Această problemă apare în problema puncte5 dată la barajul de gimnaziu în 2012. În mod similar vom precalcula o matrice auxiliară cu suma elementelor matricei originale între (0, 0) şi (i, j). Ea poate fi calculată în timp constant per element, astfel:

Calcul matrice sume parțiale în dreptunghiuri care pornesc în origine

s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + m[i][j]

Odată calculată matricea s putem răspunde în timp constant la întrebări. Suma elementelor între (i, j) şi (ii, jj) este:

S = s[ii][jj] - s[ii][j-1] - s[i-1][jj] + s[i-1][j-1]

Calcul suma numerelor în orice dreptunghi

Numărul de biţi 1 într-un întreg

Cum putem calcula numărul de cifre 1 din reprezentarea în baza 2 a unui număr?

  • Direct: shift and mask.
  • Folosind expresia x & (x - 1).
  • Cu precalculare: ţinem un vector în care elementul v[x] este numărul de biţi 1 din reprezentarea în baza 2 a lui x.
  • Gîndiţi-vă la un algoritm fără vectori, dar mai rapid decît O(nr. biţi) (algoritmii discutaţi anteriori sînt O(nr. biţi).

Sume de intervale

Se dă un vector cu n elemente, iniţial zero. O operaţiune pe acest vector constă în incrementarea fiecărui element între indicii i şi j. Se dau, de asemenea, m operaţiuni de executat. Să se afişeze valorile finale ale vectorului.

Soluţia forţă brută implică execuţia celor m operaţiuni. O operaţiune constă în incrementarea a maxim n elemente din vector, deci avem n x m operaţii, plus afişarea elementelor finale. Complexitatea totală este O(mn).

Se poate mai bine? Putem optimiza timpul unei operaţiuni. Ideea este următoarea: în loc să incrementăm pe rînd elementele vectorului, am putea să le grupăm. Pentru aceasta vom întîrzia incrementarea, marcînd doar locurile unde trebuie să adunăm.

Cu alte cuvinte: am putea considera intervalele ca pe nişte paranteze aşezate pe o dreaptă. O paranteză deschisă înseamnă că de acum înainte trebuie să adunăm 1 la toate elementele care urmează. O paranteză închisă înseamnă că ne putem opri din adunat 1. Să presupunem că nu avem capete de interval suprapuse. Atunci am putea memora parantezele într-un vector separat. Vom memora 1 pentru o paranteză deschisă, -1 pentru o paranteză închisă şi 0 în caz că nu avem nici un capăt de interval în acel element.

Ipoteză: vectorul de sume parţiale ale acestui vector constituie chiar rezolvarea problemei. Să observăm ce se întîmplă atunci cînd adunăm s[i] = s[i] + s[i-1]: la început avem elemente zero. Cînd deschidem o paranteză acel element devine 1. Următoarele sume parţiale vor fi şi ele tot 1, pînă dăm de un alt capăt de interval. Să presupunem că mai deschidem o paranteză. Atunci suma va deveni 2 şi ea se va propaga în continuare pe elemente zero. Apoi să presupunem că se închide o paranteză. Adunînd -1 suma devine iarăşi 1, care se va propaga în continuare.

Funcţionează acest algoritm dacă avem capete de interval suprapuse? Da, cu condiţia ca elementul în care se suprapun capete să fie suma acelor capete, adică o sumă de 1 şi -1. Aceasta înseamnă că atunci cînd generăm vectorul de paranteze nu vom scrie s[i] = 1 ci s[i]++ (la fel şi pentru -1, vom decrementa).

Generalizare 1: putem generaliza această metodă pentru problema în care intervalele nu adună 1, ci orice număr, constant pe parcursul intervalului. Cum generalizăm? O paranteză deschisă nu va aduna 1 ci constanta respectivă.

Generalizare 2: dar dacă vectorul iniţial are valori diferite de zero? În acest caz vom calcula un vector separat, iniţializat cu zero, pe care facem calculul sumelor parţiale. Acest vector ne va spune cu cît s-a mărit fiecare element zero. În final vom aduna acest vector de sume parţiale la vectorul iniţial.

Acesta exemplu de precalculare, este cunoscut printre unii din voi drept "șmenul lui Mars", denumire care îmi displace deoarece sugerează că informatica este o colecție de șmenuri.

Cînd nu funcţionează această soluţie? Atunci cînd nu avem vector iniţial (elementele sînt toate zero), iar coordonatele intervalelor sînt prea mari pentru ca vectorul de sume parţiale să încapă în memorie. Să presupunem că ni se cere numărul maxim din vectorul de sume parţiale. În acest caz există o soluţie alternativă, mai generală (în sensul în care rezolvă o clasă mai mare de probleme cu intervale), care nu folosește precalculare: putem memora capetele de intervale, pe care apoi le ordonăm crescător, ţinînd minte de ce tip sînt, închis sau deschis. Apoi le parcurgem în ordine, calculînd sumele parţiale fără să le stocăm. Suma parţială maximă este răspunsul cerut.

Desigur că atunci cînd vectorul încape în memorie, e mai uşoară precalcularea. Acest tip de precalculare se poate extinde în două dimensiuni, pe matrice: se dau m dreptunghiuri care adună 1 la toate elementele respective dintr-o matrice. Această precalculare necesită O(n2) memorie. Ea nu se justifică decît în măsura în care este facil de programat, deoarece avem o soluție de aceeași complexitate care folosește varianta pe vector, folosind doar O(n) memorie.

Exemple de probleme cu precalculare

  • paisprezece: necesită precalcularea unui vector al primelor 17 numere prime, precum şi a ciurului lui Eratostene.
  • intervale: necesită precalcularea ciurului lui Eratostene precum şi a sumelor parţiale ale numărului de divizori primi.
  • reginald, o extindere a problemei anterioare.
  • puncte5: necesită precalcularea sumelor parţiale ale unei matrice.
  • extraterestri precalculare vector sume prefixe parțiale (a.k.a. șmenul lui Mars)
  • extraterestri1 Mars + normalizare coordonate
  • flori precalculare matrice sume prefixe parţiale (a.k.a. şmenul lui Mars 2D)
  • flori1 exemplu de problemă nerezolvabilă cu precalculare 2D din lipsă de memorie

Alte probleme:

  • el necesită precalcularea sumelor parţiale pe liniile si coloanele unei matrice.

Concluzii

  • Precalcularea foloseşte atunci cînd avem de răspuns la mai multe întrebări costisitoare. Aceste întrebări pot fi explicite, cerute de enunţ, sau implicite, decurgînd din metoda de rezolvare, ca la problema puncte5.
  • Precalcularea poate folosi şi atunci cînd numărul de întrebări este mult mai mare decît numărul de răspunsuri posibile, caz în care putem precalcula toate răspunsurile într-un tabel înainte de a răspunde la întrebări.
  • Precalcularea foloseşte o structură de date adiţională şi memorie suplimentară. Uneori putem economisi memorie folosindu-ne chiar de structura de date iniţială.

Tema

Tema 14 clasele 7/8

  • Expresie dată la OJI 2009 clasa a 9a
  • Adun dată la ONI 2006 clasa a 8a

Incercati sa rezolvati in vacanta si cateva din problemele cu precalculare. Vom reveni asupra temei, dupa vacanta.

Rezolvări aici [2]