APLICATII CU TIPURI DE DATE STRUCTURATE ALGORITMI ELEMENTARI

1 TABLOURI

1.1 Determinare minim/maxim

Fiind dat un sir de n numere intregi memorat intr-un vector sa se determine cel mai mic element.

Program element_minim;

var a:array [1..20] of integer;

n,i,min:integer;

begin

write('n=');readln(n);

for i:=1 to n do

begin write('a[',i,']=');readln(a[i]) end;

min:=MAXINT;

for i:=1 to n do

if a[i]<min then min:=a[i];

writeln('Elementul minim din sir este: ',min);

readln

end.

Fiind dat un sir de n numere intregi memorat intr-un vector sa se determine cel mai mare element.

Program element_maxim;

var a:array [1..20] of integer;

n,i,max:integer;

begin

write('n=');readln(n);

for i:=1 to n do

begin write('a[',i,']=');readln(a[i]) end;

max:=-MAXINT;

for i:=1 to n do

if a[i]>max then max:=a[i];

writeln('Elementul maxim din sir este: ',max);

readln

end.

1.2 Ordonare (metoda bulelor, insertie, selectie, numarare)

Fiind dat un sir de n numere intregi memorat intr-un vector sa se ordoneze crescator elementele vectorului folosind metoda bulelor.

Program ordonare_metoda_bulelor;

var a:array[1..15]of integer;

n,i,aux:integer;

ordonat:boolean;

begin

write('n=');readln(n);

for i:=1 to n do

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

end;

write('Vectorul initial:');

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;

write('Vectorul ordonat crescator: ');

for i:=1 to n do

write(a[i],' ');

readln

end.

Fiind dat un sir de n numere intregi memorat intr-un vector sa se ordoneze crescator elementele vectorului folosind metoda insertiei.

Program ordonare_metoda_insertiei;

var a:array[1..15]of integer;

n,i,aux,j:integer;

begin

write('n=');readln(n);

for i:=1 to n do

begin

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

end;

write('Vectorul initial este: ');

for i:=1 to n do

write(a[i],' ');

writeln;

for i:=2 to n do

begin

aux:=a[i];j:=i-1;

while (j>0) and (aux<a[j])do

begin

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

j:=j-1

end;

a[j+1]:=aux

end;

write('Vectorul ordonat crescator: ');

for i:=1 to n do

write(a[i],' ');

readln

end.

Fiind dat un sir de n numere intregi memorat intr-un vector sa se ordoneze crescator elementele vectorului folosind metoda selectiei.

Program ordonare_metoda_selectiei;

var a:array[1..15]of integer;

n,i,aux,j,min,poz:integer;

begin

write('n=');readln(n);

for i:=1 to n do

begin

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

end;

write('Vectorul initial este: ');

for i:=1 to n do

write(a[i],' ');

writeln;

for i:=1 to n-1 do

begin

min:=a[i];poz:=i;

for j:=i+1 to n do

if a[j]<min then begin min:=a[j];

poz:=j end;

if poz<>i then begin

aux:=a[i];

a[i]:=a[poz];

a[poz]:=aux

end

end;

write('Vectorul ordonat crescator: ');

for i:=1 to n do

write(a[i],' ');

readln

end.

Fiind dat un sir de n numere intregi memorat intr-un vector sa se ordoneze crescator elementele vectorului prin numarare.

Program ordonare_numarare;

var a,nr:array[1..10]of integer;

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

begin

write('n=');readln(n);

for i:=1 to n do

begin

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

end;

write('Vectorul initial este: ');

for i:=1 to n do

write(a[i],' ');

writeln;

for i:=1 to n do

nr[i]:=1;

for i:=1 to n-1 do

for j:=i+1 to n do

if a[i]>a[j] then nr[i]:=nr[i]+1

else nr[j]:=nr[j]+1;

write('Vectorul ordonat crescator:');

for i:=1 to n do

begin

if nr[i]<>i then begin j:=i; repeat j:=j+1 until nr[j]=i; aux:=a[i];a[i]:=a[j];a[j]:=aux;

nr[j]:=nr[i];nr[i]:=i end;

end;

for i:=1 to n do

write(a[i],' ');

readln;

end.

1.3 Interclasare

