如何有效地确定完美力量

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);
}

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

Answer 1

一些问题：

• 没有理由不允许base为10或10以上
• 尝试在每个增量使用upperPower会花费太多的迭代。与下一个大国的距离可能相当大

我建议使用以下算法：

让要尝试的指数从2开始，然后递增1。计算哪个可以是相应的基数。实基数可以通过将n提高到逆指数(即1/exp(来找到。那么只有两个有趣的整数基数需要考虑：向下和向上取整。

这里有一个实现：

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))