Lecție

In Pagina principala gasiti link catre profilul vostru din site-urile de pe care lucram. Asa monitorizez eu activitatea voastra.

Matrice elemente generale

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++;
  }
}

Matrice patratice

O matrice patratica este o matrice in care numarul de linii este egal cu numarul de coloane ( n = m ). Intr-o matrice patratica vom avea elemente specifice precum cele doua diagonale ale sale, diagonala principala si diagonala secundara, diagonale fata de care vom defini zone ale matricei patratice.

Parcurgerea diagonalei principale

for( i = 0; i < n; i++ ) 
      printf ( "%d  ", a[i][i] );

Parcurgerea diagonalei secundare

for (i = 0; i < n; i++ )
    printf ("%d  ", a[i][n-i-1]);

Parcurgerea elementelor de deasupra diagonalei principale

for( i = 0; i < n; i++ ) 
  for (j = i + 1; j < n; j++ )
    printf ( "%d ", a[i][j] );

Parcurgerea elementelor de sub diagonala principala

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

Parcurgerea elementelor de deasupra diagonalei secundare

for ( i = 0; i < n; i++ ) 
  for (j = 0; j < n - i - 1; j++ )
    printf ("%d ", a[i][j]);

Parcurgerea elementelor de sub diagonala secundara

for (i = 0; i < n; i++ ) 
  for ( j = n-i; j < n; j++ )
    printf ( "%d ", a[i][j] );

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 secundară 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;
  }

Flip si rotatie

Flip orizontal

for ( l = 0; l < m / 2; l++ )
  for ( c = 0; c < n; c++ ) {
     aux = a[l][c];
     a[l][c] = a[m - 1 - l][c];
     a[m - 1 - l][c] = aux;
}

Rotatie orizontala

for ( l = 0; l < m; l++ ) {     // pentru fiecare linie in parte ducem ultimul element de pe linie in fata
  aux = a[l][n - 1];            // salvam ultimul element in aux
  for ( c = n - 1; c > 0; c-- ) // mutam toate elementele ramase o pozitie la dreapta
     a[l][c] = a[l][c - 1];
  a[l][0] = aux;                // punem pe prima pozitie elementul salvat in aux
}

Matrice - aplicatii

Continuăm cu exerciții de bază cu matrice, de rezolvat în clasă.

Parcurgerea pe diagonale a unei matrice

Rezolvați problema diagonal la vianuarena:

Se citește o matrice pătrată de caractere. Să se afișeze două linii de caractere, fiecare linie conținînd toate caracterele matricei. Prima linie afișată conține caracterele matricei în parcurgerea pe diagonale paralele cu diagonala principală. A doua linie afișată conține caracterele matricei în parcurgerea pe diagonale paralele cu diagonala secundară. Diagonala principală este din coțul stînga sus în colțul dreapta jos. Diagonala secundară este din colțul dreapta sus, în colțul dreapta jos. Atenție! Fișierul de intrare conține numai matricea de caractere, fiecare linie terminîndu-se cu '\n'. Nu se dă n, dimensiunea matricei, trebuie să o deduceți. Exemplu:

Parcurgerea pe diagonale paralele cu diagonala principală	Parcurgerea pe diagonale paralele cu diagonala secundară
Prima linie afișată: minejoafkpbglchd	A doua linie afișată: abecfidgjmhknlop

Zoom x 2

Rezolvați problema zoomx2 la vianuarena:

Se citește o matrice pătrată de caractere. Să se construiască o altă matrice în care fiecare caracter apare de două ori pe orizontală și de două ori pe verticală (zoom ori 2). Exemplu:

Am vorbit despre două variante de implementare: una prin parcurgerea matricei originale, care pentru fiecare element completează patru elemente in matricea finală și a doua variantă care parcurge matricea finală și pentru fiecare element calculează corespondentul în matricea originală.

Căutare submatrice în matrice

Rezolvați problema căutare la vianuarena:

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. Exemplu:

În acest caz matricea b apare de 13 ori în matricea a.

Aplicație: problema joc

Am vorbit despre problema joc (ONI 2011 clasa a 7-a), care are o implementare ușoară cu condiția să țineți toate matricele de căutat, inclusiv rotațiile lor, într-un vector de 12 matrice cu elemente zero și unu. Astfel, va trebui să declarați un tablou tridimensional inițializat. Necesită atenție la declararea acestui tablou, dar programul se simplifică. Cum declaram aceasta matrice? O vom gandi ca un vector de 12 matrici 3x3 cu componente char. char forme[12][3][3]; Aceasta matrice va trebui initializata, conform figurilor date.

Sa ne reamintim:

//Initializare vector: elementele vor fi caractere, despartite de virgula, toate elementele incluse in acolade.
char a[3] = { 1, 0, 0 };
//Initializare matrice: elementele sunt 3 vectori cu 3 elemente, inclusi intre acolade

char a[3][3]= { { 1, 0, 0 },
                { 1, 0, 0 },
                { 1, 1, 1 } }
//Similar veti declara si matricea tridimensionala: elementele vor fi 12 matrice de 3x3 elemente, incluse intre acolade.

char a[12][3][3]={ 
                 { { 1, 0, 0 },
                   { 1, 0, 0 },
                   { 1, 1, 1 } },
                 ...............
                 }

Tema

matrix
Terminați problemele: diagonal, zoomx2, căutare
Joc1 dată la ONI 2011 clasa a 7-a.
Probleme cu parcurgerea matricelor patratice din pbinfo, dar dupa ce ati terminat problemele de mai sus, cate probleme puteti.

Optional 2

Cartier - ONI 2012 clasa a 6-a.

Clasa a VI-a lecția 11

Contents