Clasa VI/VII/VIII lecția 6 - 09 oct 2012

From Algopedia
Jump to navigationJump to search

Introducere

  • V-am anunțat pe cei ce nu prea au ce căuta la cerc. Cei ce vin sau nu vin și mai ales cei ce nu trimit teme.
  • Întrebare mai ales către cei buni: de ce nu vă faceți temele? Sînt cu ochii pe voi ☺
  • Temele din urmă trebuie făcute! Puneți întrebări dacă nu ați înțeles ce se cere, fie pe loc, fie ulterior pe email.
  • În continuare unii dintre voi nu respectați regulile: fără fstream! Vor fi consecințe, amenințare directă ☺.

Lecție

Cum puteți face printf-urile cu if ( D ):

#define D 1
...
if ( D ) {
  ... secvență de tipărire de debug ...
}

Iar la final redefiniți D ca fiind 0 pentru a elimina printf-urile de debug.

Recapitulare

  • Probleme de bază cu vectori
    • Numărul de elemente minime într-un vector (discuție două moduri, unul simplu cu două treceri, unul mai complex dar cu o singură trecere)
    • Rotație vector cu k elemente:
      void inversare( int i, int j ) {
        int aux;
        while( i < j ) {
          aux = v[i];
          v[i] = v[j];
          v[j] = aux;
        }
        i++;
        j--;
      }
      ...
      inversare( 0, n-1 );
      inversare( 0, k-1 );
      inversare( k, n-1 );
    • Căutare binară. Atenție: stinga este prima poziție in vectorul căutat, iar dreapta este prima poziție în afara vectorului căutat. Dacă respectați această convenție evitați bug-urile de final de căutare cînd indicii rămîn pe loc și o condiție incorectă in while poate să ducă la o buclă infinită.
      stinga = 0;
      dreapta = n;
      while ( dreapta - stinga > 1 ) {
        mijloc = (stinga + dreapta) / 2;
        if ( v[mijloc] > e )
          dreapta = mijloc;
        else
          stinga = mijloc;
      }
      if ( e == v[stinga] ) {
        ... găsit, procesare aici ...
      }
    • Ciurul lui Eratostene - unul din cei mai vechi algoritmi de calcul al numerelor prime. Pentru a calcula numerele prime mai mici sau egale cu n vom folosi un vector de booleeni p, p[i] este 0 dacă i este prim sau 1 dacă nu este prim. Inițial considerăm toate numerele prime, apoi pornim cu primul număr prim, 2, și facem toți multiplii lui 2 neprimi, adica 1. Continuăm în acest fel, căutînd următorul număr prim și marcînd toți multiplii lui ca neprimi. Ca optimizare remarcăm că pentru un număr prim i putem începe să marcăm multiplii de la i ∙ i, deoarece submultiplii de forma 2i, 3i, 4i, etc, au fost deja marcați ca neprimi la pașii anteriori. Complexitatea acestui algoritm este O(n log log n). Mai multe detalii la pagina Wikipedia - Ciurul lui Eratostene.
  • Lucrul cu caractere: citire din fișier folosind funcțiile fgetc/fputc. Exemplu: transformarea unui text de la litere mici la litere mari:
FILE *fin, *fout;
char c;
fin = fopen( "caractere.in", "r" );
fout = fopen( "caractere.out", "w" );
c = fgetc( in );
while ( c != EOF ) {
  if ( 'a' <= c && c <= 'z' )
    c = c - 'a' + 'A';
  fputc( c, fout );
  c = fgetc( fin );
}
fclose( fin );
fclose( fout );

Clasa a șasea: matrice

  • Reluăm tema: se citește o matrice pătrată de caractere 0 și 1, astfel: pe prima linie se va citi n, iar pe următoarele n linii se vor citi n caractere 0 sau 1. Afișați numărul de subpătrate ale matricei care conțin numai 1. De exemplu o matrice de dimensiune 4 care are toate elementele 1 are 16 + 9 + 4 + 1 = 30 de pătrate pline cu 1.
    • Atenție la citire. Trebuie introdus un spațiu după '%d' la citirea lui n cu fscanf, pentru a trece de '\n':
      fscanf( in, "%d ", &n );
      for ( i = 0; i < n; i++ ) {
        for ( j = 0; j < n; j++ )
          m[i][j] = fgetc( in );
        fgetc( in );
      }
    • Soluția forță brută are complexitate O(n5):
nrp = 0; // nrp (numarul de patrate) numara cite patrate am gasit
for ( lin = 0; lin < n; lin++ )
  for ( col = 0; col < n; col++ ) {
    maxlat = maxim( n - i, n - j ); // latura maxima a patratului care incape
    gasit1 = 1; // cita vreme patratul curent e plin de 1 mergem la patrate mai mari 
    lat = 1;
    while ( gasit1 && lat <= maxlat ) { // daca nu, nu mai marim latura
      l = 0;
      c = 0;
      while ( l < maxlat && m[lin + l][col + c] == 1 ) { // cautam primul 0
        c++; 
        if ( c == maxlat) {
          c = 0; 
          l++; 
        }
      } 
      if ( l >= maxlat ) // plin de 1
        nrp++; 
      else
        gasit1 = 0; // semnalam gasirea unui zero pentru a nu cauta patrate mai mari
      lat++;
    }
  }
  • Căutare submatrice în matrice: se dau două matrice pătrate, matricea a de dimensiune m și matricea b de dimensiune n. Se știe că 1 ≤ n ≤ m ≤ 100. Să se spună de cîte ori se regăsește matricea b în matricea a. Am făcut-o în clasă, celor ce nu au terminat le rămîne ca temă de casă.

