4

El problema es el siguiente; dado un numero n (entero positivo <100) este se descompone en números no iguales que sumados den como resultado n y cuya multiplicación sea la mayor posible.

Ejemplos:

  • n=5 resultado 6 porque 2 x 3=6
  • n=8 resultado 15 porque 5 x 3 = 15
  • n=10 resultado 30 porque 2 x 3 x 5 = 30
  • n=15 resultado 144 porque 2 x 3 x 4 x 6 = 144

Para obtener la mayor multiplicación se deben ir descomponiendo los números pero de igual forma estos no pueden estar repetidos.

Esto es lo que he hecho:

La función esPrimo() me regresa true o false si el numero que se le pasa es primo, la utilizo para saber si puedo dividir el numero en mas sumandos.

La función dividirNumero() divide el numero en sus sumandos y regresa la mayor multiplicación de entre estos.

Y la función maximumProduct() es la que debería llamarse recursivamente para seguir dividiendo los números, y comprobar que no se repitan, pero esta parte no se como hacerla.

<!--   MIRAR ESTA FUNCION -->

function maximumProduct(n) {
    let numeros = dividirNumero(n)
    let multiplicadores = []
    let aSimplificar = [] // aqui estan los que se pueden simplificar para hallar la mayor multiplicacion
    numeros.map(n => {
        return esPrimo(n) ? multiplicadores.push(n) : aSimplificar.push(n)// esta parte es la que se pudiera llamar recursiva
    })
    console.log(aSimplificar);
    return multiplicadores.reduce((a, b) => a * b)
}

function dividirNumero(n) {
    let arr = []
    let mayorMultiplicacion = 0
    let par = []
    for (let i = 1; i < n; i++) {
        arr.push(i)
    }

    for (let i = 0; i < arr.length - 1; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[i] + arr[j] == n) {
                if (arr[i] * arr[j] > mayorMultiplicacion) {
                    mayorMultiplicacion = arr[i] * arr[j]
                    par.pop()
                    par.push([arr[i], arr[j]])
                }
            }
        }
    }
    return par[0]
}

function esPrimo(x) {
    const primos = [2, 3, 7, 11, 13, 17, 19, 23, 29];
    if (x < 2) {
        return false
    } else if (primos.indexOf(x) > -1) {
        return true
    } else if (primos.some(primo => x % primo == 0)) {
        return false
    } else {
        if (x <= primos[primos.length - 1] * 2) {
            return true
        } else {
            let test = true;
            for (let i = primos[primos.length - 1] + 1; i <= Math.floor(x / 2); i++) {
                if (x % i === 0) {
                    test = false;
                    break;
                }
            }
            return test;
        }
    }
}


console.log(maximumProduct(20));

2
  • Cual es la pregunta o el problema? Commented el 27 sept. 2019 a las 22:14
  • como seguir descomponiendo sin que se repitan los numeros
    – RazerJs
    Commented el 27 sept. 2019 a las 22:20

1 respuesta 1

4

Una alternativa para resolver el problema podría ser recorrer las opciones como un árbol con múltiples nodos.

La idea es la siguiente:

Tomando como ejemplo el número 10.

Los primeros posibles valores de la serie son los números entre 2 y n-2.

2,3,4,5,6,7,8

No se toman en cuenta el 1 y el n-1 (9) ya que su producto es incluso menor que el numero original.

Luego los próximos valores de la serie se dan según el primer valor, dichos valores sumados al anterior deberán ser menores o iguales a n, y serán números mayores a los números anteriores, por tanto no serán iguales:

para 2: 3,4,5,6,7,8
para 3: 3,4,5,6,7
para 4: 5
para 5: -
...
para 8: -

En caso de no existir números que se puedan agregar a la serie, se verifica si la sumatoria es igual a n, de ser así se agrega a la lista de posibles soluciones, de otro modo se descarta.

En el anterior nivel no se agrego ninguna serie.

Luego se continua con el siguiente nivel:

para 2,3: 4,5
para 2,4: -
...
para 2,8: -
para 3,4: -
para 3,5: -
...
para 3,7: -

En este se agregan 2,8 y 3,7

y luego el próximo nivel queda así;

2,3,4: -
2,3,5: -

En este nivel se agrega el 2,3,5.

Por ultimo se hace la multiplicatoria de cada serie para hallar la que generé el producto mas grande:

2 * 8 = 16
3 * 7 = 21
2 * 3 * 5 = 30 <= 

y entonces la que se muestra es la serie con el producto mas grande.

El código queda funcionando de la siguiente forma:

var posibles;

function maxApoyo(n, r, a) { 
  for(var i=r+1; i<n-1 ;i++){  
    var suma = [...a,i].reduce((a,s)=>a+s); 
    suma==n ? posibles.push([...a,i]) : suma<n ? maxApoyo(n, i, [...a,i]) : 0 
  }
}

function maximumProduct(n) {
  var max=0;
  var pmax=0;
  posibles = [];
  maxApoyo(n, 1, [], posibles);
  // console.log(posibles);
  for(p in posibles){
    mul = posibles[p].reduce((a,m)=>a*m);
    if(mul>max){
      pmax=p;
      max=mul;
    }
  }
  return `n = ${n} resultado ${max} por que ${posibles[pmax].join('*')}=`+max;
}

console.log(maximumProduct(5));
console.log(maximumProduct(8));
console.log(maximumProduct(10));
console.log(maximumProduct(15));
console.log(maximumProduct(29));
console.log(maximumProduct(36));
console.log(maximumProduct(59));
.as-console-wrapper { max-height: 100% !important; top: 0; }

En este código se colocan las posibles soluciones en el array posibles, luego la función maxApoyo() es una función recursiva que simula el recorrido de un árbol múltiple, y la función maximumProduct() verifica la serie mas optima y muestra el resultado.

Espero que este aporte sea de utilidad para entender como funcionan los algoritmos con arboles y ayude a resolver problemas semejantes, saludos.

3
  • Disculpa si no agregue mas información sobre la relación del problema con los algoritmos con arboles, tengo pensado agregar gráficos para hacer mas entendible la solución. Commented el 28 sept. 2019 a las 1:57
  • 1
    Muchas gracias como siempre @the-breaker... encontrastes una mejor solucion al problema
    – RazerJs
    Commented el 28 sept. 2019 a las 17:27
  • @IsraelGonzález de nada. Commented el 28 sept. 2019 a las 17:29

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.