Limbaje de programare Material de predare Domeniul: Informatică Calificarea: Analist programator Nivel 3 avansat

Tema 9: Tablouri unidimensionale (Vectori)

Fişa suport 9 - Tablouri unidimensionale

Definiţie:

Un şir de elemente de acelaşi tip, în care contează ordinea elementelor, se numeşte vector sau tablou unidimensional.

Un tablou (array) constă dintr-o succesiune de elemente, aflate într-o anumită ordine, având toate acelaşi tip. Elementele pot fi identificate prin indici care sunt obligatoriu tipuri ordinale.
Acces la componentele vectorului – referirea la elementele unui vector se face printr-o variabila cu indici. O variabila cu indici se compune din numele vectorului urmat de valorile indicelui, fiecare indice fiind reprezentat printr-o expresie inclusa intre paranteze pătrate.
Sintaxa declarării tipului tablou este

în Turbo Pascal type_nume = array [tip_ordinal1,......tip_ordinal n] of tip_oarecare unde: n - reprezintă dimensiunea tabloului tip_ordinal 1,... tip_ordinal n reprezintă tipul indicilor tabloului tip_oarecare reprezintă tipul componentelor tabloului Exemplu: type vector=array[1..100] of integer; var v:vector; variabila v este un tablou de dimensiune 1 cu 100 componente întregi identificate prin indici din subdomeniul 1..100

în Java tip dată [ ] nume_array Exemplu ad [0]=99.99; //accesarea primului element ad [4]=0.001; // accesarea elementului 4 for (int=0; i

Operaţii specifice

- citirea unui vector

Aceasta înseamnă citirea numărului n de componente, într-un ciclu for, de pildă. De fapt avem de citit componenta numărului i, cu i de la 1 la n. Deci putem scrie:

- Exemplu în Turbo Pascal for i:= 1 to n do begin write('daţi x[',x,']='); readln(x[i]); end;

- Exemplu în C++ double a[5]; int i; for (i=0; i<5; i++) { cout<<”a["< cin>>a[i]; //citirea valorii elementului de indice I }

- Scrierea unui vector

Când trebuie sa afişăm vectorul, adică toate componentele sale efective numărul acestora este cunoscut. Afişarea se realizează ciclic şi poate fi astfel:

• 
  fiecare element pe un rând (folosită mai ales când avem vectori şi şiruri de caractere)
  

Exemplu în Turbo Pascal

for i:=1 to n do

writeln(x[i]);

- Parcurgerea unui vector presupune "vizualizarea" tuturor elementelor pe rând şi prelucrare acestora. Parcurgerea într-un ciclu a poziţiilor elementelor din vector i=1,2,3,...,n şi pentru fiecare valoare a lui i, "vizităm" şi prelucrăm elementul v[i], adică elementul aflat pe poziţia i.

- Numărarea elementelor negative şi a celor pozitive dintr-un vector de numere.

Exemplu în Turbo Pascal

Fie NN Si NP cele două numere. Acestea se comportă ca două contoare, iniţial nule. De fiecare dată când găsim în şirul de numere un element negativ se incrementează NN.

NN:=NN+1,altfel NP

NN=0;NP=0;

for i:=1to n do

if x[i]<0 then inc(NN)

else inc(NP);

writeln('Exista',NN,'elemente negative');

writeln('Exista,'NP',elemente pozitive');

- afişarea elementelor pare dintr-un vector de numere întregi

- Exemplu în Turbo Pascal Se consideră var x: array [1..20] of integer şi var n,i: integer. Vom parcurge vectorul şi vom afişa doar numerele pare: for i:=1to n do if not odd (x[i]) then WrileLn (x[i])

- Exemplu în C++ Afişarea elementelor unui vector: cout<<”Vectorul introdus este:\n”; for (i=0; i cout<

Utilitate

Sortare

- prin selecţie

Algoritmul presupune ca la fiecare pas “i “ să se găsească elementul minim dintre a[i+1], a[i+2]…a[n] şi se interschimbă cu a[i].

Algoritmul este următorul:

Selecţie (a[nmax+1])

Pentru i 1 pana la n-1

{min a[i]

Pentru j i+1 pana la n

Daca (a[j] < min) min a[j]}

Daca (a[i]>min) interschimbă (a[i],a[j])

}

}

- prin inserţie

Algoritmul de sortare prin inserţie construieşte pas cu pas lista de elemente sortate, adăugând la ea câte un element la un moment dat. La fiecare pas un element este extras din lista iniţială şi este introdus în lista de elemente sortate. Elementul este inserat în poziţia corectă în lista sortată, astfel încât ea să rămână sortată în continuare.

Algoritmul este următorul:

pentru i := 1 până la N-1

aux := a[i];

j := i-1;

cât timp (j>=0) si (a[j]>aux)

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

j := j-1;

sfârşit cât timp;

a[j+1] := aux;

sfârşit pentru;

- prin numărare :

Algoritmul sortează un vector A astfel: pentru fiecare element din vector se număra câte elemente mai mici decât el exista în vector. Se va folosi un vector suplimentar K, iar rezultatul se depune in vectorul B.

Algoritmul este următorul:

Pentru i:= 1 până la n

K[i]:=0;

Sfârşit pentru;

Pentru i:=1 până la n-1

Pentru j:= i+1 până la n

Daca a [i] < a[j]

atunci

K[j]:= k [j] +1;

Altfel

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

sfârşit pentru;

sfârşit pentru;

pentru i:=1 până la n

B [k [i] +1] := A[i]

sfârşit pentru;

- prin interschimbare

Acesta metoda se rezumă la a compara fiecare element cu celelalte, făcându-se interschimbarea daca elementul mai mare are indexul mai mic. Este cea mai simplă metode de sortare.

Algoritmul este următorul:

simple-sort (a[Nmax+ 1])

pentru i 1 până la n

pentru j i+1 până la n

dacă a[i]>a[j]

interschimbă (a[i], a[j])

}
Căutare

