4

No puedo entender la lógica para plantear el caso base y recursivo para el ejercicio. alguno me puede ayudar? el ejercicio dice:

Dada la siguiente definición, proponga un planteo recursivo para computar la suma de productos de una secuencia S de n números enteros. Definimos la suma de productos de S como:

d1*dn+d2*dn-1+ ... +d(n/2)+d(n/2)+1 cuando n es par
d1*dn+d2*dn-1+ ... +d(n/2)+1 cuando n es impar

Por ej:

para n=6 y S = 10 4 3 5 7 8 entonces M = 10*8+4*7+3*5
para n=7 y S = 10 4 3 5 7 8 9 entonces M = 10*9+4*8+3*7+5
6
  • podrías mejorar la redacción de la definición de la "suma de productos de s", no comprendo bien como es que se deben generar los resultados :/ Commented el 11 sept. 2017 a las 21:01
  • @ArieCwHat n representa las posiciones mientras d el valor de la posición de manera que si n=6 entonces debes de respetar el patrón (d1*dn)+(d2*dn-1)+.... para los seis valores que hay por tanto debe haber 6 operaciones de multiplicación y dos sumas.
    – Legna
    Commented el 11 sept. 2017 a las 21:11
  • Hola, muchas gracias por responder. Entendí lo que me esta pidiendo el ejercicio. lo que no se me ocurre es como plantearlo para empezar a programarlo. Como organizar para multiplicar el 1er numero de la secuencia con el ultimo + el 2do numero de la secuencia con el penúltimo y asi hasta terminar la secuencia. Commented el 11 sept. 2017 a las 21:24
  • Ahm, con los paréntesis entendí de inmediato, está muy fácil :P gracias @RafaelAngelRamirezEstrada Commented el 11 sept. 2017 a las 21:34
  • @ArieCwHat puse 6 operaciones de multiplicación y eran tres xP.
    – Legna
    Commented el 11 sept. 2017 a las 21:36

4 respuestas 4

2

Una solución para este problema luce mas o menos así:

public class Main {
    public static void main(String[] args) {
        int[] ejemplo1 = new int[]{10, 4, 3, 5, 7, 8};
        int[] ejemplo2 = new int[]{10, 4, 3, 5, 7, 8, 9};

        // siempre empieza en 0
        System.out.println(calcular(ejemplo1, 0));
        System.out.println(calcular(ejemplo2, 0));
    }

    public static int calcular(int[] secuencia, int indice) {
        int ultimoIndice = secuencia.length - 1;

        // esto es como un espejo, suma la contraparte
        int suma = secuencia[indice] * secuencia[ultimoIndice - indice];

        // comprobamos que estemos en el medio de la secuencia
        if (indice == ultimoIndice / 2) {
            // en caso de impar la suma es incorrecta, entonces solo se envia
            // el elemento en el medio
            if (secuencia.length % 2 == 0) {
                return suma;
            } else {
                return secuencia[indice];
            }
        }

        // en los demás casos siempre se cumple que se envía esto sea par o no
        return suma + calcular(secuencia, indice + 1);
    }
}

