Informatică portofoliu

I.METODA DIVIDE ET IMPERA

1.Notiuni introductive

Asa cum spune si denumirea metodei (imparte si stapaneste), metoda se bazeaza pe impartirea unei probleme date in subprobleme, iar solutia finala a problemei initiale este data de combinarea tuturor solutiilor partiale ale problemei initiale. Impartirea problemei in doua subprobleme se continua pana cand se ajunge la o problema cu rezolvare imediata. Principiul are la baza metoda recirsivitatii.

2.Aplicatii

- Sortarea prin interclasare

Fiind dat un vector, sa se realizeze sortarea sa folosind metoda divide et impera.

Program interclasare_divide;

Uses crt;

Type sir=array[1..10] of integer;

Var n,i:integer;

A,b:sir;

Procedure inter(m,st,dr:integer; var a:sir);

Var i,j,k:integer;

Begin

i:=st; j:=m+1; k:=1;

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

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

b[k]:=a[i];

inc(i);

inc(k);

end

else begin

b[k]:=a[j];

inc(j);

inc(k);

end;

if i<m then

for j:=i to m do begin

b[k]:=a[j];

inc(k);

end

else

for i:=j to dr do begin

b[k]:=a[i];

inc(k);

end;

k:=1;

for i:=st to dr do begin

a[i]:=b[k];

inc(k);

end;

end;

procedure apelare(st,dr:integer; var a:sir);

var aux,m:integer;

begin

if (st<dr) then

begin

if a[st]>a[dr] then

begin

aux:=a[st];

a[st]:=a[dr];

a[dr]:=aux;

end

else begin

m:=(st+dr) div 2;

apelare(st,m,a);

apelare(m+1,dr,a);

inter(st,dr,m,a);

end;

end;

end;

Begin{pp}

clrscr;

write(’n= ’);

readln(n);

for i:=1 to n do

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

readln(a[i]);

apelare(1,n,a);

for i:=1 to n do

write(a[i]:4);

readln;

end.

- Problema de calcul a unei sume

Sa se realizeze program care folosind metoda divide et impera, prina intermediul unor subprograme calculeaza suma: 1+2+3+…+n

Program suma_1;

Uses crt;

Var n:integer;

Function suma (k,p:integer) : integer;

Begin

If (k=p) then suma:=k

Else suma:= suma(k,(k+p) div 2) + suma ((k+p) div 2+1, p);

End;

Begin

Clrscr;

Write(’Dati n = ’);

Readln(n);

Write(’Suma calculata este ’, suma(1,n);

Readln;

End.

- Problema de verificare

Sa se verifice daca un sir este sortat crescator

Program verificare_1;

Uses crt

Type sir=array[1..10] of integer;

Var x:sir;

n:integer;

function verif (var x:sir; k,p:integer);

var ok1,ok2:boolean;

begin

if (k=p) then verif:=true

else begin

ok1:=verif(x,k,trunc(k+p)/2);

ok2:= verif(x,trunc((k+p)/(2+1))p);

verif:=ok1 and ok2 and (x[k+p] div 2)<=(x[k+p]div2+1);

end;

end;

begin

clrscr;

write(’ Dati n= ’);

readln(n);

writeln(’In urma verificarii sirul este sortat ’, verif(1,n));

readln;

end.

- Problema de maxim

Sa se realizeze program care realizeaza maximul elementelor negative.

Program maxim;

uses crt;

type sir=array[1..10] of integer;

var x:sir; n:integer;

function maxim(x:sir; k,p:integer):integer;

var max1, max2:integer;

begin

if (k=p) then

if (x[k]<0) then maxim:=x[k]

else maxim:=-300

else begin

max1:=maxim(x,k,(k+p)div2);

max2:=maxim(x,(k+p) div 2+1,p);

if max1<max2 then maxim:= max2

else maxim:=max1;

end;

end;

begin

clrscr;

write(’Dati n= ’);

readln(n);

writeln(’Maximul elementelor este ’, maxim(1,n));

readln;

end.

- Constructii de siruri

Fiind dat un sir de n elemente, sa se construiasca sirul z cu elemente pozitive.

Program constructie_1;

uses crt;

type sir=array[1..10] of integer;

var x,z:sir; n:integer;

procedure citire(var x:sir; k,p:integer);

begin

if (k=p) then begin

write(’Dati x[‚,k,’]= ’);

readln (x[k]);

end

else begin

citire(x,k,(k+p) div 2);

citire(x,(k+p) div 2+1,p);

end;

end;

procedure afisare(x:sir; k,p:integer);

begin

if (k=p) then write (x[k]:4)

else begin

afisare(x,k,(k+p) div 2);

afisare(x,(k+p) div 2+1, p);

end;

end;

procedure constructie(x:sir; k,p:integer; var z:sir; var nz:integer);

begin

if (k=p) then begin

if (x[k]>0) then begin