Título: Sumar los elementos de un vector con DyV Publicado por: Gauss 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> Gracias. Título: Re: Sumar los elementos de un vector con DyV Publicado por: K-YreX 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 Título: Re: Sumar los elementos de un vector con DyV Publicado por: dijsktra en 17 Diciembre 2018, 21:12 pm Para que funcione tienes que distinguir 3 casos (te falta 1): Hola. Creo que ese no es el problema.- 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 El problema es que no está computando bien el punto medio. Código
Ahora queda: Código: Dimension del vector: 5 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
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! Título: Re: Sumar los elementos de un vector con DyV Publicado por: Gauss 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> Voy a tener en cuenta usar el [i,...,j) con if ( i == j ) return 0; para subsegmentos. Gracias! Título: Re: Sumar los elementos de un vector con DyV Publicado por: dijsktra 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: A ti! Código: ... Gracias! 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) ! |