elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: ¿Eres nuevo? ¿Tienes dudas acerca del funcionamiento de la comunidad? Lee las Reglas Generales


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Sumar los elementos de un vector con DyV
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Sumar los elementos de un vector con DyV  (Leído 2,003 veces)
Gauss

Desconectado Desconectado

Mensajes: 6


Ver Perfil
Sumar los elementos de un vector con DyV
« en: 17 Diciembre 2018, 05:45 am »

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:
#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.



En línea

K-YreX
Moderador
***
Desconectado Desconectado

Mensajes: 1.008



Ver Perfil
Re: Sumar los elementos de un vector con DyV
« Respuesta #1 en: 17 Diciembre 2018, 06:06 am »

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. :-X


En línea

Código
  1. cout << "Todos tenemos un defecto, un error en nuestro código" << endl;
dijsktra

Desconectado Desconectado

Mensajes: 110


Mr Edsger Dijsktra (Tribute to)


Ver Perfil
Re: Sumar los elementos de un vector con DyV
« Respuesta #2 en: 17 Diciembre 2018, 21:12 pm »

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. :-X
Hola. Creo que ese no es el problema.

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

Código
  1. int sumaDyV( int *vec, int inicio, int fin ) {
  2.    if( inicio == fin ) {
  3.        return vec[inicio];
  4.    }
  5.    const int half = (inicio + fin)/2;
  6.    return sumaDyV(vec, inicio, half) + sumaDyV( vec, half +1, fin);
  7. }

Ahora queda:

Código:
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
  1. #include <iostream>
  2. using namespace std;
  3. int sumaDyV( const int *vec, const int inicio, const int fin );
  4.  
  5. int main() {
  6.    int N;
  7.    cin>>N;
  8.    int *vec = new int[N];
  9.    for(int i = 0; i<N;i++)   cin>>vec[i];
  10.    cout<<sumaDyV( vec, 0, N )<< endl;
  11.    delete[] vec;
  12.    return 0;
  13. }
  14.  
  15. // Inmersion:
  16. // P :   0 <= i <= j <= N
  17. // Q :   n = \sum k : i<= k < j : V[k];
  18. int sumaDyV( const int *V, const int i, const int j ) {
  19.    if ( i == j )  return 0;
  20.    if ((j - i) == 1)  return V[i];    
  21.    const int half = (i + j)/2;
  22.    return sumaDyV(V, i, half) + sumaDyV( V, half, j);
  23. }


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!
En línea

Si la depuración es el proceso de eliminar fallos en el software, entonces programar debe ser el proceso de ponerlos dentro. (Edsger Dijsktra)
Gauss

Desconectado Desconectado

Mensajes: 6


Ver Perfil
Re: Sumar los elementos de un vector con DyV
« Respuesta #3 en: 17 Diciembre 2018, 23:07 pm »

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:
#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!

En línea

dijsktra

Desconectado Desconectado

Mensajes: 110


Mr Edsger Dijsktra (Tribute to)


Ver Perfil
Re: Sumar los elementos de un vector con DyV
« Respuesta #4 en: 18 Diciembre 2018, 10:15 am »

...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:
...
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:
( (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) !

« Última modificación: 18 Diciembre 2018, 10:16 am por dijsktra » En línea

Si la depuración es el proceso de eliminar fallos en el software, entonces programar debe ser el proceso de ponerlos dentro. (Edsger Dijsktra)
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines