Metoda de programare divide et impera

Metoda de programare divide et impera const{ }n }mp{r`irea problemei ini`iale de dimensiune n }n dou{ sau mai multe probleme de dimensiuni mai reduse. ]n general se execut{ }mp{r`irea }n dou{ subprobleme de dimensiuni aproximativ egale ~i anume [n/2]. Acest{ }mp{r`ire }n subprobleme are loc p|n{ c|nd dimensiunea acestora devine suficient de mic{ pentru a fi rezolvate }m mod direct ( cazul de baz{ ). Dup{ rezolvarea celor dou{ subprobleme se execut{ faza de combinare a rezultatelor }n vederea rezolv{rii }ntregii probleme.

Putem formaliza cele descrise mai sus }n urm{torul pseudocod:

procedura divide ( problem{(p,u));dac{ n<=d0 atunci rezolvare_direct{(problem{(p,u))

altfelmij<--(p+u) div 2;divide(problem{(p,mij));divide(problem{(mij+1,u))combinare_rezultate(p,mij,u)

sf|r~it_dac{;

Aici p ~i u reprezint{ limitele inferioar{ ~i superioar{ }ntre care se g{sesc datele corespunz{toare ale unei probleme. De obicei, aceste date sunt memorate }ntr-un vector de dimensiune n iar rezolvarea problemei const{ }n apelul ini`ial pentru p=1 ~i u=n.

Exemplu : Calcula`i, prin metoda divide et impera, elementul de valoare minim{ dintr-un vector de lungime n de elemente numere }ntregi.

Pe cazul general se va calcula mai }nt|i elementul minim din zona de indici 1…[n/2], apoi elementul minim din zona [n/2]+1...n urm|nd ca la combinarea rezultatelor s{ se determine minimul acestor dou{ valori. Similar, zona elementelor de la 1 la [n/2] se va }mp{r`i din nou }n dou{ zone aproximativ egale. La fel }n cazul zonei [n/2]+1, ... ,n. Procedeul va continua p|n{ c|nd o astfel de zon{ este format{ din cel mult dou{ elemente, caz }n care se va executa calcularea minimului }n mod direct, prin compara`ii.

Vom avea astfel o prim{ func`ie ce calcul a minimului a dou{ elemente:

function min_2(a,b:integer):integer;beginif a<b then min_2:=a

else min_2:=bend;

Acum, func`ia ce implementeaz{ algoritmul de tip divide et impera va fi, spre exemplu:

function min(var x:vector;p,u:integer):integer;var mij,m1,m2:integer;beginif u-p<=1 then min:=min_2(x[p],x[u])

elsebeginmij:=(p+u) div 2;m1:=min(x,p,mij);m2:=min(x,mij+1,u);min:=min_2(m1,m2)end

end;

]n programul principal se va citi: n, vectorul x ~i se va executa un apel de forma: m:=min(x,1,n);Prezent{m pe un exemplu executarea calculelor pe arborele asociat: