Clasa a VI-a lecția 4 - 7 oct 2013

From Algopedia
Jump to navigationJump to search

Tema - rezolvări

Rezolvări aici [1]

Lecție

Debug rapid

Debugare mai rapidă și mai ușoara: printf-uri 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. În felul acesta puteți să activați sau să dezactivați mesajele de debug foarte rapid.

Recapitulare - continuare

Elemente minime

Să calculăm nrmin, numărul de elemente minime într-un vector. Prima idee, probabil cea mai simplă, este să executăm doi pași. În prima trecere găsim minimul, în cea de-a doua numărăm de cîte ori apare. Iată această soluție: 

  min = v[0];
  for ( i = 1; i < n; i++ )
    if ( v[i] < min )
      min = v[i];
  nrmin = 0;
  for ( i = 0; i < n; i++ )
    if ( v[i] == min )
      nrmin++;

O idee care duce la o soluție mai bună este să facem o singură trecere. Atunci cînd găsim un element mai mic decît minimul, îl păstrăm cu un număr de apariții 1. Atunci cînd găsim un element egal cu minimul, pur și simplu incrementăm numărul de apariții. Iată programul: 

  min = v[0];
  nrmin = 1;
  for ( i = 1; i < n; i++ )
    if ( v[i] < min ) {
      min = v[i];
      nrmin = 1;
    } else if ( v[i] == min ) {
      nrmin++;
    }

De ce este această soluție mai bună? Deoarece:

  • face o singură trecere prin vector.
  • poate să rezolve problema fără să aibă nevoie de stocarea elementelor într-un vector.

Ciurul lui Eratostene

Vă rog să recitiți explicațiile detaliate ale algoritmului în lecția de anul trecut. Reamintim aici doar algoritmul: 

char ciur[2000000];
...
fscanf( fin, "%d", &n );
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;

Nu uitați:

  • Vectorul ciur[] este de tip caracter și nu întreg!
  • În final vectorul ciur[i] este 0 dacă numărul este prim sau 1 în caz contrar.

Complexitate? Matematica este complexă, dar rețineți că metoda este aproximativ O(n) pentru valorile lui n cu care vom lucra noi. Pentru cei interesați, complexitatea este de fapt O(n∙log log n).

Căutare binară

Căutarea binară este un mod mai rapid de a căuta pe ce poziție se află un element într-un vector.

Ce complexitate are căutarea clasică a unui element într-un vector? Deoarece elementul se poate afla pe orice poziție în vector, iar noi căutăm liniar elementele, unul după altul, rezultă că, pe medie, vom face n / 2 comparații atunci cînd elementul se află în vector. Aceasta înseamnă o complexitate de O(n). Putem să rezolvăm această problemă mai rapid?

Putem, cu condiția ca vectorul să fie ordonat. Să ne folosim de o analogie: cum căutam un cuvînt în dicționar? Dicționarul are circa 60000 de cuvinte. Dacă am căuta la rînd, liniar, ne-ar lua zile să-l găsim. Și atunci deschidem dicționarul undeva, să spunem la mijloc. Ne uităm la ce literă sîntem, să spunem 'm'. Dacă noi căutăm 'gorilă', știm că 'g' < 'm', deci vom căuta la stînga, eliminînd jumate din dicționar. Vom continua la fel, deschidem undeva la jumate în jumatea rămasă și vedem iarăși la ce literă sîntem. Atunci cînd ajungem la litera 'g' vom continua cu a doua literă. În acest fel vom găsi cuvîntul rapid, probabil în jumate de minut, în loc de zile.

Aceasta este metoda căutării binare. Dacă vectorul nostru este ordonat, putem căuta mai întîi la jumate. Dacă elementul din vector este mai mic decît elementul căutat înseamnă că trebuie să ne uităm în jumătatea dreaptă, altfel ne uităm în cea stîngă. Apoi, în vectorul rămas, vom repeta algoritmul. La fiecare pas vom înjumătăți numărul de numere rămase. Ne oprim atunci cînd subvectorul rămas are fix un element. Dacă este elementul căutat, returnăm poziția sa, altfel el nu există. Iată o implementare posibilă:

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 ...
}

Matrice

Matricele sînt asemănătoare cu vectorii, dar cu două dimensiuni (coordonate, poziții) în loc de una. Vectorii se mai numesc și tablouri unidimensionale, iar matricele se mai numesc și tablouri bidimensionale.

Declarare matrice

Matricele se declară similar cu vectorii, însă cu o dimensiune în plus: 

int a[100][500];

Primul număr, 100 în cazul nostru, reprezintă numărul de linii al matricei a. Al doilea număr, 500 în exemplul de mai sus, reprezintă numărul de coloane al matricei a, sau numărul de elemente al fiecărei linii. O matrice poate fi privită ca un vector de vectori. În exemplul de mai sus a poate fi privită ca un vector de 100 de elemente. Fiecare element al acestui vector este, la rîndul lui, un alt vector, de 500 de elemente. Numărul total de elemente al matricei a este 100 x 500, adică 50000 de elemente întregi.

Citire matrice

Cum citim o matrice? Asemănător cu un vector, vom citi mai întîi numărul de linii și numărul de coloane, apoi elementele. Elementele se citesc, în general, de-a lungul liniilor, fiecare linie fiind citită ca un vector: 

fscanf( fin, "%d%d", &m, &n );
for ( i = 0; i < m; i++ )
  for ( j = 0; j < n; j++ )
    fscanf( fin, "%d", &a[i][j] );

Scriere matrice

Scrierea este asemănătoare cu citirea, cu mențiunea să avem grijă să tipărim un '\n' la finalul fiecărei linii: 

for ( i = 0; i < m; i++ ) {
  for ( j = 0; j < n; j++ )
    fprintf( fout, "%d ", a[i][j] );
  fprintf( fout, "\n" );
}

Căutare element în matrice

i = j = 0;
while ( (i < m) && (a[i][j] != e) ) {
  j++;
  if ( j >= n ) {
    j = 0;
    i++;
  }
}

Transpunere matrice

Temă în clasă: se dă o matrice pătrată, să se modifice astfel încît în final elementele ei să fie oglindite față de diagonala principală. Diagonala principală e cea care începe în colțul din stînga-sus și se termină în colțul din dreapta-jos. Această operațiune se mai numește si transpunere. 

for ( i = 1; i < n; i++ )
  for ( j = 0; j < i; j++ ) {
    aux = a[i][j];
    a[i][j] = a[j][i];
    a[j][i] = aux;
  }

Aceeași problemă pentru diagonala secundară. Diagonala principală e cea care începe în colțul din dreapta-sus și se termină în colțul din stînga-jos 

for ( i = 0; i < (n - 1); i++ )
  for ( j = 0; j < (n - i); j++ ) {
    aux = a[i][j];
    a[i][j] = a[n - 1 - j][n - 1 - i];
    a[n - 1 - j][n - 1 - i] = aux;
  }

Tema

Rezolvări aici [2]

Retrieved from "https://www.algopedia.ro/wiki/index.php?title=Clasa_a_VI-a_lecția_4_-_7_oct_2013&oldid=10058"