Tabele bidimensionale

Tabele bidimensionale
Fie că e necesar de determinat în ce zi şi la care oră a fost cea mai înaltă temperatură a anului. Cu aceast scop se poate declara un tablou cu 8760 (24*365) elemente , câte un element pentru fiecare oră a anului.
Type
Ore_an = array [1..8760] of integer
Var
Temp: Ore_an
Dacă există un tablou pentru toate orele anului, atunci temperatura maximă poate fi determinată aplicând algoritmul de căutare a elementului maxim în tablou. Şi dacă temperatura maximă a fost înregistrată în ora 4568, atunci apare problema cum să determinăm luna şi ziua. Evident , sunt necesare anumite calcule. Dar există şi altă rezolvare. În limbajele de programare se folosesc tabele multidimensionale.
Tabelul multidimensional este un tablou elementele căruia sunt de tip tablou.
De exemplu tabloul LunaTemp poate fi declarat ca tablou cu 31 elemene care conţin temperaturile fiecărei ore a zilei:
LunaTemp :array [1..31] of array [0..23] of integer

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
1
2
.
.
30
31
În mod analog poate fi declarat tabloul AnTemp:
AnTemp :array[1..12] of array [1..31] of array[0..23] of integer
Sau
AnTemp: array[1..12], [1.31], [0..23] of integer
Pentru a identifica un element a acestui tablou e necesar de indicat indecele fiecărei dimensiuni.
Pentru identificarea unui element a tabloului Temp se indică un indice (valoarea orei) Temp[100];
Pentru identificarea unui erlement a tabloului LunaTemp se arată doi indici (ziua,ora) LunaTemp[2,14] (temperatura la orele 14 în ziua 2 a lunii).
Pentru identificarea unui element a tabloului AnTemp se arată trei indici (luna, ziua,ora) AnTemp[5,18,10] (temperatura la 18 mai ora 10)
Declaraţia generală a unui tablou bidimensional este:
Type
Nume_tip = array [tip_indice1,tip_indice2] of tip_element
Var
Variabila_tablou : nume_tip
Un tablou bidimensional se mai numeşte şi matrice, conform noţiunii din matematică.
Un element al tabloului bidimensional se specifică prin intermediul numelui variabilei şi a valorilor indicelor elementului respectiv, sub forma:
Variabila_tablou[indice1,indice2],
unde indice1,indice2 conţin câte o expresie pentru fiecare indice, având tipuri compatibile cu cele ale tipului declarat. Corectitudinea valorilor indicilor este verificată pe parcursul executării programului. Dacă valoarile indice1,indice2 nu corespund tipurilor declarate, atunci se cauzează eroare de depăşire a domeniului de valori (eroare run_time).
Exemple:
1. Type
luna=(martie,apr,mai)
tablou=array[1..5,luna] of integer
Var
X: tablou
În acest exemplu primul indice este de tip interval [1..5], iar al doilea de tip enumerare. Tabelul va avea 5 rânduri, numerotate de la 1 până la 5 şi 3 coloane (deoarece tipul celui de-al doilea indice are numai trei valori).
Expresia X[2,martie] - specifică primul element din rândul dou;
X[5,mai] - specifică ultimul element din ultimul rând
X[3,dec] - specifică eroare, deoarece valoare celui de-al doilea indice nu aparţine tipului luna. .
Tablou[2,martie] – specifică eroare sintactică, deoarece tablou nu este nume de variabilă ci nume de tip;
X[2,apr]:=13 - atribuie elementului din rândul doi, coloana a doua valoarea 13;
X[2,apr]:=false - cauzează eroare sintactică, deoarece tipul elementului ( este integer) nu corespunde cu tipul expresiei (este boolean].
2. Type
Tablou = array[boulean,boulean] of boulean
Var
Y: tablou
În acest caz se declară un tablou bidimensional cu două rânduri (deoarece primul indice este de tip boolean ,care are numai două valori: false,true) şi două colane.
Expresia Y[false,false]:=false atribuie valoarea false elementului din primul rând şi din prima coloană.
3. Să presupunem că vrem să elaborăm programul orarului de activităţi pentru elevii din clasa 1. Cu acest scop vom defini o matrice în care, pe coloane vom avea zilele săptămânii, iar pe linii orele de lucru. În celula care se formează la intersecţia liniei cu coloana va fi un şir de caractere care reprezintă disciplina de învăţământ.
Type
Orar=array[1..4,1..5] of string
Var
Orarul_meu: orar
Putem, de asemenea să declarăm direct:
Var
Orarul_meu: array[1..4,1..5] of string.
Elementul Orarul_meu[2,3] reprezinta ziua de miercuri, lecţia 2.
Dar, pentru a fi mai sugestivi, am putea face declaraţii de genul:
Type
Zi_de_scoala=(luni,marti,miercuri,joi,vineri)
Orar: array[1..4,zi_de scoala] of string
Var
Orarul_meu:orar
Elementul Orarul_meu[2,miercuri] reprezinta ziua de miercuri, lecţia 2.
4. Să definim o matrice pentru o tablă de şah; piesele vor fi codificate: -1 pion negru, 1- pion alb, -2- cal negru, 2 – cal alb, ş.a.m.d., iar 0 pentru poziţiile neocupate.
Type
Tabla_de_sah=array[‘a’..’h’, 1..8’] of integer

