Codility Ladder javascript - 不了解将答案从 37% 跳到 100% 的细节

Question

我正在尝试解决有关 codility 的所有课程，但我未能解决以下问题：Ladder by codility

我在互联网上进行了搜索，但没有找到让我满意的答案，因为没有人回答为什么 max 变量对结果的影响如此之大。

所以，在发布代码之前，我会解释一下这个想法。

通过查看它，我不需要太多时间来理解它的组合总数是一个斐波那契数，并从斐波那契数组中删除 0，我会很快找到答案。

现在，后来，他们告诉我们应该返回模数 2^B[i] 的组合数。

到目前为止一切顺利，我决定在没有 var max 的情况下提交它，然后我得到了 37% 的分数。 (2,30)。

任何人都可以向我解释这个最大值如何以及为什么会如此影响分数？

我的代码：

// Powers 2 to num
function pow(num){
    return Math.pow(2,num);
}
// Returns a array with all fibonacci numbers except for 0
function fibArray(num){
    // const max = pow(30); -> Adding this max to the fibonaccy array makes the answer be 100% 
    const arr = [0,1,1];
    let current = 2;

    while(current<=num){
        current++;
        // next = arr[current-1]+arr[current-2] % max; 
        next = arr[current-1]+arr[current-2]; // Without this max it's 30 %
        arr.push(next);
    }

    arr.shift(); // remove 0
    return arr;

}

function solution(A, B) {
    let f = fibArray(A.length  + 1);
    let res = new Array(A.length);

    for (let i = 0; i < A.length; ++i) {
        res[i] = f[A[i]] % (pow(B[i]));
    }

    return res;
}

console.log(solution([4,4,5,5,1],[3,2,4,3,1])); //5,1,8,0,1 

// Note that the console.log wont differ in this solution having max set or not.
// Running the exercise on Codility shows the full log with all details 
// of where it passed and where it failed.

Answer 1

输入参数的限制是：

假使，假设：

• L 是 [1..50,000] 范围内的整数；
• 数组 A 的每个元素都是 [1..L] 范围内的整数；
• 数组 B 的每个元素都是 [1..30] 范围内的整数。

所以数组finfibArray可以是 50,001 长。

斐波那契数呈指数增长；根据this page，第50,000个Fib号码有超过10,000位数字。

Javascript 没有对任意精度整数的内置支持，甚至双精度也只能提供 ~14 sf 的精度。因此，使用修改后的代码，对于任何重要的L. 这就是为什么你只得到 30% 的原因。

但为什么是max必要的？模数数学告诉我们：

(a + b) % c = ([a % c] + [b % c]) % c

所以通过施加% max到迭代计算步骤arr[current-1] + arr[current-2]，在每一个元件fibArray成为其相应的Fib号模max，而没有任何超出变量的值 max（或内置整数类型）在任何时间：

fibArray[2] = (fibArray[1] + fibArray[0]) % max = (F1 + F0) % max = F2 % max
fibArray[3] = (F2 % max + F1) % max             = (F2 + F1) % max = F3 % max
fibArray[4] = (F3 % max + F2 % max)             = (F3 + F2) % max = F4 % max
and so on ...
(Fn is the n-th Fib number)

请注意，asB[i]永远不会超过 30, pow(2, B[i]) <= max; 因此，由于max始终可以被 整除pow(2, B[i])，因此应用% max不会影响最终结果。