Tablouri bidimensionale (matrice)

Definitie: Un tablou bidimensional (o matrice) reprezinta o colectie de elemente de acelasi tip, dispuse de linii si coloane.

Pozitia este data printr-o suita de numere pozitive (indecsi), care reprezinta cele doua dimensiuni (linie si coloana).

Tabloul are un numar bine determinat de elemente si se identifica printr-un singur nume.

Valorile atribuite elementelor tabloului trebuie sa fie de acelasi tip.

Descriere generala

Sintaxa de declarare a unei matrice este: tip nume[m][n], unde:

* tip – tipul de data folosit; poate fi unul din tipurile de baza (int, float, char, …) sau

un tip definit de utilizator (articole, obiecte)

* nume – numele prin care va fi referita matricea

* m – numarul de linii din matrice

* n- numarul de coloane din matrice

Matricele pot fi:

Dreptunghiulare (in care numarul de coloane difera fata de numarul de linii); Patratice (in care numarul de coloane este egal cu numarul de linii).

Matrice patratica

Se citeste un tablou cu n linii si n coloane, numere intregi. Un astfel de tablou, in care numarul liniilor este egal cu numarul coloanelor, poarta denumirea de matrice patratica. O matrice patratica are doua diagonale: principala si secundara. Pentru un tablou patratic A, numim diagonala principala, elementele aflate pe “linia” care uneste A[1][1] cu A[n][n]. Pentru un tablou patratic A, numim diagonala secundara, elementele aflate pe “linia” care uneste A[n][1] cu A[1][n]

A11A12A13A14

A21A22A23A24

A31A32A33A34

A41A42A43A44

Zone speciale in matrice patratice Diagonala principala si secundara

Diagonala principală Diagonala principală este formată din elementele care îndeplinesc relațiai = j – numărul liniei este egal cu numărul coloanei pe care se află.

Diagonala secundară

Diagonala secundară conţine elementele a1n, a2 n-1 , a3 n-2,...,an1 caracterizate de relaţia i+j = n+1.

Zona de deasupra diagonalei principale Elementele de deasupra diagonalei principale sunt a12, a13, a14,...,a1n, a23, a24, a25,...,a2n, ...., an-1 n-1, an-1 n. Relaţia dintre coordonate comună tuturor elementelor din această zonă este i < j .

Zona de sub diagonala principală Elementele a21, a31, a32,...,a41, a42, a43, .....,an1, an2, an n-1 se află sub diagonala principală şi au între coordonate relaţia i > j.

În practică prelucrarea elementelor se poate face exclusiv pe diagonale respectiv pe zonele identificate mai sus(ex:ordonarea diagonalelor respectiv verificarea simetriei sau a triunghiularităţii) sau se poate opta pentruo parcurgere a tuturor elementelor matricei şi prelucrarea diferenţiată a elementelor în funcţie de relaţia dintre coordonate(ex: completarea elementelor cu anumite valori, calculul simultan al mai multor rezultate obţinute pentru fiecare zonă în parte).

Modalităţi de prelucrare a elementelor în matrice pătratică de dimensiune n

Diagonala principala:for (i=1;i<=n;i++)<prelucrează a[i][i]>

Diagonala secundara:for (i=1;i<=n;i++)<prelucrează a[i][n-i+1]>

Deasupra diagonalei principale:for (i=1;i<=n-1;i++)for(j=i+1;j<=n;j++)<prelucrează a[i][j]>

Sub diagonala principala:for (i=2;i<=n;i++)for(j=1;j<=i-1;j++)<prelucrează a[i][j]>

Prelucrarea intr-o singura parcurgere a tuturor zonelor:for (i=1;i<=n;i++)for(j=1;j<=n;j++)if (i==j)*<prelucrează a[i,j] – diag. princ.>elseif (i+j==n+1)*<prelucrează a[i,j] – diag. sec.>elseif (i>j)*<prelucrează a[i,j] – deasupra diag. princ.>else*<prelucrează a[i,j] – sub diag. princ.>if (i+j<n+1)*<prelucrează a[i,j] – deasupra diag. sec.>if (i+j>n+1)*<prelucrează a[i,j] – sub diag. sec.

