Clasa a VI-a lecția 2 - 27 sep 2018

From Algopedia
Jump to: navigation, search

Anunț

Pentru copiii noi:

  • Lecțiile sînt disponibile pe site-ul algopedia.ro
  • Programele se trimit la vianuarena doar în cadrul concursului temă, nu la arhivă. A trimite la arhivă înseamnă a pescui, un mod de a trișa și a cîștiga mai multe puncte. Vreau să văd rapid numărul de trimiteri la o problemă, nu pescuiți vă rog.

Comentarii

  • Unii din voi nu ați rezolvat problema monotonă de 100p, deși aveați rezolvarea în lecția de pe algopedia. Ori sînteți extrem de corecți, ori extrem de neatenți.
  • Unii din voi nu au încercat ultimele două probleme. Primele două erau de anul trecut, ultimele două erau propriu zis tema. Anul acesta mă voi uita cu atenție la seriozitatea cu care tratați temele.
  • Problemele nu sînt facultative. Nici o problemă nu este atît de grea încît să nu luați deloc puncte. Vreau să văd că încercați.

Tema - rezolvări

Discuție despre temă, cu analiza complexității timpului:

Ani bisecți

Cîți ani bisecți sînt între anul a și anul b, interval închis [a, b].

Rezolvarea 1

Vom merge cu a din 4 în 4 pînă ce ajungem la b. Pentru fiecare valoare a lui a testăm dacă este an bisect, testînd dacă fie nu se împarte la 100 fie se împarte la 400 și adunăm 1 la un contor de ani numit nr. O soluție ineficientă cu complexitate proporțională cu numărul de ani bisecți. Ce complexitate va fi ea? Numărul de ani bisecți este aproximativ (b-a)/4. Deoarece constantele multiplicative se ignoră, complexitatea va fi O(b-a). Pentru valori mari, va dura multe secunde.

Rezolvarea 2

Ne folosim de subproblema: să se afișeze numărul de numere divizibile cu k din intervalul [a, b]. Pentru a afla numărul de ani bisecți din intervalul [a, b] procedăm astfel: adunăm anii divizibili cu 4. Dar în felul acesta am adunat în plus anii divizibili cu 100, așa încît la pasul doi îi scădem. Dar acum am scăzut prea mulți ani, deoarece i-am scăzut pe cei divizibili cu 400, așa încît îi adunăm la loc. Astfel ajungem la o formulă relativ simplă:

n = b / 4 - b / 100 + b / 400 - (a - 1) / 4 + (a - 1) / 100 - (a - 1) / 400;

Deoarece formula are un număr fix de calcule, independent de a și b, această soluție are complexitate O(1).

Problema monotonă

Problema monotonă este una clasică. Am discutat o rezolvare posibilă la curs, iat-o mai jos.

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int n, a, b, i, cresc, monoton;

  fin = fopen( "monotona.in", "r" );
  fscanf( fin, "%d%d%d", &n, &a, &b ); // n si primele doua numere
  i = 2;
  // Ignoram toate elemente egale de la inceput, pt a stabili monotonia sirului
  while ( i < n && a == b ) {
    fscanf( fin, "%d", &b );
    i++;
  }
  // Daca sirul este crescator, monoton = 1; Altfel, monoton = -1.
  cresc = monoton = (a < b) ? 1 : -1;
  // Cat timp nu am terminat si este pastrata monotonia initiala
  while ( i < n && monoton == cresc ) {
    a = b;
    fscanf( fin, "%d", &b );
    if (a < b)
      cresc = 1;
    else if (a > b)
      cresc = -1;
    i++;
  }

  fout = fopen( "monotona.out", "w" );
  if (monoton == cresc)
    fprintf( fout, "da\n" );
  else
    fprintf( fout, "nu\n" );
  fclose( fout );

  return 0;
}

Problema puteri2

Problema puteri2 a fost dată la olimpiada pe școală 2012, clasa a 8a.

Iată o soluție posibilă:

#include <stdio.h>

#define MAX_N 10000
#define MOD 100019

int ai[MAX_N];

