Suma vector

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>

#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];

}

int main()

{

 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);

}