Como mencionaste en los comentarios, sin arreglos es mas difícil resolver este problema. Puedes usar un String para mantener la lista de elementos y recorrerlos para tener los números, pero eso es mucho mas código :(

2

Una manera de resolverlo sería

  • Inicializar un índice en el principio de la secuencia, llamemosle begin
  • Inicializar un índice en el fin de la secuencia llamemosle end
  • Incrementar en 1 begin y decrementar en 1 end realizando la multiplicación entre sus elementos
  • Realizar la llamada recursiva acumulando el resultado del paso anterior con el de invocar el metodo con una secuencia mas pequeña (sin incluir los dos extremos marcados por los indices)

Basicamente begin se movera desde la posicion 0 hasta la posición n/2+1 en caso de ser n impar y n/2 en caso de ser par y end hará el movimiento análogo desde el final del array.

Los índices iran "acercandose" hasta que coincidan (largo impar) o sean "vecinos" (largo par)

public Integer calcularSecuencia(Integer[] secuencia, int n){
    if(n <= secuencia.length){
        return calcularSecuencia(secuencia, 0, n-1);
    }
    return null;
}


public Integer calcularSecuencia(Integer[] secuencia, int begin, int end){
    if(begin == end-1) {
        // caso base para largo par
        return secuencia[begin] * secuencia[end];
    }else if(begin == end){
        // caso base para largo impar
        return secuencia[begin]; // o end, es un elemento y ambos indices estan en la misma posicion
    }else{
        // paso recursivo
        return (secuencia[begin] * secuencia[end]) + calcularSecuencia(secuencia, ++begin, --end);
    }
}

La primera condición corresponde al caso base para largo par, puesto que ambos índices quedarán contiguos.

La segunda condición para largo impar, donde ambos índices se moveran incrementando de a una posición hasta llegar al elemento medio del array.

Otra forma de implementarlo sería definir dos métodos recursivos, uno para largo par y otro para impar y separar desde un principio, según el largo de la secuencia, a cual de ellos vamos a invocar. Esta opción es un poco mas clara ya que sólo hay que tener en cuenta el caso base para uno de los casos.

public Integer calcularSecuencia(Integer[] secuencia, int n){
        if(n <= secuencia.length){
            if(n % 2 == 0){
                return calcularSecuenciaPar(secuencia, 0, n-1);
            }else{
                return calcularSecuenciaImpar(secuencia, 0, n-1);

            }
        }
        return null;
    }


    public Integer calcularSecuenciaPar(Integer[] secuencia, int begin, int end){
        if(begin == end-1) {
            // caso base para largo par
            return secuencia[begin] * secuencia[end];
        }else{
            // paso recursivo
            return (secuencia[begin] * secuencia[end]) + calcularSecuenciaPar(secuencia, ++begin, --end);
        }
    }

    public Integer calcularSecuenciaImpar(Integer[] secuencia, int begin, int end){
        if(begin == end){
            // caso base para largo impar
            return secuencia[begin];
        }else{
            // paso recursivo
            return (secuencia[begin] * secuencia[end]) + calcularSecuenciaImpar(secuencia, ++begin, --end);
        }
    }

Invocaciones:

Integer [] secuencia = new Integer[7]{10, 4, 3, 5, 7, 8, 9};    

System.out.println(calcularSecuencia(secuencia, 6)); // 123
System.out.println(calcularSecuencia(secuencia, 7)); // 148
2
  • Muchas gracias por responder de una forma tan detallada. Muy clara la forma en que lo resolviste. Tengo que ver si lo puedo modificar para que no use arrays, estoy en un nivel inicial. No creo que cuando tenga que rendir el examen me permiten el uso de arrays ya que todavía no los han explicado. Commented el 11 sept. 2017 a las 21:36
  • De nada. El problema es mas sencillo e intuitivo de resolver iterativamente, simplemente recorriendo la secuencia hasta que los indices coincidan (par) o se peguen (impar). De todas formas entiendo que tu pregunta apunta a utilizar un algoritmo recursivo. Sobre lo que planteas en el comentario, necesitas una estructura donde almacenar y recorrer la secuencia, que estructuras has visto hasta el momento? Commented el 11 sept. 2017 a las 21:57
2

Aqui te va otra opción. Trate de hacer que el código quedará más claro y que fuera independiente del tamaño del arreglo que le pases.

En tus comentarios ponias que lo querías hacer sin arreglos pero la verdad me parece muy incomodo. Tendría que ser separando una cadena.

public class Re {
//ESTA CLASE LA CREAS DESDE UN NUEVO FICHERO. 

public void operacion(int[]n){
    //AQUI INICIA LA OPERACION
    recursividad(n, 0,  n.length-1,  0 );
    // n es el arreglo de números que quieres sumar. 
    // 0 Es el contadorPositivo que ira sumando uno para recorrer desde la izquierda
    // n.length-1 Es el tamaño del arreglo. (-1 porque empieza en 0
    // -- y si tienes 6 números el arreglo va de 0 a 5, pero el lenght te 
    //retorna 6!! Que mal!!)
    // 0 es el total inicializado. 
}

//ESTA FUNCIÓN ES RECURSIVA PARA LOS PARES E IMPARES.
public void recursividad(int[] entero, int contadorPositivo, int contadorNegativo, int total){
    //COMPARAMOS LOS DOS CONTADORES. MIENTRAS EL NEGATIVO SEA MAYOR QUE EL 
    //POSITIVO QUIERE DECIR QUE NO HEMOS LLEGADO AL CENTRO DEL ARREGLO.
    if (contadorPositivo<contadorNegativo) {
        //EXTRAEMOS LOS NUMEROS. EL PRIMERO(d1) Y EL ULTIMO(dn-1)
        int d = entero[contadorPositivo];
        int dn_1 = entero[contadorNegativo];
    System.out.println("(+)"+contadorPositivo+"(-)"+contadorNegativo);
        // REALIZAMOS LA OPERACION DE MULTIPLICACIÓN Y LA SUMAMOS AL TOTAL.
        total += (d*dn_1);
        //AQUI HAY UNA CLAVE DE RECURSIVIDAD POR QUE EL TOTAL LO PASAMOS 
        //SIEMPRE A LA SIGUIENTE RECURSIVIDAD QUE LLAMEMOS JUNTO CON LA
        // ADICION DE 1  AL contadorPositivo y SUSTRACCION de 1 A 
        //   contadorNegativo.

        contadorPositivo++;
        contadorNegativo--;
        //ESTE ES EL MEOLLO DEL ASUNTO. VOLVEMOS A LLAMAR ESTA MISMA FUNCIÓN
        // CON LOS VALORES MODIFICADOS PARA QUE SE EJECUTEN LAS OPERACIONES
        // RECURSIVAS. SI NO MODIFICARAMOS LOS VALORES TENDRIAMOS UN BUCLE 
        //INFINITO ASI QUE PARA PODER HACER UNA FUNCIÓN RECURSIVA HAY QUE 
        //TENER VALORES QUE CAMBIEN Y QUE PUEDAN SER COMPARADOS SUS CAMBIOS.
        // ES DE NOTAR QUE PASAMOS LOS MISMOS PARÁMETROS UNA Y OTRA VEZ. 
        recursividad(entero, contadorPositivo, contadorNegativo, total);

    }else{
        //CUANDO ALCANZAMOS EL CENTRO EL contadorPositivo ES MAYOR QUE 
        //contadorNegativo y ya no es necesario volver a llamar  a la 
        //fución.
        // SI EL ARREGLO ES PAR ENTONCES TOMAMOS EL SIGUIENTE NUMERO QUE 
        //SEÑALA CONTADOR POSITIVO Y LO SUMAMOS. 

        if ((entero.length-1)%2==0) {
            total+= entero[contadorPositivo];
        }
    }

    System.out.println(total);

   }

 }
0

Al final lo pude resolver. Se me ocurrio subirlo por si alguien tiene un problema similar.

public static int sumaProd(int n){ // n establece la cantidad de numeros a leer por consola
        if (n % 2 == 0)
            return sumaProdPar(n,n/2);
        else
            return sumaProdImp(n,(n/2)+1);
}

private static int sumaProdImp(int n, int m){
    int num1,num2,numR;
    if (n == m) 
        return  ES.leerEntero();
    else {
        num1=ES.leerEntero(); //ES.leerEntero() le asigna a num1 el valor de un entero leido por consola.
        numR=sumaProdImp(n-1,m);
        num2=ES.leerEntero();

    return numR+num2*num1;   
    }
}

private static int sumaProdPar(int n, int m){
    int num1,num2,numR;
    if (n == m){
        return 0; 
    } else {
        num1=ES.leerEntero();
        numR=sumaProdPar(n-1,m);
        num2=ES.leerEntero();
    return numR+(num1*num2);   
    }
}

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.