Clasa a IX-a lecția 29

Lectie ( TEORIE )

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", &n, &m );
for ( i = 0; i < n; i++ )
  for ( j = 0; j < m; 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. Vom afisa linie cu linie, pentru fiecare linie, afisam elementele de pe acea linie si un sfarsit de linie.

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

Parcurgerea elementelor unei matrice

In functie de cerintele problemei, parcurgerea elementelor matricei, in vederea prelucrarii acestora, poate fi facuta in mai multe modalitati. Cea mai intalnita metoda de a parcurge elementele unei matrice, este parcurgerea linie cu line. Sa presupunem ca ni se cere sa calculam suma elementelor tuturor elementelor. Iata allgoritmul:

s = 0;
for ( i = 0; i < n; i++ ) 
  for ( j = 0; j < m; j++ )
    s += a[i][j];
}

Un algoritm echivalent este acela de a parcurge matricea coloane cu coloana:

s = 0;
for ( j = 0; j < m; j++ )
  for ( i = 0; i < n; i++ ) 
    s += a[i][j];
}

Din punct de vedere al eficientei, credeti ca este vreo deosebire intre cei doi algoritmi?

Căutare element în matrice

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

Permutarea coloanelor spre stanga

Se dă o matrice cu n linii şi m coloane şi elemente numere naturale. Să se permute coloanele matricei circular spre stânga cu o poziție. PermCol

#include <stdio.h>
int a[100][100];

