Metoda "divide et impera"

Metoda "divide et impera" a fost sugerata de ideea fireasca de rezolvare a unei probleme complexe prin impartirea acesteia in doua sau mai multe subprobleme de acelasi tip cu cea initiala, mai simple, care prin rezolvarea lor, folosind solutiile deja obtinute, permit reconstituirea solutiei problemei initiale. Aceasta "divizare" poate fi aplicata sucesiv noilor subprobleme, pana la nivelul de detaliu la care obtinerea solutiilor subproblemelor este facila. In mod natural totul se finalizeaza cu reconstituirea de jos in sus a solutiilor partiale. O reprezentare grafica sugestiva a metodei este prezentata mai jos:

Fig.11.

Problema generala Sa consideram n elemente a₁, a₂, a_n si un subsir al acestuia a_p, a_p+1, a_q, cu p<q n asupra caruia avem de efectuat o prelucrare oarecare (procedura Prelucrare).

Solutie Metoda 'divide et impera' de rezolvare a acestei probleme presupune impartirea sirului determinat de capetele acestuia (procedura Divide), (p,q), in doua subsiruri (p,m) si (m + 1,q), p m<q sau (p,m-1) si (m,q), p<m q, asupra carora sa se poata efectua mai usor prelucrarea. Prin prelucrarea celor doua subsiruri se vor obtine rezultatele b si g care 'combinate' (procedura ObtinSolutieFinala) vor conduce la solutia a a problemei initiale. Impartirea in subsiruri poate continua pana la gradul de detaliu care permite obtinerea imediata a solutiei prelucrarii unui subsir. Metoda este ilustrata de procedura de mai jos:

procedura DivideEtImpera (p,q,a

daca p-q<d atunci

Prelucrare (p,q,a

altfel

Divide (p,q,m)

DivideEtImpera (p,m,b

DivideEtImpera (m + 1,q,g

ObtinSolutieFinala (b g a

sf daca

sfarsit DivideEtImpera

In cele mai frecvente cazuri, procedurile Divide, ObtinSoltieFinala si Prelucrare sunt compuse dintr-un numar redus de instructiuni sau sunt chiar vide, nemotivandu-se descrierea si apelul lor separat ca proceduri in corpul procedurii DivideEtImpera

Exemplu. Sa se determine apartenenta unui element la un sir ordonat crescator.

Solutie. Aplicand metoda "divide et impera" vom imparti sirul in doua "jumatati". In functie de elementul k (cautat), mai mic sau mai mare decat elementul de diviziune, vom renunta la prelucrarea (cautarea) unuia dintre subsiruri, rezultatul prelucrarii fiind deja cunoscut. Vom repeta prelucrarea numai pentru subsirul ramas pana cand se va ajunge la un sir despre care se poate afirma ca este gata prelucrat. Iata procedura care implementeaza aceasta forma "trunchiata" a algoritmului general (limbaj Pascal):

procedure dividimp (p,q:byte; var a:boolean);

var b,c : boolean;

m:byte;

begin

if (q-p > 1) then

if (s[p] = k) then

a := true

else

a := false

else

begin

m := (p + q) div 2;

if (s[m] > k) then

begin

dividimp(p,m,b);

c := false;

end

else

begin

b := false;

dividimp(m + 1, q, c);

end;

a := b or c;

end;

end;

Observatie. Programul apelant va testa valoarea variabilei raspuns a. Daca aceasta are valoarea true inseamna ca elementul cautat apartine secventei s, completata tot in programul apelant.

Merita a fi delimitate procedurile care reliefeaza metoda 'divide et impera' in acest caz:

procedura Prelucrare este reprezentata de urmatorul cod:

if (s[p] = k) then

a:= true

else

a: false;

- procedura Divide prin

m := (p + q) div 2;

- procedura ObtinSolutieFinala prin

a := b or c;