Prezentare Divide et Impera

Metoda Divide Et Impera

 Definitia metodei Divide et Impera

Metoda Divide et Impera se poate folosi pentru problemele care pot fi descompuse in subprobleme similare cu problema initiala (care se rezolva prin aceeasi metoda) si care prelucreaza multimi de date de dimensiuni mai mici,independente unele de altele (care folosesc multimi de date de intrare disjuncte).

Metoda Divide Et Impera se bazeaza pe descompunerea unei probleme in subprobleme similare,prin intermediul unu proces recursiv.Procesul recursiv de descompunere a unei subprobleme in alte subprobleme continua pana se obtine o subproblema cu rezolvare imediata (cazul de baza),dupa care se compun solutiile subproblemelor - pana se obtine solutia problemei initiale.

Pasii algoritmului sunt:

1. Pas1.Se descompune problema in subprobleme similare problemei initiale , de dimensiuni mai mici,independente unele de altele(care folosesc multimi de date de intrare disjuncte - di)
2. Pas2.Daca subproblema permite rezolvare imediata (corespunde cazului de baza), atunci se rezolva obtinandu-se solutia s ; altfel se revine la Pas 1.
3. Pas3.Se combina solutiile subproblemelor(si) in care a fost descompusa o subproblema ,pana cand se obtine solutia problemei initiale.

Implementarea metodei "Divide et Impera "

Deoarece subproblemele in care se descompune problema sunt similare cu problema initiala ,algoritmul divide et impera poate fi implementat recursiv.Subprogramul recursiv divide_et_impera(d,s) unde d reprezinta dimensiunea subproblemei (corespunde multimii datelor de intrare),iar s solutia subproblemei ,poate fi descris in pesudocod astfel:

divide_et_impera(d,s)

inceput

   daca dimensiunea d corespunde unui caz de baza 

atunci se determina solutia s a problemei ;

altfel

  pentru i=1,n executa

se determina dimensiunea d_i a subproblemei p_i;

se determina solutia s_i a subproblemei p_i prin 

apelul divide_et_impera(d_i,s_i);

  sfarsit pentru;

         se combina solutiile s_1,s_2,s_3,....,s_n;

    sfarsit daca;

sfarsit;

Implementarea acestui algoritm in limbajul C++ se face altfel:

/*declaratii globale pentru datele de intrare,ce vor fi divizate in submultimi disjuncte pentru subproblemele in care se descompune problema */

void divizeaza(<parametrii: submultimile>)

{ //se divizeaza multimea de date de intrare in submultimi disjuncte d_i}

void combina(<parametri; solutiile s_i care se combina>)

{//se combina solutiile obtinute s_i}

void dei(<parametri: multimea de date d si solutia s>)

{//declaratii de variabile locale

 if(<este_caz_de_vaza>) 

 {//se obtine solutia corespunzatoare subproblemei}

   else 

       {divizeaza(<parametri: k submultimi>);

for(i=1;i<=k;i++)

dei(<parametri:multimea de date d_i si solutia s_i>);

        combina(<parametri:solutiile s_i);}}

void main()

{//declaratii de variabile locale

 //se citesc datele de intrare ale problemei - multimea d

dei(<parametri: multimea de date d si solutia s>);

//se afiseaza solutia problemei - s} 

Exemplu :

Sa se calculeze suma elementelor pare dintr-un vector v care contine numere intregi. Numarul de elemente ale vectorului (n) si elementele lui se citesc de la tastatura.

Implementarea metodei divide et impera in acest exemplu se face astfel:

Subprograme folosite.

1. Subprogramul divizeaza() - Numarul de subprobleme in care se descompune problema este 2 (k=2).Multimea datelor de intrare este divizata in doua submultimi disjuncte,prin divizarea multimii indicilor in doua submultimi disjuncte de indici,adica multimea indicilor [s,d] (unde s este primul indice ,iar d ultimul) este divizata in duoua submultimi sijuncte,[s,m] si [m+1,d],unde m este mijlocul intervalului m=(s+d)/2.In subprogram,procesul de divizare consta in determinarea mijlocului intervalului m.
2. Suprogramul combina() -Combinarea solutiei inseamna adunarea celor doua sume obtinute prin rezolvarea celor doua subprobleme.In subprogram sunt combinate cele doua valori obtinute prin prelucrare celor doua intervale,adica se aduna cele doua valori x si y,obtinandu-se solutia z;
3. subprogramul dei() - O subproblema corespunde cazului de baza atunci cand submultimea contine un singur element(se poate calcula suma,obtinandu-se solutia subproblemei ).Daca s-a terminat procesul recursiv (prin procesul de divizare ,cele doua capete ale intervalului au ajuns sa fie identice) atunci se prelucreaza cazul de baza (se calucleaza suma in variabila z,corespunzatoare solutiei ; astfel: daca numarul v[s] este par,atunci suma va fi chiar numarul; altfel,are valoarea 0);altfel,se apeleaza subprogramul pentru divizarea intervalului,se apeleaza subprogramul dei() pentru primul interval,se apeleaza subprogramul dei() pentru al doilea interval si se combina cele doua rezultate:

#include<iostream>
using namespace std;

int v[100],n;

void divizeaza(int s,int d,int &m)
{

m=(s+d)/2;}

void combina(int x,int y,int &z)
{

z=x+y;}

void dei(int s,int d,int &z)
{

int m,x1,x2;

if(d==s)

if(v[s]%2==0)

z=v[s];

else z=0;

else

{divizeaza(s,d,m);

dei(s,m,x1);

dei(m+1,d,x2);

combina(x1,x2,z);}
}

int main()

{

int i,z;

cout<<"n= ";cin>>n;

for(i=1;i<=n;i++)

cin>>v[i];

dei(1,n,z);

cout<<"suma= "<<z;

}

Pentru mai multe informatii faceti click pe acest link