Tehnici de programare (Desparte si stapaneste)

,,DIVIDE ET IMPERA''=,,desparte si stapaneste''

Metoda de programare DIVIDE ET IMPERA consta in impartirea 
problemei initiale de dimensiuni [n] in doua sau mai multe probleme de dimensiuni reduse .In general se executa impartirea in doua subprobleme  de dimensiuni aproximativ egale  si anume [n/2] . Impartirea in subprobleme are loc pana cand dimensiunea acestora devine suficient de mica pentru a fi rezolvate in mod direct(cazul de baza).Dupa rezolvarea celor doua subprobleme se executa faza de combinare a rezultatelor in vederea rezolvarii intregii probleme .

Dupa  cum sugereaza si numele  "desparte si stapaneste "etapele rezolvarii unei probleme (numita problema initiala) in   DIVIDE ET IMPERA  sunt :

-descompunerea problemei initiale in subprobleme independente ,smilare problemei de baza ,de dimensiuni mai mici 

-descompunerea treptata a subproblemelor in alte subprobleme din ce in ce mai simple ,pana cand se pot rezolva imediata ,prin algoritmul simplificat ;

-rezolvarea subproblemelor simple ;

-combinarea solutiilor gasite pentru construirea solutiilor subproblemelor de dimensiuni din ce in ce mai mar

-combinarea ultimelor solutii determina obtinerea solutiei problemei initiale .

Se citeste un vector cu n componente, numere naturale. Se cere sa se tipareasca valoarea maxima.

>      daca i=j, valoarea maxima va fi v[i];

>      contrar vom imparti vectorul in doi vectori: primul vector va contine componentele de la i la (i+j) div 2, al doilea vector va contine componentele de la (I+J) div 2 +1 la j; rezolvam problemele (aflam maximul pentru fiecare din ele) iar solutia problemei va fi data de valoarea maxima dintre rezultatele celor doua subprobleme.

program maxim;

var v:array[1..10] of integer;

n,i:integer;

function max(i,j:integer):integer;

var a,b:integer;

begin

if i=j then max:=v[i]

else begin

a:=max(i, (i+j) div 2);

b:=max((i+j) div 2+1,j);

if a>b then max:=a

else max:=b;

end;

end;

begin

write(’n=’);

readln(n);

for i:=1 to n do read(v[i]);

writeln(maximul este ’,max(1,n));

end.

Link:http://www.creeaza.com/referate/informatica/Metoda-de-programare-DIVIDE-ET449.php