Zona Nordica : deasupra diagonalei principale si deasupra diagonalei secundare;i<j si i+j<n+1

Zona Sudica : sub diagonala principala si sub diagonala secundara;i>j si i+j>n+1

Zona Vestica : sub diagonala princiapala si deasupra diagonalei secundare;i>j si i+j<n+1

Zona Estica : deasupra diagonalei principale si sub diagonala secundara;i<j si i+j>n+1Declararea unei variabile de tip matrice

tip_tablou nume_tablou [dimensiune_tablou] [dimensiune_tablou];

Exemplu: întreg a[20][20];

a

1 2 3 4 5

1 5 3 12 9 25

2 3 20 4 2 9

3 6 5 6 13

4

4 8 9 11 3 8

5 14

16 2 6 4

Poziţie

Deoarece elementele unui matrice sunt memorate în ordine pentru a ne referi la un element al matricii putem specifica numele matricii din care face parte şi poziţia sa în matrice, prin număr liniei şi a coloanei sale

Exemplu: Primul element este a[1][1], al treilea element este a[1][3].

Pseudocodul pentru declararea unei matrici

1.Sectiunea TYPE

TYPE matrice=array[1..n,1..n]of tip de date;Var varmatrice:matrice;I,j,n,m:integer; Ex:TYPE matrice=array[1..20,1..25]of integer;Var A:matrice;I,j,m,n:integer;

2.Sectiunea VARVAR varmatrice=array[1..n,1..n]of tip de date;Ex:var A:array[1..20,1..24]of real;I,j,m,n:integer;

Citirea unei matrici

Pentru a citi o matrice înainte de toate, trebuie să citim dimensiunile matricii, dimensiunile în general se notează cu n şi m, şi reprezintă numărul de linii şi de coloane din matrice. Citirea elementelor unui tablou nu este posibila decat prin citirea fiecarui element. De aceea, la fel ca si in cazul vectorilor, operatia de citire a matricelor impune folosirea a doua secvente ciclice suprapuse. Acestea corespund indicelor liniei (i), respectiv coloanei (j). De multe ori nu ştim câte linii şi câte coloane va trebui să aibă tabloul. În acest caz , tabloul se declară cu un număr maxim de linii şi un număr maxim de coloane, în aşa fel încât acesta să corespundă oricărui set de date de intrare. Evident , într-un astfel de caz există o risipă de memorie internă.

Citeşte n,m;

Elementele unei matrici se citesc pe rând folosind două structuri pentru imbricate(una în cealaltă).

Pentru i=1 la n execută

Pentru j=1, m execută

Citeşte a[i][j];

Sfârşit_pentru;

Sfârşit_pentru;

Afişarea unei matrici Pentru a afişa elementele unei matrici se parcurge matricea în 2 structuri pentru şi se

afişează fiecare element.

Pentru i=1 la n execută

Pentru j=1 la m execută

scrie a[i][j];

Sfârşit_pentru;

Sfârşit_pentru;

Problema : Se citesc de la tastatura elementele reale ale unei matrici cu n linii si m coloane. Sa se afiseze matricea.

var a:array[1..100,1..100] of real;n,m,i,j:byte;begin {citire datele de intrare: numarul de linii, numarul de coloane si elementele matricii}write(‘numarul de linii=’);readln(n);write(‘numarul de coloane=’);readln(m);for i:=1 to n dofor i:=1 to m dobeginwrite(‘a[‘,i,’,’,j,’]=’);readln(a[i,j]);end;{afisam elementele matricii}for i:=1 to n do begin {afisam o linie}for j:=1to m dowrite(a[i,j]:5:2,’’);writeln{trecem la linie noua pentru a da forma de matrice datelor afisate}end;end.

Căutarea unui element într-o matrice.Pasul 1. Se citeşte matricea

Pasul 2. Se citeşte elementul căutat

