typescript Pow(x,n)Leetcode -递归不起作用

utugiqy6  于 2023-03-04  发布在  TypeScript
关注(0)|答案(1)|浏览(79)

我已经看了这个输出很长时间了,我不知道为什么它是不正确的...正确的答案是1.13074,但是我得到的是1.06336,这是不正确的。有人看到其中的缺陷吗?
我正在实现pow(x,n),它返回x^n,但使用(x^n)^m = x^n*m的原则来加快运行速度。
代码

function getMiddleFactors(n: number): number[] {
    const factors = [];
    for(let i = 1; i <= n; i=i+1) {
        if(n%i===0) {
            factors.push(i);
        }
    }

    return [factors[Math.floor(factors.length/2) - 1], factors[Math.floor(factors.length/2)]]
}

function myPow(x: number, n: number): number {
    let answer = 1;
    const negative = n < 0;

    if(negative) {
        n = -n;
    }

    if(n < 20) {
        for(let i = 0; i < n; i=i+1) {
            answer = answer * x;
        }
    } else {
        const factors = getMiddleFactors(n);
        console.log(`Got the factors: ${factors}`)
       
        const inner = myPow(x, factors[0]);
        console.log(`Got the inner number ${x}^${factors[0]}: ${inner}`);

        answer = myPow(inner,factors[1]);
        console.log(`Got the answer for ${x}^${n} (${inner}^${factors[1]}): ${answer}`);
    }
    
    if(negative) {
        answer = 1/answer;
    }

    return answer
};

产出

Got the factors: 16,32
Got the inner number 1.00012^16: 1.0019217289680562
Got the factors: 4,8
Got the inner number 1.0019217289680562^4: 1.0077091025273281
Got the answer for 1.0019217289680562^32 (1.0077091025273281^8): 1.0633627729389192
Got the answer for 1.00012^1024 (1.0019217289680562^32): 1.0633627729389192
wko9yo5t

wko9yo5t1#

问题似乎是你没有区分 * 偶数 * 个因子(您的代码应该工作的地方)和 * 奇数 * 个因子(如果不存在)数字1024的因子数为奇数(2,4,8,16,32,64,128,256,512),因为32是它的 * 平方根 *,并且使用了两次。(不是16和32。)
1.00012 ^ 1024
= 1.00012 ^(32 * 32)
=(1.00012 ^ 32)^ 32
=(1.00012 ^(4 * 8))^ 32
=((1.00012 ^4)^8)^32
=((1.00012 ^4)^8)^(4 * 8)
=((((1.00012 ^4)^8)^4)^8)

相关问题