Bella: /* Tema Laborator */

2020-05-12T13:04:00Z

Tema Laborator

New page

= 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:
<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", &n, &m );
for ( i = 0; i < n; i++ )
for ( j = 0; j < m; 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. Vom afisa linie cu linie, pentru fiecare linie, afisam elementele de pe acea linie si un sfarsit de linie.
<syntaxhighlight>
for ( i = 0; i < n; i++ ) {
for ( j = 0; j < m; j++ )
fprintf( fout, "%d ", a[i][j] );
fprintf( fout, "\n" );
}</syntaxhighlight>

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

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

Un algoritm echivalent este acela de a parcurge matricea coloane cu coloana:
<syntaxhighlight>
s = 0;
for ( j = 0; j < m; j++ )
for ( i = 0; i < n; i++ )
s += a[i][j];
}</syntaxhighlight>

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

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

=== 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. [https://www.pbinfo.ro/?pagina=probleme&id=770 PermCol]

<syntaxhighlight>
#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;
}
</syntaxhighlight>

== LABORATOR ==
==== [https://www.pbinfo.ro/?pagina=probleme&id=659 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.
<syntaxhighlight>
#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;
}
</syntaxhighlight>

==== [https://www.pbinfo.ro/?pagina=probleme&id=773 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.
<syntaxhighlight>
#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;
}
</syntaxhighlight>

====[https://www.pbinfo.ro/?pagina=probleme&id=771 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.

<syntaxhighlight>
#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;
}
</syntaxhighlight>
==== [https://www.pbinfo.ro/?pagina=probleme&id=778 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.
<syntaxhighlight>
#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;
}
</syntaxhighlight>

==== [https://www.pbinfo.ro/?pagina=probleme&id=804 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.
<syntaxhighlight>
#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;
}
</syntaxhighlight>

==== [https://www.pbinfo.ro/?pagina=probleme&id=751 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.
<syntaxhighlight>#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;
}
</syntaxhighlight>
_________________________________________________________________________________________________________________________

==== 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.
<syntaxhighlight>
// 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;
}

</syntaxhighlight>
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.

<syntaxhighlight>
//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;
}
</syntaxhighlight>

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.
<syntaxhighlight>
#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;
}
</syntaxhighlight>

'''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
==== [https://www.pbinfo.ro/?pagina=probleme&id=767 SumaPare2] ====
Se dă o matrice cu n linii şi m coloane şi elemente numere naturale. Determinați suma valorilor pare din matrice.
<syntaxhighlight></syntaxhighlight>

==== [https://www.pbinfo.ro/?pagina=probleme&id=658 SumaLinii] ====
Se dă o matrice cu n linii și m coloane și elemente numere naturale. Să se determine suma elementelor de pe fiecare linie.
<syntaxhighlight></syntaxhighlight>

==== [https://www.pbinfo.ro/?pagina=probleme&id=666 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.
<syntaxhighlight></syntaxhighlight>

==== [https://www.pbinfo.ro/?pagina=probleme&id=768 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ă.
<syntaxhighlight></syntaxhighlight>

====[https://www.pbinfo.ro/?pagina=probleme&id=771 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.
<syntaxhighlight></syntaxhighlight>
== Tema Laborator pbinfo ==

==== [https://www.pbinfo.ro/?pagina=probleme&id=789 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.
<syntaxhighlight></syntaxhighlight>

====[https://www.pbinfo.ro/?pagina=probleme&id=776 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.
<syntaxhighlight></syntaxhighlight>

====[https://www.pbinfo.ro/?pagina=probleme&id=777 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ă.
<syntaxhighlight></syntaxhighlight>

==== [https://www.pbinfo.ro/?pagina=probleme&id=769 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.
<syntaxhighlight>
</syntaxhighlight>

==== [https://www.pbinfo.ro/?pagina=probleme&id=662 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ă.
<syntaxhighlight></syntaxhighlight>

==== [https://www.pbinfo.ro/?pagina=probleme&id=766 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.
<syntaxhighlight></syntaxhighlight>

====[https://www.pbinfo.ro/?pagina=probleme&id=1007 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.
<syntaxhighlight></syntaxhighlight>
== Probleme de pe varena ==
* [http://varena.ro/problema/zoomx2 zoomx2] - generare matrice pe baza unei matrice date
* [http://varena.ro/problema/cautare căutare] - cautare submatrice in matrice
* [http://varena.ro/problema/patrate1 patrate1]

Clasa a IX-a lecția 29 - Revision history

Bella: /* Tema Laborator */