 Autor
|
Tema: Sumar los elementos de un vector con DyV (Leído 1,991 veces)
|
Gauss
 Desconectado
Mensajes: 6
|
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 #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
|
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. 
|
|
|
|
|
En línea
|
cout << "Todos tenemos un defecto, un error en nuestro código" << endl;
|
|
|
dijsktra
Desconectado
Mensajes: 110
Mr Edsger Dijsktra (Tribute to)
|
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. 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: 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: #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!
|
|
|
|
|
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
Mensajes: 6
|
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: #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
Mensajes: 110
Mr Edsger Dijsktra (Tribute to)
|
...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: ...
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 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)
|
|
|
|
| Mensajes similares |
|
Asunto |
Iniciado por |
Respuestas |
Vistas |
Último mensaje |
|
|
|
[Ayuda]Sumar elementos de un listBox y mostrarlos en un textBox
Programación C/C++
|
Beaustyle
|
1
|
7,723
|
16 Junio 2013, 00:55 am
por aguml
|
|
|
|
Sumar los elementos de una fila de una matriz en Pythong
Dudas Generales
|
Matinegro
|
1
|
2,814
|
10 Noviembre 2013, 20:41 pm
por crazykenny
|
|
|
|
[Ruby] Sumar elementos de un array
Scripting
|
ka0s
|
2
|
8,805
|
25 Noviembre 2013, 20:32 pm
por ka0s
|
|
|
|
Duda, sumar elementos en torno a un punto de la matriz en C
Programación C/C++
|
MrDude
|
1
|
2,635
|
8 Julio 2015, 10:19 am
por vangodp
|
|
|
|
¿Cómo sumar los primeros elementos de tres listas dentro de una lista?
Scripting
|
sebastiancorrea
|
2
|
2,954
|
19 Abril 2019, 04:32 am
por yuimugi912
|
 |