int main() {
  FILE *fin, *fout;
  int n, i, b, s, p;
  long long a;

  fin = fopen( "puteri2.in", "r" );
  fscanf( fin, "%d", &n );
  for ( i = 0; i < n; i++ )
    fscanf( fin, "%d", &ai[i] );
  s = 0;
  for ( i = 0; i < n; i++ ) {
    fscanf( fin, "%d", &b ); // nu are rost sa memoram sirul b[]
    a = ai[i];
    // vom calcula p = a^b cu algoritmul eficient, logaritmic
    p = 1;
    while ( b > 0 ) {
      if ( b % 2 == 1 )
        p = (p * a) % MOD;
      a = (a * a) % MOD;
      b /= 2;
    }
    s += p; // adunam puterea calculata la suma totala
  }
  fclose( fin );

  fout = fopen( "puteri2.out", "w" );
  fprintf( fout, "%d\n", s % MOD );
  fclose( fout );

  return 0;
}

Ce complexitate are acest algoritm? Știm că o ridicare la puterea b are complexitate O(log b). Vom face n astfel de ridicări la putere, deci complexitatea totală va fi O(n·log b).

Problema date

Problema date vă cere să calculați cîte zile sînt între două date calendaristice corecte.

Această problemă poate fi foarte grea, dacă nu o rezolvăm corect. O primă idee ar putea fi să pornim cu data d1 și să adunăm cîte o zi pînă ajungem la data d2. Foarte ineficient si cu complexitate mare (numărul de zile de afișat). O a doua idee ar putea fi să numărăm cîte zile avem de la data d1 pînă la sfîrșitul anului. Apoi să adunăm zilele din anii dintre d1 și d2. Apoi să adunăm numărul de zile de la începutul anului pînă la data d2. Această rezolvare este eficientă, dar foarte neelegantă, rezultînd într-un algoritm complicat.

Pentru o rezolvare eficientă și elegantă vom aplica metoda standard de prelucrare a timpului: vom converti ambele date la un număr de zile scurse de la 1 ianuarie anul 1 (exclusiv acea zi). Data d1 se transformă în numărul de zile nz1, iar d2 în nz2. În final vom afișa pur și simplu diferența numărului de zile, nz2 - nz1. Atenție mare la anii bisecți. Va trebui să folosim problema anterioară.

#include <stdio.h>

int szile[12] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30 };

