Metoda Divide et Impera

Metoda Divide et Impera (Imparte si Stapaneste) este o metoda de programare care se aplica problemelor care pot fi descompuse in subprobleme independente, similare problemei initiale, de dimensiuni mai mici si care pot fi rezolvate foarte usor. Procesul se reia pana cand (in urma descompunerilor repetate) se ajunge la probleme care admit rezolvare imediata.

Metoda presupune:

• Descompunerea problemei Pb curente in subprobleme independente SubPb_i.
• In cazul in care subproblemele SubPb_i. admit o rezolvare imediata se compun solutiile si se rezolva problema Pb
• Altfel se descompun in mod similar si subproblemele SubPb_i

Evident, nu toate problemele pot fi rezolvate prin utilizarea acestei tehnici. Majoritatea algoritmilor de Divide et Impera presupun prelucrari pe tablouri (dar nu obligatoriu).

Aceasta metoda (tehnica) se poate implementa atat iterativ dar si recursiv. Dat fiind ca problemele se impart impart in subprobleme in mod recursiv, de obicei impartirea se realizeaza pana cand sirul obtinut este de lungime 1, caz in care rezolvarea subproblemei este foarte usoara, chiar banala.

Spre exemplu fie un vector X=[x₁, x₂, x₃, …x_i … x_p… x_j, …x_n] asupra caruia se aplica o prelucrare. Pentru orice secventa din vector delimitata de indecsii i si j, i<j exista o valoare p astfel incat prin prelucrarea secventelor :

x_i, x_i+1, x_i+2, x_i+3, …x_p si x_p+1, x_p+2, x_p+3, …x_j

se obtin solutiile corespunzatoare celor doua subsiruri care prin compunere conduc la obtinerea solutiei prelucrarii secventei:

x_i, x_i+1, x_i+2, x_i+3, …x_j

Aplicatie:

Ne propunem sa determinan suma elementelor unui vector de intregi utilizand metoda Divide et Impera:

2

3

4

1

5

6

8

9

1

10

3

4

4

5

2

6

Se imparte vectorul in doi vectori:

2

3

4

1

5

6

8

9

1

10

3

4

4

5

2

6

Fiecare se dintre cei doi vectori se poate imparti in continuare in alti doi vectori:

2

3

4

1

5

6

8

9

1

10

3

4

4

5

2

6

La fel se procedeaza in continuare:

2

3

4

1

5

6

8

9

1

10

3

4

4

5

2

6

Apoi:

2

3

4

1

5

6

8

9

1

10

3

4

4

5

2

6

Dat fiind ca s-au obtinut secvente de vector de lungime 1, nu se mai realizeaza descompunerea.

Se compun solutiile subsecventelor si se determina solutiile corespunzatoare:

2

+

3

4

+

1

5

+

6

8

+

9

1

+

10

3

+

4

4

+

5

2

+

6

Si in continuare:

5

+

5

11

+

17

11

+

7

9

+

8

Apoi:

10

+

28

18

+

17

La fel:

38

+

35

La sfarsit:

73

Iata o solutie de implementare:

#include<iostream.h>

#include<conio.h>

int v[20],n;

int divide(int li,int ls) // functia primeste ca parametric extremitatile unei secvente din vector

{int mij, d1 ,d2; //mijlocul, d1 si d2 retin sumele pe extr. Stanga respective dreapta

if(li!=ls) //algoritmul se autoapeleaza daca secventele au lungime mai mare de 1

{mij=(li+ls)/2;

d1=divide(li,mij);

d2=divide(mij+1,ls);

return d1+d2;

}

else

return v[li];

}

void main()

{clrscr();

cout<<"n=";

cin>>n;

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

{cout<<"v["<<i<<"]=";

cin>>v[i];}

cout<<"suma celor "<<n<<" elemente ale vectorului "<<divide(1,n);

getch();

}

Probleme propuse:

1. Sa se determine produsul a n numere intregi
2. Sa se determine maximul (minimul) a n numere intregi
3. Sa se determine cel mai mare divizor comun a n valori dintr-un vector
4. Sa se caute o valoare intr-un vector. Daca se gaseste se va afisa pozitia pe care s-a gasit, altfel se va afisa un mesaj.
5. Sa se caute o valoare intr-un vector ordonat crescator
6. Sa se numere cate valori sunt egale cu x dintr-un sir de numere intregi citite.