Probleme rezolvate
Problemele de la Divide et impera vor fi rezolvate prin 2 metode:
- cu proceduri
- cu functii
Folsoind metoda Divide et impera sa se afiseze suma primelor n numere naturale. n se citeste de la tastatura.
Prima metoda
var n:byte;
function suma(p,u:byte):integer;{p-pozitia primului element din sirul p..u, u-pozitia ultimului element din sirul p..u}
var m:byte;s1,s2:integer;
begin
if(p=u) then suma:=p {daca sirul are un singur element suma este egala cu valoarea elementului}
else begin
m:=(p+u)div 2;{gasim pozitia elementului din mijloc}
s1:=suma(p,m);{s1-suma elementelor din prima parte a sirului}
s2:=suma(m+1,u);{s2-suma elementelor din cea de-a doua parte a sirului}
suma:=s1+s2;{suma elementelor din sirul p..u este suma celor elementelor din cele 2 subsiruri}
end;
end;
begin
write('n=');readln(n);
writeln('suma=',suma(1,n));{primul element se afla pe pozitia 1 iar ultimul pe pozitia n}
end.
A doua metoda
var n:byte;s:integer;
procedure suma(p,u:byte; var s:integer);{p-pozitia primului element, u-pozitia ultimului element din sirul p..u; s-suma elementelor din sir}
var m:byte;s1,s2:integer;
begin
if(p=u) then s:=p {daca sirul are un singur element suma elementelor din sir este egala cu valoarea elementului}
else begin
m:=(p+u)div 2;{gasim pozitia elementului din mijloc}
suma(p,m,s1);{s1-suma elementelor din prima parte a sirului p..u}
suma(m+1,u,s2);{s2-suma elementelor din a doua parte a sirului p..u}
s:=s1+s2;{suma elementelor din sir este egala cu suma dintre cele 2 rezultate ale subsirurilor}
end;
end;
begin
write('n=');readln(n);
s:=0;{initializam suma cu 0}
suma(1,n,s);{primul element se afla pe pozitia 1, ultimul element se afla pe pozitia n}
writeln('suma=',s);
end.
Sa se afiseze folosind metoda Divide et impera suma elementelor unui sir de n numere intregi.
Prima metoda
var a:array[1..10]of integer;
n:byte;
function suma(p,u:byte):integer;{p-pozitia primului element din sir, u-pozitia ultimului element din sir}
var m:byte;
begin
if(p>u) then suma:=0 {aceasta conditie nu este obligatorie. Daca se intampla una stfel de caz, functia returneaza valoarea 0 deoarece s-au terminat de adunat toate elementele din subsir}
else if (p=u) then suma:=a[p] {daca avem un singur element suma elementelor din sir este egala cu valoarea elementului}
else begin
m:=(p+u)div 2;{gasim pozitia elementului din mijloc}
suma:=suma(p,m)+suma(m+1,u);{pentru a afla rezultatul trebuie sa adunam rezultatele obtinute pentru cele 2 subsiruri}
end;
end;
procedure citire;{citirea datelor de intrare}
var i:byte;
begin
write('n=');readln(n);
for i:=1 to n do
begin
write('a[',i,']=');readln(a[i]);
end;
end;
begin
citire;
writeln('suma=',suma(1,n));{primul element se afla pe pozitia 1 iar ultimul se afla pe pozita n}
end.
A doua metoda
var a:array[1..10]of integer;
n:byte;s:integer;
procedure suma(p,u:byte;var s:integer);{p-pozitia primului element, u-pozitia ultimului element, s-suma elementelor de pe pozitiile p..u}
var m:byte;s1,s2:integer;
begin
if(p=u) then s:=a[p] {daca avem un singur element atunci suma elementelor din sir este egala cu aceasta valoare}
else begin
m:=(p+u)div 2;{gasim pozitia elementului de la mijloc}
suma(p,m,s1);{s1-suma elementelor aflate pe primele pozitii din sir}
suma(m+1,u,s2);{s2-suma elementelor aflate in cea de-a doua parte a sirului}
s:=s1+s2;{suma elementelor din sir se gaseste adunand cele 2 rezultate ale celor 2 subsiruri}
end;
end;
procedure citire;{citim datele de intrare}
var i:byte;
begin
write('n=');readln(n);
for i:=1 to n do
begin
write('a[',i,']=');readln(a[i]);
end;
end;
begin
citire;
s:=0;{initializam suma elementelor din sir}
suma(1,n,s);{primul element se afla pe pozitia 1, ultimul pe pozitia n}
writeln('suma=',s);
end.
Folosind metoda Divide et impera se se gaseasca valoarea minima dintr-un sir de n numere intregi.
Prima metoda
var a:array[1..100]of integer;
n:integer;
procedure citire;{citirea datelor de intrare}
var i:byte;
begin
write('n=');readln(n);
For i:=1 to n do
begin
write('a[',i,']=');readln(a[i]);
end;
end;
function minim(p,u:integer):integer; {p-pozitia primului element, u-pozitia ultimului element}
var m:byte;m1,m2:integer;
begin
if(p=u) then minim:=a[p] {daca sirul are un singur element atunci valoarea minima este egala cu valoarea elementului}
else begin
m:=(p+u)div 2;{gasim pozitia elementului din mijloc}
m1:=minim(p,m);{m1 - valoarea minima din prima parte a sirului}
m2:=minim(m+1,u);{m2-valoarea minima din cea de-a doua parte a sirului}
if (m1>m2) then minim:=m2 {verificam care dintre cele 2 valori este mai mica. min- valoarea minima rezultata in urma comparatiei (rezultatul problemei)}
else minim:=m1;
end;
end;
begin
citire;
write('valoarea minima=',minim(1,n));{primul element se afla pe pozitia 1, ultimul element se gaseste pe pozitia n}
end.
A doua metoda
var a:array[1..100]of integer;
n,min:integer;
procedure citire;{citirea datelor de intrare}
var i:byte;
begin
write('n=');readln(n);
For i:=1 to n do
begin
write('a[',i,']=');readln(a[i]);
end;
end;
procedure minim(p,u:integer;var min:integer);{p-pozitia primului element din sir,u-pozitia ultimului element din sir, min-valoarea minima rezultata}
var m:byte;m1,m2:integer;
begin
if(p=u) then min:=a[p] {daca sirul are un singur element atunci valoarea minima este egala cu valoarea acestui element}
else begin
m:=(p+u)div 2;{gasim pozitia elementului din mijloc}
minim(p,m,m1);{m1-valoarea minima din prima parte a sirului}
minim(m+1,u,m2);{m2-valoarea minima din cea de-a doua parte a sirului}
if (m1>m2) then min:=m2 {rezultatul problemei min - valoarea minima dintre cele 2 valori rezultate}
else min:=m1;
end;
end;
begin
citire;
min:=a[1];{initializam valoarea minima}
minim(1,n,min);{primul element din sir se gaseste pe pozitia 1 iar ultimul se gaseste pe pozitia n}
write('valoarea minima=',min);
end.
