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

Question

我正在尝试解决所有关于 codility 的类(class)，但我未能解决以下问题:Ladder by codility

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

因此，在发布代码之前，我将解释一下思路。

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

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

到目前为止一切顺利，我决定在不使用 var max 的情况下提交它，然后我得到了 37% 的分数。我在整个互联网上进行了搜索，100% 的结果与我的相似，但他们补充说 max =数学.pow(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

输入参数的限制是:

Assume that:

• L is an integer within the range [1..50,000];
• each element of array A is an integer within the range [1..L];
• each element of array B is an integer within the range [1..30].

所以数组f在fibArray可以是 50,001 长。

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

Javascript 没有对任意精度整数的内置支持，甚至 double 也只提供 ~14 s.f.精度。因此，使用修改后的代码，您将获得 L 的任何重要值的“垃圾”值。 .这就是为什么你只得到了 30%。

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

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

所以通过应用 % max到迭代计算步骤 arr[current-1] + arr[current-2] , fibArray 中的每个元素成为其对应的 Fib 数 mod 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)

请注意，作为 B[i]永远不会超过 30，pow(2, B[i]) <= max ;因此，由于 max总是能被 pow(2, B[i]) 整除, 申请 % max不影响最终结果。