- secvenţială

Această operaţie necesită o parcurgere a vectorului, de la prima poziţie până la sfârşit sau până s-a găsit elementul căutat. Găsirea elementului căutat este marcat de o variabilă logică găsit, poziţionată iniţial pe fals. Fie x vectorul, iar a elementul căutat.

găsit:= fals;

i:= 1;

while (i<=n) and (not găsit) do

if x[i]=y then

găsit:=true

else

Inc(i)

- binară: se compară elementul căutat cu elementul din mijloc şi dacă ele nu coincide se va trece la căutarea doar în acea jumătate a vectorului în care în mod logic elementul căutat s-ar putea găsi: în stânga sau în dreapta, după cum elementul din mijloc este mai mare sau mai mic decât elementul căutat, până când domeniul în care trebuie să se mai caute s-a terminat.

s:=1; d:=N;

dacă (x<=a[d]) şi (x>=a[s]) atunci

repetă

m:=(s+d) div 2;

dacă x>a[m] atunci s:=m+1 altfel d:=m-1

sfârşit dacă;

până când (a[m]=x) sau (s>d);

sfârşit repetă;

sfârşit dacă;

dacă a[m]=x atunci { elementul căutat se află pe poziţia m }

altfel { nu exista elementul căutat }

sfârşit dacă;

Operaţiile aritmetice cu vectori

- adunarea a doi vectori

Fiind daţi doi vectori, A cu M cifre si B cu N cifre, adunarea lor se face în mod obişnuit, ca la aritmetică. Pentru a evita testele de depăşire, se recomandă să se completeze mai întâi vectorul cu mai puţine cifre cu zerouri până la dimensiunea vectorului mai mare. La sfârşit, vectorul sumă va avea dimensiunea vectorului mai mare dintre A si B, sau cu 1 mai mult dacă apare transport de la cifra cea mai semnificativă.

Exemplu în C++:

Procedura de mai jos adăuga numărul B la numărul A.

void Add(Huge A, Huge B)

/* A <- A+B */

{ int i,T=0;

if (B[0]>A[0])

{ for (i=A[0]+1;i<=B[0];) A[i++]=0;

A[0]=B[0];

}

else for (i=B[0]+1;i<=A[0];) B[i++]=0;

for (i=1;i<=A[0];i++)

{ A[i]+=B[i]+T;

T=A[i]/10;

A[i]%=10;

}

if (T) A[++A[0]]=T;

}
- Scăderea a doi vectori

Fie doi vectori A si B. Pentru a calcula diferenţa A – B se presupune B ≤ A. Pentru aceasta, se porneşte de la cifra unităţilor şi se memorează la fiecare pas "împrumutul" care trebuie efectuat de la cifra de ordin imediat superior (împrumutul poate fi doar 0 sau 1). Deoarece B ≤ A, avem garanţia că pentru a scădea cifra cea mai semnificativă a lui B din cifra cea mai semnificativă a lui A nu e nevoie de împrumut.

Exemplu în C++:

void Subtract(Huge A, Huge B)

A <- A-B */

{ int i, T=0;

for (i=B[0]+1;i<=A[0];) B[i++]=0;

for (i=1;i<=A[0];i++)

A[i]+= (T=(A[i]-=B[i]+T)<0) ? 10 : 0;

/* Adică A[i]=A[i]-(B[i]+T);

if (A[i]<0) T=1; else T=0;

if (T) A[i]+=10; */

while (!A[A[0]]) A[0]--;

}
Înmulţirea unui vector cu un scalar

