2. NoNo iuni introductiveiuni introductive
Divide et Impera (mparte i Stp但nete) este o metod de programare care
se aplic problemelor care pot fi descompuse 樽n subprobleme
independente, similare problemei ini釘iale, de dimensiuni mai mici i care pot
fi rezolvate foarte uor.
Metoda presupune:
Descompunerea problemei ini釘iale 樽n subprobleme independente;
Rezolvarea subproblemelor;
Construirea rezultatului prin compunerea solu釘iilor problemelor de
dimensiuni mici.
3. Metoda DIVIDE ET IMPERA se poate aplica 樽n rezolvarea unei
probleme care 樽ndeplinete urmtoarele condi釘ii :
se poate descompune 樽n( dou sau mai multe) subprobleme;
aceste subprobleme sunt independente una fa釘 de alta (o
subproblema nu se rezolv pe baza alteia i nu se folosete
rezultatele celeilalte);
aceste subprobleme sunt similare cu problema ini釘ial;
la r但ndul lor subproblemele se pot descompune (dac este
necesar) 樽n alte subprobleme mai simple;
aceste subprobleme simple se pot solu釘iona imediat prin
algoritmul simplificat.
4. Cutarea binarCutarea binar
Algoritmul de cutare binar este un algoritm de
cutare folosit pentru a gsi un element 樽ntr-o list
ordonat.
Algoritmul func釘ioneaz pe baza tehnicii divide et
impera. Valoarea cutat este comparat cu cea a
elementului din mijlocul listei. Dac e egal cu cea a
acelui element, algoritmul se termin. Dac e mai mare
dec但t acea valoare, algoritmul se reia, de la mijlocul
listei p但n la sf但rit, iar dac e mai mic, algoritmul se
reia pentru elementele de la 樽nceputul listei p但n la
mijloc.
ntruc但t la fiecare pas cardinalul mul釘imii de elemente 樽n
care se efectueaz cutarea se 樽njumt釘ete,
algoritmul are complexitate logaritmic.
5. ProgramulProgramul
program cautare_binara;
var a:array[1..100] of integer; n,x:integer;
function cautb(s,d,x:integer):integer;
var m:integer;
begin
if s>d then cautb:=-1
else
begin
m:=(s+d)div 2;
if a[m]=x then cautb:=m
else
if x>a[m] then cautb:=cautb(m+1,d,x)
else cautb:=cautb(s,m-1,x);
end;
end;
6. Continuare programContinuare program
procedure citire;
var f:text;
begin
assign(f,'cautb.txt');reset(f);n:=0;
while not eof(f) do
begin
n:=n+1; readln(f,a[n]);
end;
close(f);
end;
begin
citire; readln(x);
writeln(cautb(1,n,x));
end.
7. Aplica釘iiAplica釘ii
S se determine cea mai mare valoare dintr-un ir de n numere
樽ntregi, folosind metoda Divide et Impera.
Rezolvare:
Dac irul are un singur element, acesta va fi elementul maxim.
Pentru un subir oarecare de cel mult 2 elemente vom avea
urmtoarele etape:
mpr釘im irul ini釘ial x [ p . . q ] 樽n dou subiruri x [ p . . m] i x [
m+1 . . q], unde m este mijlocul irului: m=[(p+q)/2]. Cele dou
subiruri pot fi 樽mpr釘ite la r但ndul lor 樽n alte dou iruri p但n se
ajunge la un subir de dimensiune 1. Notm cu x [p . . q] subirul
format din toate elementele irului dintre x[p] i x[q].
Se determin recursiv elementul maxim pentru cele dou subiruri
(a i b).
Se combin cele dou maxime ob釘inute pentru aflarea maximului
din irul ini釘ial.
9. Subprogramul maximSubprogramul maxim
Type vector=array[1..100] of integer;
Var x:vector;
i,n:integer;
function maxim ( p , q : integer ) : integer;
var m, a, b : integer;
begin
if p < q then begin
m := ( p + q ) div 2;
a := maxim ( p , m );
b := maxim ( m + 1 , q ) ;
if a > b then maxim := a
else maxim := b;
end
else maxim := x [ p ];
end;
11. Aplica釘ii grilAplica釘ii gril
1. Ce va afia programul urmtor?
var v : array [ 1 . . 50 ] of integer ; i : integer;
function s ( a , b : byte ): longint;
begin
if a > b then s := 0
else if a=b then s := v [ a ]
else s := s ( a , ( a + b ) div 2 ) + s ( ( a + b ) div 2 + 1 , b );
end;
begin
for i := 1 to 20 do v [ i ] := i;
writeln ( s ( 5 , 9 ) );
readln;
end. a) 29 b) 35 c) 45 d) 14
12. Aplica釘ii grilAplica釘ii gril
2. Ce va afia programul pentru n = 10 ?
var n : integer;
function s ( a , b : integer ) : longint ;
var m : byte;
begin
if a <= b then
begin
m := ( a + b ) div 2;
s := m + s ( a , m-1 ) + s ( m+1 , b );
end
else s := 0;
end;
begin readln(n);
writeln ( s ( 1 , n ) );
end. a) 29 b) 35 c) 41 d) 45
![ProgramulProgramul
program cautare_binara;
var a:array[1..100] of integer; n,x:integer;
function cautb(s,d,x:integer):integer;
var m:integer;
begin
if s>d then cautb:=-1
else
begin
m:=(s+d)div 2;
if a[m]=x then cautb:=m
else
if x>a[m] then cautb:=cautb(m+1,d,x)
else cautb:=cautb(s,m-1,x);
end;
end;](https://image.slidesharecdn.com/metodadivideetimpera-150509070014-lva1-app6891/85/Metoda-Divide-et-Impera-5-320.jpg)
![Continuare programContinuare program
procedure citire;
var f:text;
begin
assign(f,'cautb.txt');reset(f);n:=0;
while not eof(f) do
begin
n:=n+1; readln(f,a[n]);
end;
close(f);
end;
begin
citire; readln(x);
writeln(cautb(1,n,x));
end.](https://image.slidesharecdn.com/metodadivideetimpera-150509070014-lva1-app6891/85/Metoda-Divide-et-Impera-6-320.jpg)
![Aplica釘iiAplica釘ii
S se determine cea mai mare valoare dintr-un ir de n numere
樽ntregi, folosind metoda Divide et Impera.
Rezolvare:
Dac irul are un singur element, acesta va fi elementul maxim.
Pentru un subir oarecare de cel mult 2 elemente vom avea
urmtoarele etape:
mpr釘im irul ini釘ial x [ p . . q ] 樽n dou subiruri x [ p . . m] i x [
m+1 . . q], unde m este mijlocul irului: m=[(p+q)/2]. Cele dou
subiruri pot fi 樽mpr釘ite la r但ndul lor 樽n alte dou iruri p但n se
ajunge la un subir de dimensiune 1. Notm cu x [p . . q] subirul
format din toate elementele irului dintre x[p] i x[q].
Se determin recursiv elementul maxim pentru cele dou subiruri
(a i b).
Se combin cele dou maxime ob釘inute pentru aflarea maximului
din irul ini釘ial.](https://image.slidesharecdn.com/metodadivideetimpera-150509070014-lva1-app6891/85/Metoda-Divide-et-Impera-7-320.jpg)
![Subprogramul maximSubprogramul maxim
Type vector=array[1..100] of integer;
Var x:vector;
i,n:integer;
function maxim ( p , q : integer ) : integer;
var m, a, b : integer;
begin
if p < q then begin
m := ( p + q ) div 2;
a := maxim ( p , m );
b := maxim ( m + 1 , q ) ;
if a > b then maxim := a
else maxim := b;
end
else maxim := x [ p ];
end;](https://image.slidesharecdn.com/metodadivideetimpera-150509070014-lva1-app6891/85/Metoda-Divide-et-Impera-9-320.jpg)
![Programul principalProgramul principal
begin
write(n=); readln(n);
for i:=1 to n do
begin
write(x[, i ,]=);
readln ( x[i] );
end;
writeln ( maximul=, maxim ( 1, n ));
readln;
end.](https://image.slidesharecdn.com/metodadivideetimpera-150509070014-lva1-app6891/85/Metoda-Divide-et-Impera-10-320.jpg)
![Aplica釘ii grilAplica釘ii gril
1. Ce va afia programul urmtor?
var v : array [ 1 . . 50 ] of integer ; i : integer;
function s ( a , b : byte ): longint;
begin
if a > b then s := 0
else if a=b then s := v [ a ]
else s := s ( a , ( a + b ) div 2 ) + s ( ( a + b ) div 2 + 1 , b );
end;
begin
for i := 1 to 20 do v [ i ] := i;
writeln ( s ( 5 , 9 ) );
readln;
end. a) 29 b) 35 c) 45 d) 14](https://image.slidesharecdn.com/metodadivideetimpera-150509070014-lva1-app6891/85/Metoda-Divide-et-Impera-11-320.jpg)