5. Să presupunem că avem un grup de n băieţi şi n fete care sunt prietene cu cei n băieţi.
Vom memora aceasta sub forma unei matrice patratice (are numărul de coloane egal cu cel de linii):
Type
Matrice=array[1..n, 1..n] of boolean
Var
X:matrice
Vom avea X[i,j]=true dacă băiatul i este prieten cu fata j, respectiv false, dacă nu.
Noţiunea de prietenie este simetrică: dacă băiatul j este prieten cu fata i, atunci şi fata i este prietenă cu băiatul j. Matricea X va fi simetrică: X[i,j]=X[j,i].
Parcurgerea matricei
Considerăm declaraţia:
A :array[1..n,1..m] of integer;
Se declară un tablou cu două dimensiuni - un tablou bidimensional, care declară o matrice, formată din n linii şi m coloane:
A11 A12 … A1m
A21 A22 … A2m
…
An1 An2 … Anm
În memoria operativă elementele matriciei se alocă în felul următor:
A11, A12, … A1m, A21, A22, … A2n, … An1 , An2 … An
Elementele unui tablou bidimensional pot fi accesate secvenţial prin două metode:
1) pe rânduri;
2) pe coloane.
Pentru a parcurge toate elementele unei matrice este necesar ca cei doi indici care selectează un element din matrice să primească toate combinaţiile posibile. În acest scop trebuie să se efectuieze două cicluri incluse unul în altul.
Prelucrarea secvenţială pe rânduri se organizează cu ajutorul următorului algoritm:
Var
I:integer ;indicele rândului
J:integer ;indicele coloanei
Begin
For i:=1 to n step 1 do
For j:=1 to m step 1 do
{prelucrarea elementului A[i,j]}
endfor
endfor
Primul ciclu (după i) organizează prelucrarea a n rânduri a matricei. Corpul ciclului realizează prelucrarea unui rând. Deoarece rândul este compus din m elemente, se organizează un ciclu (după j), care prelucrează toate elementele rândului.
Pentru o valoare a variabilei i variabila j parcurge toate elementele posibile. Adică se va parcurge tot rândul respectiv.

Prelucrarea secvenţială pe coloane se organizează cu ajutorul următorului algoritm:
Var
I:integer ;indicele rândului
J:integer ;indicele coloanei
Begin
For j:=1 to m step 1 do
For i:=1 to n step 1 do
{prelucrarea elementului A[i,j]}
endfor
endfor

Citirea unei matrice


1. Să se citească de la tastatură un tabel bidimensional pe rânduri:
For i:=1 to n step 1 do
WriteString(‘Introdu rândul’
WriteInt(i)
For j:=1 to m step 1 do
ReadInt A[i,j]
Endfor
Writeln
Endfor
2. Să se citească de la tastatură un tabel bidimensional pe coloane:
For j:=1 to m step 1 do
WriteString(‘Introdu coloana’)
WriteInt(j)
For i:=1 to n step 1 do
ReadInt A[i,j]
Endfor
Endfor

Afişarea unei matrice

Să se afişeze un tabel bidimensional pe rânduri:

For i:=1 to n step 1 do
For j:=1 to m step 1 do
WriteInt A[i,j]
Endfor
Writeln
endfor

Însumarea componentelor unei matrice

1. Să se calculeze suma elementelor unui tabel bidimensional.

Se pleacă de la suma nulă. Apoi, folosind algoritmul de parcurgere secvenţială a elementelor maticei, suma creşte cu elementul curent, care este A[i,j],
unde i – indecele rândului, iar j – indecele coloanei.

S:=0
For i:=1 to n step 1 do
For j:=1 to m step 1 do
S:=S+ A[i,j]
Endfor
Endfor

3. Să se determine suma elementelor rândului k a unui tabel bidimensional
Elementele rândului k au primul indice constant, iar cel de-al doilea indice se schimbă de la 1.. m. Se va folosi un ciclu care se repetă de m ori care va accesa pe rând toate elementele rândului k.
S:=0
For j:=1 to m step 1 do
S:=S+A[k,j]
Endfor

Numărarea elementelor matricei, care verifică o anumită condiţie

Să se calculeze câte elemente impare conţine un tabel bidimensional.

Să notăm prin N_impar numărul elementelor impare. Iniţial ea se comportă caun contor nul. Parcurgând secvenţial elementele matricei, de fiecare dată când găsim în matrice un element impar (A[i,j] mod 2 #0) se incrementează contorul N_impar.
N_impar:=0
For i:=1 to n step 1 do
For j:=1 to m step 1 do
If A[i,j] mod 2 # 0 then
N_impar:=N_impar+1
endif
Endfor
Endfor


Determinarea existenţei în matrice a elementelor care au o anumită proprietate

Să se determine dacă matricea A conţine vre-un element nul.

Trebuie să se determine primul element nul. În cel mai nefavorabil caz ( când elementul din ultimul rând şi ultima coloană este nul sau nu există nici un element nul) se vor examina toate elementele matricei. Se va folosi o variabilă logică, de exemplu conţine. Iniţial acestei variabile i se atribuie valoarea false. Dacă elementul analizat va fi egal cu zero, atunci această variabilă va primi valoarea true şi se va termina parcurgerea matricei. Deci parcurgerea matricei va avea loc până când mai sunt elemente în matrice (i<=n şi j<=m) şi nu s-a găsit un element nul (not contine). Cu acest scop vom folosi ciclul While.

I:=1 se începe cu primul rând;
Contine := false;
While (i <=n) and not contine do
; prelucrarea unui rând
j:=1 se începe cu primul element al rândului;
while (j<=m) and not contine do
if a[i,j]=0 then
contine=true
endif
j:=j+1
enddo
i:=i+1
enddo