Fiind date doua siruri de n, respectiv m numere intregi memorate in doi vectori (vectorii sunt ordonati crescator), se cere sa se formeze al treilea vector care sa contina elementele celor doi vectorui (elementele comune se iau o singura data) de asemenea ordonate crescator.

Program interclasarea_a_doi_vectori;

var a,b,c:array[1..20]of integer;

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

begin

write('n=');readln(n);

write('m=');readln(m);

for i:=1 to n do

begin

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

end;

for i:=1 to m do

begin

write('b[',i,']='); readln(b[i])

end;

write('Vectorul unu: ');

for i:=1 to n do

write(a[i],' ');

writeln;

write('Vectorul doi: ');

for i:=1 to m do

write(b[i],' ');

writeln;

i:=1;j:=1;k:=0;

while (i<=n) and (j<=m) do

begin

k:=k+1;

if a[i]<b[j] then begin

c[k]:=a[i];

i:=i+1

end

else if a[i]>b[j] then begin

c[k]:=b[j];

j:=j+1

end

else begin

c[k]:=a[i];

i:=i+1;

j:=j+1

end

end;

if i<=n then for j:=i to n do

begin

k:=k+1;

c[k]:=a[j]

end

else for i:=j to m do

begin

k:=k+1;

c[k]:=b[i]

end;

write('Vectorul rezultat: ');

for i:=1 to k do

write(c[i],' ');

readln

end.

1.4 Metode de cautare (secventiala, binara)

Fiind dat un sir de n numere intregi ordonat crescator, memorat intr-un vector si un numar intreg nr, sa se decida daca nr se gaseste in sirul celor n numere citite. (cautare binara)

Program cautare_binara;

var a:array [1..20] of integer;

n,i,nr,li,ls,mijloc:integer;

gasit:boolean;

begin

write('n=');readln(n);

for i:=1 to n do

begin

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

end;

write('nr=');readln(nr);

li:=1; ls:=n; gasit:=false;

repeat

mijloc:=(li+ls) div 2;

if nr=a[mijloc] then gasit:=true

else if nr<a[mijloc] then ls:=mijloc-1

else li:=mijloc+1

until (li>ls) or (gasit);

if gasit then writeln(nr,' face parte din sir si este pe pozitia ',mijloc)

else writeln(nr,' nu face parte din sir');

readln

end.

Fiind dat un sir de n numere intregi, memorat intr-un vector si un numar intreg nr, sa se decida daca nr se gaseste in sirul celor n numere citite. (cautare secventiala)

Program cautare_secventiala;

var a:array [1..20] of integer;

n,i,nr:integer;

gasit:boolean;

begin

write('n=');readln(n);

for i:=1 to n do

begin

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

end;

write('nr=');readln(nr);

gasit:=false; i:=1;

while (i<=n) and (not gasit) do

begin

if nr=a[i] then gasit:=true;

i:=i+1

end;

if gasit then writeln(nr,' face parte din sir si este pe pozitia ',i-1)

else writeln(nr,' nu face parte din sir');

readln

end.

1.5 Parcurgerea unei matrice in raport cu diagonalele

Se considera o matrice cu n linii si n coloane.O matrice cu proprietatea ca numarul liniilor este egal cu numarul coloanelor se numeste matrice patratica.

a₁₁ a₁₂ a₁₃ a₁₄ diagonala principala: a₁₁, a₂₂, a₃₃, a₄₄

a₂₁ a₂₂ a₂₃ a₂₄ deasupra diagonalei principale: a₁₂, a₁₃, a₁₄, a₂₃, a₂₄, a₃₄

a₃₁ a₃₂ a₃₃ a₃₄ sub diagonala principala: a₂₁, a₃₁, a₃₂, a₄₁, a₄₂, a₄₃

a₄₁ a₄₂ a₄₃ a₄₄

Pentru a "vizita" elementele de pe diagonala principala parcurgem toate elementele din matrice in doua cicluri (liniile i de la 1 la n si coloanele j de la 1 la n) si pentru fiecare element a[i,j] testam daca este situat pe diagonala principala, adica verificam daca i=j.

For i:=1 to n do sau For i:=1 to n do

For j:=1 to n do <prelucreaza a[i,i]>

if i=j then

<prelucreaza a[i,j]>

Pentru a "vizita" elementele de deasupra diagonalei principale avem doua posibilitati:

