Metoda divide et impera (divide si stapaneste)

Metoda divide et impera (divide si stapaneste)

Aceasta modalitate de elaborare a programelor consta in impartirea repetata a unei probleme de dimensiune mai mare in doua sau mai multe subprobleme de acelasi tip urmata de combinarea solutiilor subproblemelor rezolvate pentru a obtine solutia problemei initiale.

Se da un vector A=(a₁,,a_n) si trebuie efectuata o prelucrare oarecare asupra elementelor sale.

Presupunem ca:

p,qI cu 1 £p < q £ mI a.i. prelucrarea secventei se poate face prelucrand subsecventele:

si si apoi combinand rezultatele pentru a obtine prelucrarea intregii secvente .

Daca se reuseste o astfel de formalizare a problemei atunci ea poate fi rezolvata cu ajutorul acestei metode.

Vom da in continuare o procedura recursiva in pseudocod:

procedure DI (p,q,α)

if q-p £ eps then

call PREL (p,q,α)

else

call IMPARTE (p,q,m) ;

call DI (p,m,β);

call DI (m+1,q,γ);

call COMB (β,γ,α);

endif;

return;

end procedure

Cateva precizari se impun:

procedura trebuie apelata prin call DI (1,n,α) in α obtinandu-se rezultatul final;

eps este lungimea maxim a unei secvene notata prin (p,q) pentru care se face prelucrarea directa fara a mai fi necesara impartirea in subprobleme;

procedura PREL realizeaza prelucrarea directa a secventelor (p,q);

procedura COMB realizeaza combinarea rezultatelor β si γ ale prelucrarii a doua secvente vecine (p,m) si (m+1,q) obtinand rezultatul α al prelucrarii intregii secvente (p,q);

prin procedura IMPARTE se obtine valoarea lui m.

Vom da ca exemplu problema sortarii crescatoare a unui sir de intregi prin interclasare.

deoarece secventele (i,i+1) sunt usor de ordonat acestea vor constitui secventele ce se vor prelucra, deci eps = 1;

m se va calcula ca (p+q)/2, deci nu mai e nevoie de procedura speciala IMPARTE;

procedura COMB va interclasa intotdeauna doua secvente (p,m) si (m+1,q) ordonate crescator;

vom folosi un vector x drept structura globala si vom face toate prelucrarile pe elementele sale nemaiavand nevoie de zonele α,β;

pentru zona γ vom folosi un vector local y in procedura COMB acesta continand elementele corespondente din x dar ordonate crescator; tot in procedura COMB se vor copia apoi elementele lui y din portiunea (p,q) in x;

evident ca procedurile din schema generala a algoritmului sunt functii C cititorul facand analogiile necesare.

#include <stdio.h>

#include <conio.h>

#define nrelem 100

int x[nrelem];

int n;

void PREL (int p, int q)

void COMB (int inf, int mijloc, int sup)

for(l=i; l<=mijloc; y[k++]=x[l++]);

for(l=j; l<=sup; y[k++]=x[l++]);

for(k=inf; k<=sup; x[k++]=y[k]);

void DI (int p, int q)

return;

void main(void)

DI (1,n);

printf('nsirul sortat crescator este:n');

for (i=1; i<=n; i++) printf('x[%d]=%dn',i,x[i]);

getch();