Dado un producto, quiero encontrar la base más simplificada y su correspondiente exponente. Por ejemplo, un producto de 343 produciría una base de 7 y un exponente de 3. Si un determinado producto arroja múltiples conjuntos de bases y exponentes, solo se considera la base más simple. Por ejemplo, el producto de 64 devolvería una base de 2 y un exponente de 6, y eliminaría las combinaciones superiores de base 4 y exponente 3 y base 8 y exponente 2.
Ahora, ya he escrito un programa que funciona para este escenario. Sin embargo, parece ser relativamente poco ortodoxo y puede llevar mucho tiempo compilarlo dados los números altos para el argumento del product especificado. ¿Existe una forma mejor y más eficiente de escribir la función, posiblemente usando logaritmos? Parece que no puedo encontrar nada sobre este tipo de problema de programación.
function findBaseAndExponent(product) { product = Math.round(product); var base = 0; var exp = 0; var abort = false; for (var i = 1; i <= product && !abort; i++) { for (var j = 1; j <= product && !abort; j++) { const currProd = Math.pow(i, j); if (currProd == product) { base = i; exp = j; abort = true; } if (currProd > product){ break; } } } if (base == product && exp == 1) { base = "N/A"; exp = "N/A"; } return { "base": base, "exponent": exp }; } console.log(findBaseAndExponent(343)); // Output: { base: 7, exponent: 3 } console.log(findBaseAndExponent(64)); // Output: { base: 2, exponent: 6 } console.log(findBaseAndExponent(41)); // Output: { base: N/A, exponent: N/A }El problema parece reducirse a encontrar el primer número que divide el producto (comenzando primero con el menor posible), y luego encontrar cuántas veces lo hace.
Una forma simple y más eficiente que la tuya sería comenzar en 2, luego verificar 3, luego aumentar en 2 para cada iteración siguiente, hasta llegar a la raíz cuadrada del producto. No es el más eficiente, pero es mejor y más fácil de implementar.
const isDivisible = (a, b) => Number.isInteger(a / b); const log = (n, base) => Math.log(n) / Math.log(base); const findExponent = (product, base) => ({ base, exponent: Math.round(log(product, base)) }); function findBaseAndExponent(product) { if (isDivisible(product, 2)) return findExponent(product, 2); for (let i = 3, limit = Math.floor(Math.sqrt(product)); i <= limit; i += 2) { if (isDivisible(product, i)) return findExponent(product, i); } return { base: null, exponent: null }; } console.log(findBaseAndExponent(343)); // Output: { base: 7, exponent: 3 } console.log(findBaseAndExponent(64)); // Output: { base: 2, exponent: 6 } console.log(findBaseAndExponent(41)); // Output: { base: N/A, exponent: N/A }Comenzar con una lista de números primos e iterar sobre ella en lugar de iterar sobre todos los números impares ayudaría, si eso lo permiten las restricciones bajo las que se encuentra.
No veo una lógica mejor, sin embargo, puedo pensar en algunas optimizaciones:
i pase de 2 a Math.max(2, Math.floor(Math.sqrt(product))) No de 1 porque Math.pow(1, <something>) siempre será igual a 1
no hay un entero positivo N = Math.pow(a, b) donde a y b son enteros positivos mayores que 1 con b > sqrt(N)
Este código comprueba si un número es la base de un producto, no un factor del producto. Verá, para un producto como 42, no hay una base ni un exponente que coincidan, pero habrá números enteros divisibles que entren, como 2, 6, 7 y 21. No nos importa ninguno de esos factores. siendo un número entero, sino más bien una base que se evalúa como un número entero.
var isRoot = function (n, root) { return Number.isInteger(getBase(n, root)); }; const getBase = (n, root) => parseFloat(Math.pow(n, 1 / root).toFixed(3)); const findExponent = (product, exponent) => ({ base: getBase(product, exponent), exponent }); function findBaseAndExponent(product) { for (var i = Math.ceil(Math.sqrt(product)); i >= 2; i--) { if (isRoot(product, i)) return findExponent(product, i); } return { base: null, exponent: null }; } console.log(findBaseAndExponent(343)); // Output: { base: 7, exponent: 3 } console.log(findBaseAndExponent(64)); // Output: { base: 2, exponent: 6 } console.log(findBaseAndExponent(42)); // Output: { base: null, exponent: null }