Sumar los elementos de un vector con DyV

[Gauss]

Hola, andaba con un problema corto y quería ver si alguien me podía ayudar.
La cuestión es que tengo que sumar todos los elementos de un vector cualquiera usando la técnica divide y vencerás.
Yo estuve haciendo este código pero tengo problemas con los índices inicio y fin

Código [Seleccionar] Expandir


#include <iostream>
#include <cstdlib>
using namespace std;
int sumaDyV( int *vec, int inicio, int fin );

int main() {
    int longitud;
    cout<<"Dimension del vector: ";
    cin>>longitud;
    int *vec = new int[longitud];
    for(int i = 0; i<longitud;i++) {
        cout<<"\nNumero en la posicion "<<i<<": ";
        cin>>vec[i];
    }
    cout<<"\nResultado: "<<sumaDyV( vec, 0, longitud-1 );
    delete[] vec;
    return 0;
}

int sumaDyV( int *vec, int inicio, int fin ) {
    if( inicio == fin ) {
        return vec[inicio];
    }
    return sumaDyV(vec, inicio, fin/2) + sumaDyV( vec, (fin/2) +1, fin);
}

Hay veces en las que el índice de inicio es mayor al del fin, a causa de la división, cuando le pongo algún +1 para que eso no pase el problema está en otros índices.
Gracias.

[K-YreX]

Para que funcione tienes que distinguir 3 casos (te falta 1):
- Si inicio y fin son iguales -> return v[inicio]
- Si la diferencia entre inicio y fin es 1 -> return sumaDyV(v, inicio, inicio) + sumaDyV(v, fin, fin)
- Si la diferencia es mayor que 1 -> return sumaDyV(v, inicio, fin/2) + return sumaDyV(v, fin/2+1, fin)
Suerte.

[dijsktra]

Para que funcione tienes que distinguir 3 casos (te falta 1):
- Si inicio y fin son iguales -> return v[inicio]
- Si la diferencia entre inicio y fin es 1 -> return sumaDyV(v, inicio, inicio) + sumaDyV(v, fin, fin)
- Si la diferencia es mayor que 1 -> return sumaDyV(v, inicio, fin/2) + return sumaDyV(v, fin/2+1, fin)
Suerte.

Hola. Creo que ese no es el problema.

El problema es que no está computando bien el punto medio.

Código (c) [Seleccionar] Expandir

int sumaDyV( int *vec, int inicio, int fin ) {
    if( inicio == fin ) {
        return vec[inicio];
    }
    const int half = (inicio + fin)/2;
    return sumaDyV(vec, inicio, half) + sumaDyV( vec, half +1, fin);
}

Ahora queda:

Código [Seleccionar] Expandir

Dimension del vector: 5

Numero en la posicion 0: 2

Numero en la posicion 1: 2

Numero en la posicion 2: 2

Numero en la posicion 3: 2

Numero en la posicion 4: 3

Resultado: 11

Por cierto, que te recomiendo usar para subsegmentos el convenio [i..j) , semiabierto por la derecha, en vez de [i..j-1], cerrado por los dos lados, que es el que usas. Es más inmediato a la lectura de C, y permite valorar la longitud del segmento con la simple diferencia (j-i), contra las más compleja ((j-1)-i+1).
(Además, es legítimo preguntar por la suma de ls elements del vector vacío)


Lo pongo según mi versión:

Código (c) [Seleccionar] Expandir

#include <iostream>
using namespace std;
int sumaDyV( const int *vec, const int inicio, const int fin );

int main() {
    int N;
    cin>>N;
    int *vec = new int[N];
    for(int i = 0; i<N;i++)   cin>>vec[i];
    cout<<sumaDyV( vec, 0, N )<< endl;
    delete[] vec;
    return 0;
}

// Inmersion:
// P :   0 <= i <= j <= N
// Q :   n = \sum k : i<= k < j : V[k];
int sumaDyV( const int *V, const int i, const int j ) {
    if ( i == j )  return 0;
    if ((j - i) == 1)  return V[i];   
    const int half = (i + j)/2;
    return sumaDyV(V, i, half) + sumaDyV( V, half, j);
}


Ah! yo no me preocuparía de hacer "friendly" la entrada - salida... No están pedidiendo una aplicación, solo la exhibición de un algoritmo!

[Gauss]

Muchas gracias por responder!
Claro es verdad, estaba sacando mal el punto medio, como dijo dijsktra. Para la primer división sirve pero para toda la segunda mitad de la primera división ya no. La forma correcta es la que mencionas, (inicio+fin)/2 para obtener el punto medio de cada subdivisión.
Con ese punto medio hice la forma propuesta por YreX-DwX, quedando muy similar a como estaba el programa al inicio, lo dejo abajo por las dudas:

Código [Seleccionar] Expandir


#include <iostream>
#include <cstdlib>
using namespace std;
int sumaDyV( int *vec, int inicio, int fin );

int main() {
    int longitud;
    cout<<"Dimension del vector: ";
    cin>>longitud;
    int *vec = new int[longitud];
    for(int i = 0; i<longitud;i++) {
        cout<<"\nNumero en la posicion "<<i<<": ";
        cin>>vec[i];
    }
    cout<<"\nResultado: "<<sumaDyV( vec, 0, longitud-1 );
    delete[] vec;
    return 0;
}

int sumaDyV( int *vec, int inicio, int fin ) {
    if( inicio == fin ) {
        return vec[inicio];
    }
    if( (fin - inicio) == 1) {
        return sumaDyV(vec, inicio, inicio) + sumaDyV( vec, fin, fin);
    }
    else {
        return sumaDyV(vec, inicio, (inicio+fin)/2) + sumaDyV( vec, ((inicio+fin)/2)+1, fin);
    }
}


Voy a tener en cuenta usar el [i,...,j) con if ( i == j )  return 0; para subsegmentos.
Gracias!

[dijsktra]

...Con ese punto medio hice la forma propuesta por YreX-DwX, quedando muy similar a como estaba el programa al inicio, lo dejo abajo por las dudas:

Código [Seleccionar] Expandir


...
int sumaDyV( int *vec, int inicio, int fin ) {
   if( inicio == fin ) {
       return vec[inicio];
   }
   if ( (fin - inicio) == 1)
  {
       return sumaDyV(vec, inicio, inicio) + sumaDyV( vec, fin, fin);
   }
   else {
       return sumaDyV(vec, inicio, (inicio+fin)/2) + sumaDyV( vec, ((inicio+fin)/2)+1, fin);
   }
}

Voy a tener en cuenta usar el [i,...,j) con if ( i == j )  return 0; para subsegmentos.
Gracias!

A ti!
No obstante, ahora el caso de  YreX-DwX es redundante, no es necesario. De tu forma, si

Código [Seleccionar] Expandir

( (fin - inicio) == 1)

Entonces el tamaño del subsegmento es 2, y consecuentemente en el caso recursivo se partirá en dos submitades. Sigue valiendo el cálculo del punto medio del caso general.

Una razón más para emplear el convenio  [i..j) !