a)     parcurgem toate elementele din matrice in doua cicluri (liniile i de la 1 la n si coloanele j de la 1 la n) si pentru fiecare element a[i,j] testam daca este situat deasupra diagonalei principale, adica verificam daca i<j

b)     "vizitam" numai elementele aflate deasupra diagonalei principale: parcurgem numai liniile i care contin elemente deasupra diagonalei principale i=1,2,.,n-1.Pentru fiecare linie i, parcurgem numai coloanele j ale liniei i care au elemente deasupra diagonalei principale, adica j=i+1,.,n.

b)

a) For i:=1 to n do b) for i:=1 to n-1 do

For j:=1 to n do for j:=i+1 to n do

if i<j then <viziteaza a[i,j]>

<prelucreaza a[i,j]>

Pentru a "vizita" elementele de sub diagonala principala avem doua posibilitati:

a)     parcurgem toate elementele din matrice in doua cicluri (liniile i de la 1 la n si coloanele j de la 1 la n) si pentru fiecare element a[i,j] testam daca este situat sub diagonala principala, adica verificam daca j<i

b)     "vizitam" numai elementele aflate sub diagonala principala: parcurgem numai liniile i care contin elemente situate sub diagonala principala i=2,.,n.Pentru fiecare linie i, parcurgem numai coloanele j ale liniei i care au elemente sub diagonala principala, adica j=1,.,i-1.

b)

a) For i:=1 to n do b) for i:=2 to n do

For j:=1 to n do for j:=1 to i-1 do

if j<i then <viziteaza a[i,j]>

<prelucreaza a[i,j]>

a₁₁  a₁₂ a₁₃ a₁₄ diagonala secundara: a₁₄, a₂₃, a₃₂, a₄₁

a₂₁ a₂₂ a₂₃ a₂₄ deasupra diagonalei secundare: a₁₁, a₁₂, a₁₃, a₂₁, a₂₂, a₃₁

a₃₁ a₃₂ a₃₃ a₃₄ sub diagonala secundara: a₂₄, a₃₄, a₃₃, a₄₄, a₄₃, a₄₂

a₄₁ a₄₂ a₄₃ a₄₄

Pentru a "vizita" elementele de pe diagonala secundara parcurgem toate elementele din matrice in doua cicluri (liniile i de la 1 la n si coloanele j de la 1 la n) si pentru fiecare element a[i,j] testam daca este situat pe diagonala secundara, adica verificam daca i+j=n+1.

For i:=1 to n do sau For i:=1 to n do

For j:=1 to n do <prelucreaza a[i,n-i+1]>

if i+j=n+1 then

<prelucreaza a[i,j]>

Pentru a "vizita" elementele de deasupra diagonalei secundare avem doua posibilitati:

a)     parcurgem toate elementele din matrice in doua cicluri (liniile i de la 1 la n si coloanele j de la 1 la n) si pentru fiecare element a[i,j] testam daca este situat deasupra diagonalei secundare, adica verificam daca i+j<n+1

b)     "vizitam" numai elementele aflate deasupra diagonalei secundare: parcurgem numai liniile i care contin elemente deasupra diagonalei secundare i=1,2,.,n-1.Pentru fiecare linie i, parcurgem numai coloanele j ale liniei i care au elemente deasupra diagonalei secundare, adica j=1,.,n-i.

b)

a) For i:=1 to n do b) for i:=1 to n-1 do

For j:=1 to n do for j:=1 to n-i do

if i+j<n+1 then <viziteaza a[i,j]>

<prelucreaza a[i,j]>

Pentru a "vizita" elementele de sub diagonala secundara avem doua posibilitati:

a)        parcurgem toate elementele din matrice in doua cicluri (liniile i de la 1 la n si coloanele j de la 1 la n) si pentru fiecare element a[i,j] testam daca este situat sub diagonala secundara, adica verificam daca i+j>n+1.

b)       "vizitam" numai elementele aflate sub diagonala secundara: parcurgem numai liniile i care contin elemente situate sub diagonala secundara i=2,.,n.Pentru fiecare linie i, parcurgem numai coloanele j ale liniei i care au elemente sub diagonala secundara, adica j=n,.,n-i+2.

b)a) For i:=1 to n do b) for i:=2 to n do

b) For j:=1 to n do for j:=n-i+2 to n do

b) if i+j>n+1 then <viziteaza a[i,j]>

b) <prelucreaza a[i,j]>

b)