Pasul 3. Se parcurge matricea şi se compară elementul căutat cu toate elementele matricii, dacă a fost găsit unei variabile „găsit” îi atribuim valoare de adevăr, şi afisăm „poz” poziţia elementului în vector.

Pasul 4. Dacă variabila găsit este falsă atunci afişăm un mesaj,”nu este în matrice .

Sortarea elementelor unei linii dintr-o matrice dupa o anumita regula

1.Ordonarea unui sir - Metoda "bulelor" (Bubble Sort)

            Se citeste un sir de numere intregi si se cere sa se ordoneze elementele acestui sir crescator

A: 7 , 4 , 5 , 3 , 9 , 1    (inainte)

A: 1 , 3 , 4 , 5 , 7 , 9     (dupa)

Ideea care sta la baza acestei metode este urmatoarea: se parcurge sirul, comparandu-se elementele consecutive din sir doua cate doua. Daca acestea nu sant in relatia dorita ("³" sau "£") se schimba valorile elemntelor.

Printr-o parcurgere a sirului si efectuarea comparatiilor obtinem: 

 Comparam  A[i] > A[i+1]   daca da, le schimb

Se observa ca, dupa o parcurgere a vectorului, sirul obtinut nu este ordonat deci este necesara reluarea procedeului descris anterior.

Daca vectorul contine elemente deja ordonate se face o singura parcurgere. La efectuarea unei interschimbari se marcheaza aceasta operatie prin valoarea "FALSE" a unei variabile logice care, inainte de parcurgere va avea valoarea "TRUE". La sfarsitul algoritmului valoarea acestei variabile va fi "TRUE" , pentru ca nu va mai fi necesara nici o interschimbare.

PROGRAM BULE;

TYPE

vector = ARRAY[1..100] OF integer;

VAR

 a : vector;

 n , i , aux : integer;

 ordonat : boolean;

BEGIN

Write ('nr de componente= ');readln(n);

FOR i := 1 TO n DO BEGIN

                               write ('a[', i ,']= ');

                                    readln( a[i] );

                                    END;

FOR i := 1 TO n DO

                               write (a[ i ],' ');

writeln;

REPEAT

ordonat := true;

FOR i := 1 TO n-1 DO

IF a[i] > a[i+1] THEN  BEGIN

aux := a[i];

a[i] := a[i+1];

a[i+1] := aux;

ordonat := false;

END;

UNTIL ordonat = true;

FOR i := 1 TO n DO                              

write (a[ i ], ' ');

writeln;

END.

2. Metoda de sortare prin INSERTIE

Consta in inserarea fiecarui element al vectorului la locul corespunzator in raport cu elementele sortate anterior. Principiul de baza al algoritmului de sortare prin insertie este urmatorul:

Se presupune ca subsecventa a[1], a[2], . , a[i-1] este sortata; Se cauta in aceasta subsecventa locul j al elementului a[i] si se insereaza a[i] pe pozitia j. Sa vedem cum se determina pozitia j (finala in vectorul sortat):

-  j = 1 daca a[i] < a[1]

-  1 < j < i si sunt satisfacute relatiile a[j-1] <= a[i] < a[j]

-  j = i daca a[i] >= a[i-1]

Determinarea lui j se face prin cautare secventiala sau prin cautare binara. Putem observa ca aceasta tehnica de sortare se bazeaza pe metoda " jucatorului de bridge".

Implementare: Consideram cazul cand pozitia j este determinata prin cautare secvetiala (de la dreapta la stanga) simultan cu deplasarea elementelor mai mari ca a[i] cu o pozitie la dreapta. Aceasta deplasare se realizeaza prin interschimbari astfel incat valoarea a[i] realizeaza o deplasare la stanga pana ajunge la locul ei final.

PROGRAM Sort_Ins;

VAR a:array[1..50] of integer;

         n, i, j, k, aux: integer;

BEGIN

Write('cate elem are vectorul: '); readln(n);

Writeln('Introduceti elem:');

FOR i := 1 TO n DO BEGIN

                                      Write('a[', i ,']= '); Readln(a[i]);

                                     END;