Clasa a șaptea și a opta:

  • Problema de la a șasea în mai puțin de O(n5), cît mai bine.
    • Soluția forță brută are cinci bucle (conceptual, căci ultimele două bucle sînt "compactate" într-una) și complexitate O(n5). O puteți vedea mai sus.
    • O reducere ușoară la O(n4) se face avînd grijă să nu refacem calcule făcute anterior: cînd trecem de la lat la lat + 1 putem verifica numai elementele nou adăugate în pătrat, care sînt în număr de 2 lat + 1.
    • Reducerea la O(n3) se face printr-o construcție auxiliară: calculăm o matrice nr1 unde nr1[i][j] este numărul de elemente 1 din dreptunghiul (0,0)-(i,j). Matricea nr1 se poate calcula în O(n2) în felul următor:
      Calcul matrice număr 1 în dreptunghiuri care pornesc în origine



      Cu această matrice putem răspunde rapid la întrebări de forma "cîte elemente 1 avem într-o regiune dreptunghiulară din matrice (i, j)-(ii, jj)". Răspunsul este:
      Calcul număr 1 în orice dreptunghi



      Pe baza acestei matrice putem să păstram numai primele trei bucle din algoritmul forță brută. Pentru fiecare punct din matrice și pentru fiecare latură a unui pătrat ce pornește din acel punct, dacă numărul de 1 din acel pătrat este lat2 adunăm 1 la nrp. Acest algoritm are complexitatea O(n3).
    • Există mai mulți algoritmi O(n2) care sînt și optimi deoarece problema nu se poate rezolva în mai puțin de n2. Felicitări lui Ori, Alex și Bogdan care au găsit următorul algoritm: calculăm o altă matrice, max, unde max[i][j] este pătratul maximal plin de 1 care are colțul din dreapta-jos în elementul (i,j). Această matrice se poate calcula folosind formula
      Pentru fiecare pătrat maximal de latură lat avem 12 + 22 + 32 + ... + lat2 = lat (lat + 1) (2 lat + 1) / 6 pătrate.
      Un al doilea algoritm O(n2) ne introduce în analiza amortizată. Ca un prim exemplu de analiză amortizată am enunțat problema bibliotecarului.
  • Problema bibliotecarului (coada implementată cu două stive): un bibliotecar primește cărți una cîte una și le returnează în aceeași ordine, la cerere. În spatele ghișeului el are doi subalterni. Bibliotecarul trebuie să dea cărțile primite unuia din subalterni. Poate de asemenea să ceară înapoi cărți de la subalterni. Fiecare subaltern ține o stivă de cărți. Atunci cînd bibliotecarul îi dă o carte subalternul o pune peste toate celelalte, în stiva sa. Atunci cînd bibliotecarul îi cere o carte o ia pe prima din stivă și i-o returnează. Voi trebuie să găsiți algoritmul de funcționare a bibliotecarului astfel încît după un număr mare de depuneri și cereri de cărți numărul total de operații (înmînări de cărți) să fie cît mai mic ca complexitate. Puteți presupune că vor fi 500000 de depuneri de cărți și 500000 de cereri, în orice ordine coerentă.

Temă

  • clasa a 6-a:
    • Ce v-a rămas nefăcut din problemele medalion, cartier, numar5 (rezolvări medalion și numar5 aici [1])
    • problemele joc14, robinson, cifru de pe campion
    • Opțional: punctul c de la cartier mai bine de O(n2) (rezolvare aici: [2])
    • Opțional: tetris
  • clasa a 7-a și a 8-a,:
    • Scrieți o funcție recursivă care calculează an în timp O(log n)
    • De data trecută: folosiți o funcție recursivă penttru a afișa toate combinările de n luate cîte k (submulțimile de k elemente ale mulțimii {1, 2, 3, ..., n})
    • Opțional, grea: Pn - permutări de n. Date numărul natural n, folosiți o funcție recursivă pentru a afișa toate permutările mulțimii {1, 2, 3, ..., n} de k elemente. Exemplu: pentru n = 3 afișăm:
      1 2 3
      1 3 2
      2 1 3
      2 3 1
      3 1 2
      3 2 1
    • Gîndiți-vă la problema bibliotecarului, enunțată mai sus.
  • clasa a 7-a
    • ce a rămas din bile6, proiecte, zigzag
    • Opțional: problema patru de la campion
  • clasa a 8-a
    • ce v-a rămas din alune, cuburi4, optim (încercați să folosiți recursivitate) (rezolvare optim aici [3])
    • Opțional: problema tren1 de la campion

Rezolvări la problemele de recursivitate aici [4] și aici [5]