代码之家 › 专栏 › 技术社区 › Max Voisard

求最简基及其指数的乘积

logarithm javascript

Max Voisard · 技术社区 · 4 年前

给定一个乘积,我想找到最简化的基及其对应的指数。例如,343的乘积将产生7的基数和3的指数。如果某个产品返回多组基和指数,则只考虑最简单的基。例如,64的乘积将返回基数2和指数6,并消除基数4和指数3以及基数8和指数2的较高组合。

现在,我已经为这个场景编写了一个程序。然而,这似乎是相对非正统的,并且在给定的高数据下,可能需要很长时间来编译 product 指定了参数。有没有更好更有效的方法来编写函数,可能是使用对数?我似乎找不到关于这种编程问题的任何信息。

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 }

2 回复 | 直到 4 年前

CertainPerformance 4 年前

问题似乎归结为找到第一个划分乘积的数字(首先从尽可能低的数字开始),然后找到它划分的次数。

一个简单且比你的方法更有效的方法是从2开始,然后检查3,然后在接下来的每次迭代中增加2,直到达到乘积的平方根。这不是问题最效率很高,但它更好、更容易实现。

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 }

从素数列表开始,迭代它,而不是迭代所有奇数,如果你所受的约束允许的话,这会有所帮助。

Xavier B. 4 年前

我看不出更好的逻辑,但我能想到一些优化:

你应该让 i 从2点到 Math.max(2, Math.floor(Math.sqrt(product)))

不是从1开始,因为 Math.pow(1, <something>) 永远等于 1

没有正整数 N = Math.pow(a, b) 哪里 a 和 b 正整数是否大于 1. b> sqrt(N)

推荐文章

code-geek · Jquery根据单选按钮选择隐藏或显示文本字段

1 年前

Niobos · 如何/是否有方法使通用算法函数同时与同步和异步函数一起工作?

1 年前

Alex · 在轻量级中同时解构和不解构变量

1 年前

Ângelo Rigo · ReactJS映射:如何迭代[关闭]

1 年前

bairog · 从按属性筛选的对象数组字典中创建值数组

1 年前

KaiMcKiernan · 基于Math.random()的函数在另一个函数内不起作用[关闭]

1 年前

David Jeong · 浏览器不会为浏览器自动添加的某些标头发送CORS预检请求吗?

1 年前

user29519291 · 为不同的变量创建一个带有可重用Click函数的简单菜单

1 年前

user3472810 · Angular@Output/EventEmitter返回undefined

1 年前

lokiuucx · JS对象属性返回未定义,尽管对象属性应该有值

1 年前