FOR i := 2 TO n DO begin

                                       j := i - 1;

                                       aux := a[i];

                                       WHILE (j>=1) AND (a[j]>aux) DO j := j - 1;

                                       FOR k := i  DOWNTO j+1 DO a[k] := a[k-1];

                                       a[j+1] := aux;

                                    end;

FOR i :=1 TO n DO write(a[i],' '); END.                           

3. Metoda de sortare prin SELECTIE

Consta in determinarea elementului minim si aducerea lui pe prima pozitie; apoi dintre elementele ramase in vector, se determina minimul si va fi adus pe a 2-a pozitie, s.a.m.d. pana cand toate elementele vor fi asezate in ordine.

Implementare: Vectorul se parcurge de la prima pozitie pana la pozitia n-1; se compara fiecare element de la pozitia 1 pana la pozitia n-1 cu elementele aflate dupa el. Daca elementele nu sunt in ordinea corecta, se efectueaza interschimbarea acestora, astfel incat minimul se determina comparand un element cu toate elementele care ii succed.

Algoritmul Sort_Sel;

FOR i := 1 TO n-1 DO

 FOR j := i+1 TO n DO

             IF a[i] > a[j] THEN begin

                                                aux := a[i];

                                                a[i] := a[j];

                                                a[j] := aux;

                                                end;

4. Metoda de sortare prin NUMARARE

Fie vectorul a = (a1, a2, . , an).

Pentru fiecare element se numara cate elemente sunt mai mici decat el. Numerele pe care le obtinem se vor memora intr-un vector k = (k1, k2, . , kn).

Pentru a obtine elementele sortate, pe baza elementelor vectorului k, vom rearanja elementele vectorului a intr-un vector b = (b1, b2, . , bn), unde b[k[i]+1] = a[i].

EX:

N=5, a=(7, 6, 3, 8, 0)

Initial: k = (0, 0, 0, 0, 0)

Iterativ: k = (3, 2, 1, 4, 0)     k = (0, 3, 6, 7, 8)

Procedeul: Pentru fiecare element incepand de la pozitia 2, se compara valoarea acestuia cu valorile aflate in vectorul a, inaintea sa. Daca elementul curent este mai mic decat un anumit element aflat inaintea sa, atunci se contorizeaza numarul de elemente mai mici pentru

elementul care este mai mare, marindu-se cu o unitate acest contor; in caz contrar acesta se modifica pentru numarul curent.

Algoritmul Sort_Number;

FOR  i := 1 TO n DO k[i] := 0;

 For i := 2 TO n DO

         FOR j := 1 To i-1 DO  

              IF a[i] < a[j] THEN k[j] := k[j]+1

                                         ELSE k[i] := k[i]+1;

FOR i :=1 TO n DO b[k[i]+1] := a[i];

FOR i := 1 TO n DO write (b[i],' ');

Problema: Se citesc de la tastatura elementele reale ale unei matrice cu n linii si m coloane. Sa se afiseze transpusa matricii.

var a:array[1..100,1..100]of real;n,m,i,j:byte;begin{citirea datelor de intrare}write(‘numarul de linii=’);readln(n);write(‘numarul de coloane=’);readln(m);for i:=1 to n dofor j:=1 to m do

beginwrite(‘a[‘,i,’’,j,’]=’);readln(a[i,j]);end;{afisarea transpusei}for j:=1 to m beginfor i:=1 to n do write(a[i,j]:5:2,’’);writeln;end;end.

Problema: Se da o matrice patratica. Sa se realizeze un program care sa afiseze suma elementelor negative din matrice.

program matrice;var x:array[1..100,1..100] of integer;n,i,j,s:integer;beginwrite('n='); readln(n);for i:=1 to n dofor j:=1 to n dobeginwrite('x[',i,',',j,']=');readln(x[i,j]);end;s:=0;for i:=1 to n dofor j:=1 to n doif x[i,j]<0 then s:=s+x[i,j];writeln('Suma elementelor negative din matrice este: ',s);end.

Poiect tablouri bidimensionaleinformatica

Lita Denisa-Elena

Paiu Georgiana

Andrei Ralucaclasa a X-a C