如何有效地确定完美功率？

Question

挑战：https://www.codewars.com/kata/57c7930dfa9fc5f0e30009eb/train/javascript

嗨，我已经尝试这个问题好几个小时了，但不幸的是我的代码花了太长时间才能通过：

function closestPower(num) {
  num = Math.floor(num);
  if (num < 4) return 4;
// check if input is perfect power
  let base = 2;
  while (base < 10) {
  let exponent = Math.trunc(getBaseLog(base , num));
  if ( Math.pow(base, exponent)  === num ) { 
  return num;
}
base++;
  }
// check for upper and lower
  base = 2;
  const verifyObj = {upper:null, lower:null}; // verify
  let upperPower = num + 1;
  let lowerPower = num - 1;
  while (!verifyObj.upper || !verifyObj.lower)
  {
    // no perfect power
    if (lowerPower <= 2 ) verifyObj.lower = "Not found";
    if (upperPower === Infinity ) verifyObj.upper = "Not found";
  // up til base 9
  if (base === 10) { 
    if (!verifyObj.upper) upperPower++;
    if (!verifyObj.lower) lowerPower--;
    base = 2;
  }
// upper
if (!verifyObj.upper) {
  let exponent = Math.trunc(getBaseLog(base , upperPower));
  if ( Math.pow(base, exponent)  === upperPower ) { 
  verifyObj.upper = upperPower;
}
}
// lower
if (!verifyObj.lower) { 
  let exponent = Math.trunc(getBaseLog(base , lowerPower));
  if ( Math.pow(base, exponent)  === lowerPower ) { 
  verifyObj.lower = lowerPower;
}
}
base++;
  }
  console.log(verifyObj) // {upper:64, lower: 49}
  // nearest power
  if ((upperPower - num) < (num - lowerPower)) { 
    return upperPower;
  }
  else return lowerPower;
}

closestPower(56.5); // 49

function getBaseLog(x, y) {
  return Math.log(y) / Math.log(x);
}

我意识到我的代码是多余的，因为我只需要知道“基数”和“指数”是否大于 1 即可确定完美的幂。有什么公式或想法吗？

Answer 1

一些问题：

没有理由不让base大于等于10
在每个增量尝试 upperPower 需要太多迭代。到下一个幂的距离可能会比较大

我建议使用以下算法：

令试的指数从2开始，然后递增1，计算出对应的底数是多少。可以通过将 n 提高到反指数（即 1/exp）来找到实底。然后只有 2 个有趣的整数基要考虑：向下和向上舍入。

这是一个实现：

function closestPower(n) {
    if (n <= 6) return 4;
    let result = -1;
    let closest = n;
    for (let factor, exp = 2; (factor = n ** (1 / exp)) > 1.9; ++exp) {
        let above = Math.ceil(factor);
        for (let intfactor = Math.floor(factor); intfactor <= above; intfactor++) {
            let power = intfactor ** exp;
            let diff = Math.abs(power - n);
            if (diff == 0) return n;
            if (diff < closest || diff == closest && power < n) {
                closest = diff;
                result = power;
            }
        }
    }
    return result;
}

// Some tests:
const tests = [
    [0, 4], [9, 9], [30, 32], [34, 32], [56.5, 49],
    [123321456654, 123321773584]
];
for (let [n, expected] of tests) {
    let result = closestPower(n);
    if (result === expected) continue;
    console.log(`closestPower(${n}) returned ${result}, but expected ${expected}`);
}
console.log("all tests done");

Answer 2

这是我的算法首先，我将从小于 n 的基数中获取指数，然后我将循环的当前基数与 n 添加，然后获取基数对数。

function closestPower(n) {
  if(n < 4) return 4
  let closest = []
  let base = 2
  while(base < n) {
    const exponent = Math.floor(Math.log(n + base) / Math.log(base))
    const power = Math.pow(base,exponent)
    if(exponent === 1) break
    if(power === n) return n
    closest.push(power)
    base++
  }
  return closest.reduce((prev, curr) => (Math.abs(curr - n) < Math.abs(prev - n) ? curr : prev))
}

console.log(closestPower(0))
console.log(closestPower(9))
console.log(closestPower(30))
console.log(closestPower(34))
console.log(closestPower(56.5))
console.log(closestPower(123321456654))

如何有效地确定完美功率？

How to determine a Perfect Power efficiently?

javascript

algorithm

math