Bella: /* Transpunere matrice */

2017-12-18T13:59:33Z

Transpunere matrice

New page

= Lecție =
In [http://algopedia.ro/wiki/index.php/Clasa_a_VI-a_isa 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:
<syntaxhighlight>int a[100][500];</syntaxhighlight>
Primul număr, <tt>100</tt> în cazul nostru, reprezintă numărul de linii al matricei <tt>a</tt>. Al doilea număr, <tt>500</tt> în exemplul de mai sus, reprezintă numărul de coloane al matricei <tt>a</tt>, sau numărul de elemente al fiecărei linii. O matrice poate fi privită ca un vector de vectori. În exemplul de mai sus <tt>a</tt> poate fi privită ca un vector de <tt>100</tt> de elemente. Fiecare element al acestui vector este, la rîndul lui, un alt vector, de <tt>500</tt> de elemente. Numărul total de elemente al matricei <tt>a</tt> este <tt>100</tt> x <tt>500</tt>, adică <tt>50000</tt> 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:
<syntaxhighlight>fscanf( fin, "%d%d", &m, &n );
for ( i = 0; i < m; i++ )
for ( j = 0; j < n; j++ )
fscanf( fin, "%d", &a[i][j] );</syntaxhighlight>

=== Scriere matrice ===
Scrierea este asemănătoare cu citirea, cu mențiunea să avem grijă să tipărim un <tt>'\n'</tt> la finalul fiecărei linii:
<syntaxhighlight>for ( i = 0; i < m; i++ ) {
for ( j = 0; j < n; j++ )
fprintf( fout, "%d ", a[i][j] );
fprintf( fout, "\n" );
}</syntaxhighlight>

=== Căutare element în matrice ===
<syntaxhighlight>i = j = 0;
while ( (i < m) && (a[i][j] != e) ) {
j++;
if ( j >= n ) {
j = 0;
i++;
}
}</syntaxhighlight>

== 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 ===

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

=== Parcurgerea diagonalei secundare ===
<syntaxhighlight>
for (i = 0; i < n; i++ )
printf ("%d ", a[i][n-i-1]);
</syntaxhighlight>

=== Parcurgerea elementelor de deasupra diagonalei principale ===
<syntaxhighlight>
for( i = 0; i < n; i++ )
for (j = i + 1; j < n; j++ )
printf ( "%d ", a[i][j] );
</syntaxhighlight>

=== Parcurgerea elementelor de sub diagonala principala ===
<syntaxhighlight>
for( i = 0; i < n; i++ )
for (j = 0; j < i; j++ )
printf ( "%d ", a[i][j] );
</syntaxhighlight>

=== Parcurgerea elementelor de deasupra diagonalei secundare ===
<syntaxhighlight>
for ( i = 0; i < n; i++ )
for (j = 0; j < n - i - 1; j++ )
printf ("%d ", a[i][j]);
</syntaxhighlight>
=== Parcurgerea elementelor de sub diagonala secundara ===
<syntaxhighlight>
for (i = 0; i < n; i++ )
for ( j = n-i; j < n; j++ )
printf ( "%d ", a[i][j] );
</syntaxhighlight>

=== 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''.
<syntaxhighlight>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;
}</syntaxhighlight>
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
<syntaxhighlight>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;
}</syntaxhighlight>
=== Flip si rotatie ===
==== Flip orizontal ====
<syntaxhighlight>
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;
}
</syntaxhighlight>
==== Rotatie orizontala ====
<syntaxhighlight>
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
}
</syntaxhighlight>

== Matrice - aplicatii ==
Continuăm cu exerciții de bază cu matrice, de rezolvat în clasă.
=== Parcurgerea pe diagonale a unei matrice ===
Rezolvați problema [http://varena.ro/problema/diagonal 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 <tt>'\n'</tt>. Nu se dă <tt>n</tt>, dimensiunea matricei, trebuie să o deduceți. Exemplu:
{| style="border-spacing:0;"
| [[Image:matr-parcurg-diag-princ.gif|frame|none|Parcurgerea pe diagonale paralele cu diagonala principală]]
| [[Image:matr-parcurg-diag-sec.gif|frame|none|Parcurgerea pe diagonale paralele cu diagonala secundară]]
|-
| <center>Prima linie afișată: ''minejoafkpbglchd''</center>
| <center>A doua linie afișată: ''abecfidgjmhknlop''</center>
|}

=== Zoom x 2 ===
Rezolvați problema [http://varena.ro/problema/zoomx2 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:

{| style="border-spacing:0;"
| <center>[[Image:matr-car.gif|frame|none|Matricea inițială]]</center>
| [[Image:matr-car-zoom-x2.gif|frame|none|Matricea finală]]
|}

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 [http://varena.ro/problema/cautare căutare] la vianuarena:

Se dau două matrice pătrate, matricea <tt>a</tt> de dimensiune <tt>m</tt> și matricea <tt>b</tt> de dimensiune <tt>n</tt>. Se știe că <tt>1 ≤ n ≤ m ≤ 100</tt>. Să se spună de cîte ori se regăsește matricea <tt>b</tt> în matricea <tt>a</tt>. Exemplu:

{| style="border-spacing:0;"
| <center>[[Image:matr-cautare.gif|frame|none|Matricea a]]</center>
| <center>[[Image:sablon-cautare.gif|frame|none|Matricea b]]</center>
|}

În acest caz matricea <tt>b</tt> apare de 13 ori în matricea <tt>a</tt>.

== Aplicație: problema joc ==
Am vorbit despre problema [http://varena.ro/problema/joc1 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:
<syntaxhighlight>
//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 } },
...............
}
</syntaxhighlight>

= Tema =
* [http://varena.ro/problema/matrix matrix]
* Terminați problemele: [http://varena.ro/problema/diagonal diagonal], [http://varena.ro/problema/zoomx2 zoomx2], [http://varena.ro/problema/cautare căutare]
* [http://varena.ro/problema/joc1 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
* [http://varena.ro/problema/cartier Cartier] - ONI 2012 clasa a 6-a.

Clasa a VI-a lecția 11 - Revision history

Bella: /* Transpunere matrice */