int main() {
  FILE *fin, *fout;
  int i, z1, l1, a1, z2, l2, a2, nbisect;
  long long nz1, nz2;

  // insumam numerele din szile pentru a avea sumele partiale,
  // szile[i] = suma zilelor lunilor 1..i inclusiv i
  for ( i = 2; i < 12; i++ )
    szile[i] += szile[i-1];

  fin = fopen( "date.in", "r" );
  fscanf( fin, "%d%d%d%d%d%d", &z1, &l1, &a1, &z2, &l2, &a2 );
  fclose( fin );

  // calcul zile asociate datei 1
  a1--;
  nbisect = a1 / 4 - a1 / 100 + a1 / 400;
  nz1 = a1 * 365LL + nbisect + szile[l1 - 1] + z1;
  a1++;
  if ( l1 > 2 && ((a1 % 400 == 0) || ((a1 % 4 == 0) && (a1 % 100 != 0))) )
    nz1++;

  // calcul zile asociate datei 2
  a2--;
  nbisect = a2 / 4 - a2 / 100 + a2 / 400;
  nz2 = a2 * 365LL + nbisect + szile[l2 - 1] + z2;
  a2++;
  if ( l2 > 2 && ((a2 % 400 == 0) || ((a2 % 4 == 0) && (a2 % 100 != 0))) )
    nz2++;

  fout = fopen( "date.out", "w" );
  fprintf( fout, "%lld\n", nz2 - nz1 );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție? Deoarece ea face un număr constant de calcule independent de cele două date de la intrare complexitatea ei este O(1). Simplu, scurt și elegant, nu-i așa?

Problema paranteze1

Problema paranteze1 vă cere să spuneți dacă o expresie cu paranteze și acolade este corectă, caz în care se cere factorul maxim de imbricare.

Încercare de rezolvare

O primă idee ar fi să extindem soluția pentru un șir doar cu paranteze, fără acolade. În loc de un contor să folosim două contoare. Din nefericire această soluție pică teste de genul:

({)}

Aceasta nu v-a împiedicat pe unii din voi să trimită totuși această soluție, care nu trece nici măcar exemplele problemei, mizînd pe teste ușoare. Aceia dintre voi sînt pescari profesioniști!

Am putea încerca să corectăm această problemă ținînd minte ultima paranteză deschisă, pentru a ști ce să închidem. Soluția îmbunătățită va detecta eroarea în exemplul de mai sus. Dar nu va putea să detecteze erori la dincolo de închiderea ultimei paranteze. Iată un exemplu pe care această soluție nu va funcționa:

({())}

Am putea extinde și această soluție, memorînd ultimele două paranteze deschise, caz în care ea va funcționa pe exemplul de mai sus, dar nu va detecta erori dincolo de închiderea ultimelor două paranteze.

Soluția

Ideile de mai sus ne duc la soluție: observăm că oricîte paranteze deschise am ține minte putem crea un exemplu cu o paranteză deschisă în plus. Deci, ce putem face? Să memorăm toate parantezele deschise și încă neînchise! Locul contoarelor este luat de un vector în care memorăm nu doar numărul parantezelor deschise, ci și ordinea lor. Algoritmul va porni cu un vector vid, apoi va adăuga la coada lui parantezele deschise. Atunci cînd la intrare avem o paranteză închisă verificăm că ultima paranteză închisă este corectă, caz în care o eliminăm de la coada vectorului, pentru a ști care este paranteza de închis din-naintea ei. Aceasta este echivalentul decrementării contorului din soluția incorectă.

Iată o soluție posibilă:

#include <stdio.h>

char p[1000000];

int main() {
  FILE *fin, *fout;
  int np, max;
  char c;

  fin = fopen( "paranteze1.in", "r" );
  max = np = 0;
  c = fgetc( fin );
  while ( c != '\n' && max >= 0 ) {
    switch ( c ) {
    case '(':
    case '{':
      p[np] = c;
      np++;
      if ( np > max )
        max = np;
      break;
    case ')':
      if ( np > 0 && p[np-1] == '(' )
        np--;
      else
        max = -1;
      break;
    case '}':
      if ( np > 0 && p[np-1] == '{' )
        np--;
      else
        max = -1;
      break;
    default:
      max = -1;
    }
    c = fgetc( fin );
  }
  fclose( fin );

  if ( np != 0 )
    max = -1;
  
  fout = fopen( "paranteze1.out", "w" );
  fprintf( fout, "%d\n", max );
  fclose( fout );

  return 0;
}

Un vector în care atît adăugările cît și ștergerile se fac doar la coadă se numește stivă. Vom discuta mai multe despre stive în clasa a 7a.

Ce complexitate are această soluție? Prelucrăm n caractere (n este lungimea șirului) și facem un număr constant de calcule per caracter, deci complexitatea este O(n). Cîtă memorie folosește această soluție? Pe cazul cel mai rău, atunci cînd șirul de la intrare conține doar paranteze deschise, vom memora tot șirul, deci avem nevoie de 'O(n)' memorie, mai exact un milion de octeți. Cu o modifcare simplă putem reduce memoria la jumătate. Gîndiți-vă voi cum!

Doors

La rugămințile unora dintre voi vă voi mai lăsa o săptămînă pentru acest puzzle.

Rezolvări aici [1]

Lecție - continuare recapitulare

Interclasare vectori (array merge)

Dați doi vectori ordonați crescător construiți un al treilea vector ordonat crescător cu elementele din primii doi vectori. Sînt permise elemente duplicat. Exemplu: dați vectorii 1 4 6 9 și 2 4 5 9 12 rezultatul este vectorul 1 2 4 4 5 6 9 9 12.

O soluție ar fi să copiem toate elementele în cel de-al treilea vector și apoi să îl ordonăm. Există însă o soluție mai bună, bazată pe faptul că vectorii sînt deja ordonați. Să observăm că primul element din vectorul final este minimul dintre primele elemente din vectorii inițiali. Îl putem deci copia și apoi îl eliminăm din vectorul din care face parte. Apoi reluăm procedura. La un moment dat unul din vectori se va goli. În acel moment copiem ceea ce a rămas din vectorul nevid. Vom folosi trei indici i1, i2 și i3 care vor avansa în vectorii corespunzători, pe măsură ce selectăm elemente. Iată soluția:

// avem vectorii v1 de n1 elemente si v2 de n2 elemente
// vrem sa construim vectorul v3 de n1 + n2 elemente
i1 = 0;
i2 = 0;
i3 = 0;
while ( i1 < n1 && i2 < n2 ) { // mai avem elemente in ambii vectori?
  if ( v1[i1] < v2[i2] ) {     // daca v1 are elementul mai mic
    v3[i3] = v1[i1];           // il copiem
    i1++;                      // si avansam pe urmatorul element
  } else {                     // altfel v2 are elementul cel mai mic
    v3[i3] = v2[i2];           // il copiem
    i2++;                      // si avansam pe urmatorul element
  }
  i3++;                        // avansam si in vectorul v3
}
// in acest moment unul din vectorii v1, v2 este vid
while ( i1 < n1 ) { // incercam sa copiem elementele ramase in v1, daca exista
  v3[i3] = v1[i1];
  i1++;
  i3++;
}
while ( i2 < n2 ) { // incercam sa copiem elementele ramase in v2, daca exista
  v3[i3] = v2[i2];
  i2++;
  i3++;
}
n3 = n1 + n2;

Ce complexitate are acest algoritm? Se observă că la fiecare iterație a primei bucle while unul din indicii i1 sau i2 crește cu unu. La final, indicele care nu a parcurs întregul vector o va face în una din buclele while următoare. Vom face, în total, n1 + n2 prelucrări, deci complexitatea este O(n1+n2).

Cîtă memorie folosește acest algoritm? Avem, pe de o parte, vectorii inițiali, ce ocupă O(n1+n2). Avem însă nevoie și de vectorul rezultat, care ocupă tot O(n1+n2). Rezultă că memoria totală va fi O(n1+n2). Este important să remarcăm că avem nevoie de un vector suplimentar, vectorul rezultat. Nu putem refolosi vectorii inițiali.

Pentru a coda această metodă vă sfătuiesc pe cei ce nu ați luat 100p la problema portofel să o refaceți. Interclasarea apare din cînd în cînd la concursuri în diverse forme.

Ștergere element din vector

Dat un vector v și un element e să se elimine din vector prima apariție a elementului e, în caz că acesta apare în vector. Exemplu: v = 5 9 2 7 9 3 5 7 4 si e = 9, la final v = 5 2 7 9 3 5 7 4

Soluție incorectă

O soluție foarte populară este să căutăm elementul în vector și, în momentul cînd îl găsim să-l ștergem:

for ( i = 0; i < n; i++ )
  if ( v[i] == e ) {
    for ( j = i + 1; j < n; j++ )
      v[j-1] = v[j];
    i = n;
  }

Aceasta este o soluție urîtă deoarece:

  • folosește instrucțiunea for pentru un ciclu cu număr necunoscut de pași
  • modifică variabila de ciclu, i
  • nu folosește "cărămizile" învățate deja și anume căutarea unui element în vector și ștergerea unui element din vector

Soluție corectă

Ștergerea unui element din vector se face astfel:

  • Vom avea două etape: căutare element în vector + eliminarea propriu zisă.
  • În final numărul de elemente n se micșorează cu unu.

Iată implementarea corectă:

i = 0;
while ( i < n && v[i] != e )
  i++;
if ( i < n ) { // dacă am găsit elementul, îl eliminăm
  for ( j = i + 1; j < n; j++ )
    v[j-1] = v[j];
  n--;
}

Întrebare: putem elimina instrucțiunea if ( i < n )?

Constante in C

Constante în C: #define. Atunci cînd o constantă apare des în program este bine să îi dăm un nume cu #define. În felul acesta programul devine mai citibil, iar în cazul unei modificări ulterioare a constantei putem modifica într-un singur loc.

Exemplu: să se ordoneze n numere cu valori între 0 și 100.

Input Output
8

3 2 9 6 3 2 9 6

2 2 3 3 6 6 9 9

Rezolvare: vom folosi sortarea bazată pe vector de frecvență (counting sort). Construim vectorul de frecvență al numerelor de la intrare, apoi îl parcurgem afișînd pozițiile cu valori nenule de cîte ori arată acea valoare. Ca noutate vom folosi o constantă pentru valoarea maximă a unui element, adică 100. Iată programul:

// ordonare crescatoare a n numere cu valori intre 0 si 100
#include <stdio.h>

#define VAL_MAX 100

int v[VAL_MAX + 1];

int main() {
  int n, i, j;

  scanf( "%d", &n );
  for ( i = 0; i < n; i++ ) {
    scanf( "%d", &j );
    v[j]++;
  }

  for ( i = 0; i <= VAL_MAX; i++ )
    for ( j = 0; j < v[i]; j++ )
      printf( "%d ", i );
  printf( "\n" );

  return 0;
}

Avantajul folosirii constantei VAL_MAX este că, dacă ulterior enunțul problemei se schimbă, valoarea maximă devenind 200 sau alt număr, vom modifica doar VAL_MAX, într-un singur loc în program.

Un mod special de a folosi constantele este la debug: cît timp facem corecții la program putem defini o constantă care să "activeze" instrucțiuni de tipărire de debug:

#define D 1
...
if ( D )
  printf( "x=%d   y=%d   a=%d\n", x, y, a )
...

La final, cînd considerăm că programul este corect tot ce avem de făcut este să modificăm constanta D în zero:

#define D 0

Observați folosirea lui 0 și 1 ca valori adevărat, respectiv fals.

Instrucțiunea switch

Precum ştim instrucţiunea if implementează structura alternativă. Uneori avem nevoie de decizii multiple, de exemplu cînd vrem să ştim dacă o variabilă are valoarea 1, 2 sau 3. În aceste cazuri putem folosi o combinaţie de instrucţiuni if:

if ( n == 1 ) {
  cod pentru cazul 1;
} else if ( n == 2 ) {
  cod pentru cazul 2;
} else if ( n == 3 ) {
  cod pentru cazul 3;
}

Deoarece situaţiile cînd vrem să executăm diverse acţiuni în funcţie de valoarea unei variabile limbajul C se oferă instrucţiunea switch a cărei formă este:

switch ( n ) {
case constantă1:
  cod de executat dacă n este egal cu constantă1;
  break;
case constantă2:
  cod de executat dacă n este egal cu constantă2;
  break;
  .
  .
  . 
default:
   cod de executat dacă n nu este egal cu nici una din constante;
}

Exemplu: se citesc pe aceeaşi linie, în ordine, un caracter şi apoi două numere întregi, toate separate printr-un spaţiu. Dacă caracterul este una din operaţiile +, -, * sau / să se afişeze rezultatul acelei operaţii pe cele două numere. În caz contrar să se afişeze cuvîntul eroare.

Input Output
+ 12 191 203
* 12 11 132
 % 20 8 eroare

Rezolvare:

#include <stdio.h>

int main() {
  int a, b;
  char ch;

  ch = fgetc( stdin );
  scanf( "%d%d", &a, &b );
  switch ( ch ) {
  case '+':
    printf( "%d\n", a + b );
    break;
  case '-':
    printf( "%d\n", a - b );
    break;
  case '*':
    printf( "%d\n", a * b );
    break;
  case '/':
    printf( "%d\n", a / b );
    break;
  default:
    printf( "eroare\n" );
  }
  return 0;
}

De menţionat că nu este obligatoriu să avem o variabilă testată în switch, putem avea o expresie, cu condiţia ca ea să aibă o valoare întreagă, nu reală.

Ce complexitate are instrucțiunea switch? Ea este echivalentul a n instrucțiuni if una într-alta, unde n este numărul de cazuri din switch. Pe cazul cel mai rău acele n instrucțiuni if pot testa n-1 condiții, nu-i așa? Deci am fi tentați să spunem că instrucțiunea switch are complexitate O(n), ca și echivalentul său în if. Ei bine, nu este așa. Instrucțiunea switch este compilată de compilator cu tabele de salturi. Ea va selecta ramura corectă în O(1).

Iată un motiv pentru a folosi această instrucțiune ce era mai greu de explicat anul trecut: ea este și mai eficientă algoritmic.

Tema

Tema 2: să se rezolve următoarele probleme (program C trimis la vianuarena): (lista problemelor va fi afișată după ce începe tema)

Rezolvări aici [2]