Această operaţie este o simplă implementare a modului manual de efectuare a calculului. La înmulţirea "de mână" a unui număr mare cu unul de o singură cifră, noi parcurgem deînmulţitul de la sfârşit la început, şi pentru fiecare cifră efectuăm următoarele operaţii:

Înmulţim cifra respectivă cu înmulţitorul;

Adăugam "transportul" de la înmulţirea precedentă;

Separăm ultima cifră a rezultatului şi o trecem la produs;

Celelalte cifre are rezultatului constituie transportul pentru următoarea înmulţire;

La sfârşitul înmulţirii, dacă există transport, acesta are o singură cifră, care se scrie înaintea rezultatului.

Exact acelaşi procedeu se poate aplica şi dacă înmulţitorul are mai mult de o cifră. Singura deosebire este că transportul poate avea mai multe cifre (poate fi mai mare ca 9). Din această cauză, la sfârşitul înmulţirii, poate rămâne un transport de mai multe cifre, care se vor scrie înaintea rezultatului.

Exemplu în C++:

void Mult(Huge H, unsigned long X)

/* H <- H*X */

{ int i;

unsigned long T=0;

for (i=1;i<=H[0];i++)

{ H[i]=H[i]*X+T;

T=H[i]/10;

H[i]=H[i]%10;

}

while (T) /* Cat timp exista transport */

{ H[++H[0]]=T%10;

T/=10;

}
Înmulţirea a doi vectori

Dacă ambele numere au dimensiuni mari, produsul lor se calculează înmulţind fiecare cifră a deînmulţitului cu fiecare cifră a înmulţitorului şi trecând rezultatul la ordinul de mărime (exponentul lui 10) cuvenit.

Exemplu în C++:

void MultHuge(Huge A, Huge B, Huge C)

/* C <- A x B */

{ int i,j,T=0;

C[0]=A[0]+B[0]-1;

for (i=1;i<=A[0]+B[0];) C[i++]=0;

for (i=1;i<=A[0];i++)

for (j=1;j<=B[0];j++)

C[i+j-1]+=A[i]*B[j];

for (i=1;i<=C[0];i++)

{ T=(C[i]+=T)/10;

C[i]%=10;

}

if (T) C[++C[0]]=T;

}
Împărţirea unui vector la un scalar

Ne propunem să scriem o funcţie care să împartă numărul A la scalarul B, să reţină valoarea câtului tot în numărul A şi să întoarcă restul (care este o variabilă scalară).

Exemplu în C++:

unsigned long Divide(Huge A, unsigned long X)

/* A <- A/X si intoarce A%X */

{ int i;

unsigned long R=0;

for (i=A[0];i;i--)

{ A[i]=(R=10*R+A[i])/X;

R%=X;

}

while (!A[A[0]] && A[0]>1) A[0]--;

return R;

}

Împărţirea a doi vectori

Dacă se dau doi vectori A si B şi se cere să se afle câtul C şi restul R. Etapele de parcurs sunt aceleaşi ca la punctul precedent. Cu alte cuvinte, după ce "coborâm" la fiecare pas următoarea cifră de la deîmpărţit, trebuie să aflăm cea mai mare cifră X astfel încât împărţitorul să se cuprindă de X ori în restul de la momentul respectiv. Acest lucru se face cel mai comod prin adunări repetate: pornim cu cifra X=0 şi o incrementăm, micşorând concomitent restul, până când restul care rămâne este prea mic.

Exemplu în C++:

void DivideHuge(Huge A, Huge B, Huge C, Huge R)

/* A/B = C rest R */

{ int i;

R[0]=0;C[0]=A[0];

for (i=A[0];i;i--)

{ Shl(R,1);R[1]=A[i];

C[i]=0;

while (Sgn(B,R)!=1)

{ C[i]++;

Subtract(R,B);

}

}

while (!C[C[0]] && C[0]>1) C[0]--;

}

Sugestii metodologice UNDE PREDĂM? Conţinutul poate fi predat în: - laboratorul de informatică - sală de clasă dotată cu video-proiector CUM PREDĂM? Metode: Expunere Conversaţie Învăţare prin descoperire Profesorul defineşte vectorii, prezintă operaţiile cu vectori, algoritmii de sortare şi căutare şi operaţiile aritmetice. Se recomandă utilizarea calculatoarelor pentru activităţile de fixare a noilor cunoştinţe. Ca materiale de evaluare se pot folosi: Probe orale, scrise şi practice