|
|
|
1. Care din urmatoarele afirmatii sunt adevarate? Justificati raspunsul. (0,5 puncte)
a) Metoda Divide et Impera consta in descompunerea in doua sau mai multe probleme mai simple.
b) Solutiile obtinute dupa aplicarea metodei Divide et Impera sunt retinute intr-o matrice patratica dupa care acestea se combina.
2. Fie subprogramul urmator : (1,5 puncte)
function f(k,p:integer):integer;
Var m:integer ;
begin
if (k=p) then f :=k
else begin
m:=(k+p) div 2;
f:= f(k,m)+f(m+1,p);
end;
end;
Ce se va afisa in urma apelului f(1,10)?
3. Scrieti care este efectul urmatorului subprogram. Transforma aceasta functie intr-o procedura care sa aiba acelasi efect. (2 puncte)
Type vect = array[1..100] of integer;
function test(x:vect; p,q:byte):integer;
Var m:byte;
m1,m2:integer;
begin
if q-p<=1 then
if x[p]<x[q] then
test:=x[p]
else
test:=x[q]
else
begin m:=(p+q) div 2;
m1:=test(x,p,m);
m2:=test(x,m+1,q);
if m1<m2 then test:=m1
else test:=m2
end;
end;
4. Scrieti un subprogram care realizeaza cautarea binara a unui element intr-un vector sortat crescator indicand pozitia acestuia in vector. (2,5 puncte)
5. Folosind metoda Divide et Impera, realizati un subprogram care sa returneze numarul de elemente negative dintr-un vector cu n numere intregi. (2,5 puncte)
Nota: Toate subiectele sunt obligatorii. Se acorda 1 punct din oficiu.
2. Se afiseaza valoarea 55. Calculeaza suma numerelor de la 1 la 10.
3. Subprogramul calculeaza minimul dintr-un vector.
procedure test(x:vect;p,q:byte;var min:integer);
var m:byte;
m1,m2:integer;
begin
if q-p<=1 then
if x[p]<x[q] then min:=x[p]
else min:=x[q]
else
begin
m:=(p+q) div 2;
test(x,p,m,m1);
test(x,m+1,q,m2);
if m1<m2 then min:=m1
else min:=m2;
end;
end;
4.
function binar(p,q:byte):byte;
var m:byte;
begin
if q<p then binar:=0
else
begin
m:=(p+q) div 2;
if x[m]=a then binar:=m
else if a<x[m] then binar:=binar(p,m-1)
else binar:=binar(m+1,q);
end;
end;
5.
function nrneg(p,q:byte):byte;
var m,m1,m2:byte;
begin
if q=p then
if x[p]<0 then nrneg:=1
else nrneg:=0
else
begin
m:=(p+q) div 2;
m1:=nrneg(p,m);
m2:=nrneg(m+1,q);
nrneg:=m1+m2;
end;
end;