int main(){
  int n, m, i, j, aux;
  scanf ( "%d%d", &n, &m );
  for ( i = 0; i < n; i++ )
    for ( j = 0; j < m; j++ )
      scanf ( "%d", &a[i][j] );      
  
  for ( i = 0; i < n; i++ ){
      // permutam spre stanga linia i
      aux = a[i][0];                // primul element de pe linia i il salvam in aux
      for ( j = 0; j < m - 1; j++ ) // mutam spre dreapta toate celelalte elem de pe linie, incepand cu al doilea elem
        a[i][j]= a[i][j+1];
      a[i][m-1] = aux;              // punem elementul salvat in aux pe ultima pozitie a liniei i
  }

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

LABORATOR

SumaLinii1

Gigel a găsit o matrice cu n linii și m coloane și elemente numere naturale. El își propune să determine, pentru fiecare linie, cea mai mică valoare care se poate obține adunând elementele de pe linie, cu excepția unuia.

#include <stdio.h>

int a[101][101];

int main(){
    int n, m, s, c, l, max;
    
    scanf ( "%d %d", &n, &m);
    
    for ( l = 0 ; l < n ; l++ ){
        s = 0;
        max = a[l][0];
        for ( c = 0 ; c < m ; c++ ){
            scanf ( "%d", &a[l][c] );
            s = s + a[l][c];
            if ( a[l][c] > max ){
                max = a[l][c];
            }
        }
        s  =  s - max;
        printf ( "%d ", s);
    }
    return 0;
}

MaxAp1

Se dă o matrice cu n linii şi m coloane şi elemente numere naturale. Să se determine elementul cu număr maxim de apariții în matrice. Dacă există mai multe elemente cu număr maxim de apariții se va afișa cel mai mare dintre ele.

#include <stdio.h>
#include <stdlib.h>
int v[1000000]; //vectorul de frecventa

int main(){
  int n, m, i, j, x, maxap;
  scanf( "%d%d", &m, &n );
  for( i = 0; i < m; i++ ){
    for( j = 0; j < n; j++ ){
      scanf( "%d", &x );
      v[x]++;
    }
  }
  int val;
  maxap = 0;
  for( i = 0; i < 1000000; i++ )
    if( v[i] >= maxap ){
      maxap = v[i];
      val = i;
  }

  printf("%d", val);

  return 0;
}

OrdLin

Se dă o matrice cu n linii şi m coloane şi elemente numere naturale. Să se ordoneze liniile matricei crescător după suma elementelor.

#include <stdio.h>
#include <stdlib.h>
int a[101][101];

int main(){
  int n, m, i, j, x, minim, poz;

  // citim matricea si calculam suma pe fiecare linie, memorand sumele pe ultima coloana
  scanf( "%d%d", &m, &n );
  for( i = 0;i < m; i++ ){
    a[i][n] = 0;       // aici voi pune suma elementelor de pe linia i
    for( j = 0; j < n; j++ ){
      scanf( "%d", &a[i][j] );
      a[i][n] += a[i][j];
    }
  }
  
  // sortam liniile dupa elementele de pe coloana n cu metoda select sort
  for( i = 0; i < m - 1; i++ ){
    // determinam minimul si pozitia minimului pe coloana n, incepand de la linia i
    minim = a[i][n]; poz = i;
    for( j = i + 1; j < m; j++ )
      if( a[j][n] < minim ){
        minim = a[j][n];
        poz = j;
      }
    // interschimb  linia i cu linia poz ( inclusiv a[i][n] cu a[poz][n])
    int aux;
    for( x = 0; x <= n; x++ ){
      aux = a[poz][x];
      a[poz][x] = a[i][x];
      a[i][x] = aux;
    }
  }
  
  // afisam matricea 
  for( i = 0; i < m; i++ ){
    for( j = 0; j < n; j++ )
      printf( "%d ", a[i][j] );
    printf( "\n" );
  }
  return 0;
}

MChenar

Se dă o matrice cu n linii şi m coloane şi elemente numere naturale. Să se determine mulțimea formată din elementele distincte ale chenarului matricei.

#include <stdio.h>
#include <stdlib.h>
int v[1000000]; //vectorul de frecventa

int main(){
  int n, m, i, j, x;
  scanf( "%d%d", &m, &n );
  for( i = 0; i < m; i++ ){
    for( j = 0; j < n; j++ ){
      scanf( "%d", &x );
      if ( i == 0 || j == 0 || i == m - 1 || j == n - 1 )
        v[x]++;
    }
  }

  for(i = 0; i < 1000000; i++ ){
    if( v[i] > 0 )
      printf("%d ", i );
  }
  return 0;
}

ColEgale

Se dă o matrice cu m linii şi n coloane şi elemente numere naturale cu cel mult 4 cifre fiecare. Să se determine coloanele matricei care au toate elementele egale cu aceeași valoare.

#include <stdio.h>

int a[50][50];

int main(){
  int i, j, n, m, cnt;
  scanf( "%d%d", &n, &m);
  for( i = 0; i < n; i++ )
    for( j = 0; j < m; j++ )
      scanf( "%d", &a[i][j] );

  cnt = 0;
  for( j = 0; j < m; j++ ){
    // cautam pe coloana j un element diferit de primul element al coloanei j
    i = 1;
    while( i < n && a[i][j] == a[0][j] )
      i++;
    // daca nu am gasit un element diferit printam valoarea comuna
    if ( i == n ){
      cnt ++;
      printf("%d ", a[0][j]);
    }
  }
  if (!cnt)
    printf("nu exista");


  return 0;
}

MCautare

Se dă o matrice cu n linii și m coloane și elemente numere naturale și k valori naturale. Determinați pentru fiecare dintre cele k valori dacă apare pe fiecare linie a matricei.

#include <stdio.h>

int a[100][100];

int main(){
  int i, j, n, m, nr, x, cnt, k;

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

  scanf( "%d", &nr );
  for( k = 0; k < nr; k++ ){
    scanf( "%d", &x );
    // numaram pe cate linii apare x
    cnt = 0;
    for ( i = 0; i < m; i++ ){
      j = 0;
      while ( j < n  && a[i][j] != x  )
        j++;
      cnt = cnt + ( j < n );
    }
    // daca x apare pe toate liniile afisam DA altfel afisam NU
    if ( cnt == m )
      printf("DA\n");
    else
      printf("NU\n");
  }
  return 0;
}

_________________________________________________________________________________________________________________________

Citirea unei matrice de caractere fara sa se citeasca in prealabil dimensiunea ei

Sa se citeasca din fisierul "date.in" o matrice de caractere. Fiecare linie de caractere este pe cate un rand al fisierului, iar caracterele nu au spatii intre ele. D Vom citi prima linie a fisierului si vom determina numarul de elemente de pe aceasta, determinand astfel numarul de coloane ale matricei n. Apoi vom citi urmatoarele linii pana la intalnirea sfarsitului de fisier.

// Sol 9 C
#include <stdio.h>

char a[100][100];

int main() {
  FILE *fin, *fout;
  int n, m, l, c;
  char ch;

  fin = fopen( "date.in", "r" );
  // citim intii prima linie pina la '\n', pentru a-l afla pe n=nr. de coloane
  n = 0;
  ch = fgetc( fin );
  while ( ch != '\n' ) {
    a[0][n] = ch;
    n++;
    ch = fgetc( fin );
  }
  
  // citim linie cu linie pana ajungem la o linie goala sau la finalul fisierului(EOF)
  ch = fgetc( fin );
  m = 1; // nr. de linii
  while ( ch != '\n' && ch != EOF ) {
    // Fisierul nu s-a terminat, citim urmatoarea linie:
    for ( c = 0; c < n; c++ ) {
      a[m][c] = ch;
      ch = fgetc( fin );
    }
    m++;
    ch = fgetc( fin );
  }

  // Afisam matricea
  fout = fopen( "date.out", "w" );
  for ( l = 0; l < m; l++ ) {
    for ( c = 0; c < n; c++ )
      fputc( a[l][c], fout );
    fputc( '\n', fout );
  }
  fclose( fout );

  return 0;
}

O implementare similara a solutiei de mai sus presupune citirea tuturor caracterelor pana la sfarsit de fisier. Vom numara elementele pana la intalnirea primului sfarsit de linie, determinand astfel numarul de coloane si vom numara '\n'-rile determinand astfel numarul de linii.

//Sol 9I
#include <stdio.h>

char a[100][100];

int main() {
  FILE *fin, *fout;
  int n, m, l, c,i;
  char ch;

  fin = fopen( "date.in", "r" );
  // citim intii prima linie pina la '\n', pentru a-l afla pe n=nr. de coloane
  i = m = n =  0;//m = nr de linii, m = linii de coloane
  ch = fgetc( fin );
  while (ch != EOF ) {
    if(ch == '\n'){
        if(m == 0)
            n = i;
        m++;
        i = 0;
    }
    else{
        a[m][i] = ch;
        i++;
    }
    ch = fgetc(fin);
  }

  // Afisam matricea
  fout = fopen( "date.out", "w" );
  for ( l = 0; l < m; l++ ) {
    for ( c = 0; c < n; c++ )
      fputc( a[l][c], fout );
    fputc( '\n', fout );
  }
  fclose( fout );

  return 0;
}

O alta solutie ar fi sa retinem toate elementele intr-un vector, determinand numarul de linii in functie de numarul de '\n' uri, iar numarul de coloane il putem determina pe baza numarului de linii si al numarului total de elemente trasnferate in vector. La final vom afisa elementele vectorului sub forma unei matrice, tiparind cate n elemente pe fiecare rand.

#include <stdio.h>

char a[100*100];

int main() {
  FILE *fin, *fout;
  int n, m, l, c, j;
  char ch;

  fin = fopen( "date.in", "r" );
  // Construim un vector cu toate elementele matricei
  m = j = 0;        //m = nr de linii, j = numarul de elemente citite
  ch = fgetc( fin );
  while (ch != EOF ) {
    if( ch == '\n' )
        m++;
    else
        a[j++] = ch;
    ch = fgetc(fin);
  }
  
  n = j / m;        // n = nr de coloane = nr de elemente citite / nr de linii
  
  // Afisam matricea
  fout = fopen( "date.out", "w" );
  for ( l = 0; l < m; l++ ) {
    for ( c = 0; c < n; c++ )
      fputc( a[l*n+c], fout );
    fputc( '\n', fout );
  }
  fclose( fout );

  return 0;
}

Sarcina Laborator:

• Cititi o matrice de numere naturale fara sa se cunoasca dimensiunea acestea
• Cititi o matrice de numere intregi fara sa se cunoasca dimensiunea acesteia

Tema

Tema Teorie

Rezolvati urmatoarele probleme de pe pbinfo.ro

SumaPare2

Se dă o matrice cu n linii şi m coloane şi elemente numere naturale. Determinați suma valorilor pare din matrice.

SumaLinii

Se dă o matrice cu n linii și m coloane și elemente numere naturale. Să se determine suma elementelor de pe fiecare linie.

NrPrime

Se dă o matrice cu n linii și m coloane și elemente numere naturale. Să se determine câte dintre elementele situate pe linii cu indici pari sunt prime.

SumaPare3

Se dă o matrice cu n linii şi m coloane şi elemente numere naturale. Determinați suma valorilor pare distincte din matrice. Dacă o valoare pară apare în matrice de mai multe ori, se va aduna o singură dată.

MaxAp

Se dă o matrice cu n linii şi m coloane şi elemente numere naturale. Să se determine elementul cu număr maxim de apariții în matrice. Dacă există mai multe elemente cu număr maxim de apariții se vor afișa toate, în ordine crescătoare.

Tema Laborator pbinfo

Max2Ap

Se dă o matrice cu n linii şi m coloane şi elemente numere naturale. Să se determine cea mai mare valoare care apare în matrice de cel puțin două ori.

CntLinii

Se dă o matrice cu n linii şi m coloane şi elemente numere naturale. Să se determine câte linii ale matricei au toate elementele egale.

CntColoane

Se dă o matrice cu n linii şi m coloane şi elemente numere naturale. Să se determine câte coloane ale matricei au elementele distincte două câte două.

OrdCol

Se dă o matrice cu n linii şi m coloane şi elemente numere naturale. Să se ordoneze coloanele matricei astfel încât elementele de pe prima linie să fie ordonate crescător.

SumElPare

Se dă o matrice cu n linii și m coloane și elemente numere naturale. Să se determine indicele liniei pentru care suma elementelor pare este maximă.

NrPare

Se dă o matrice cu n linii şi m coloane şi elemente numere naturale. Determinați indicele liniei care conține număr maxim de elemente pare. Dacă există mai multe linii cu număr maxim de elemente pare, se vor afișa toți indicii, în ordine crescătoare.

Matrice7

Se consideră o matrice cu n linii şi m coloane şi elemente numere naturale. Să se modifice matricea în felul următor: toate elementele egale cu valoarea maximă din matrice se înlocuiesc cu valoarea minimă de pe coloana lor.

Probleme de pe varena

• zoomx2 - generare matrice pe baza unei matrice date
• căutare - cautare submatrice in matrice
• patrate1