javascript - 这段代码为何有效的数学解释

Question

我在网站 CodeFights 中遇到了一个问题，我用两个循环解决了这个问题。在查看其他答案时，我发现了一个没有循环解决它的答案，这让我张开了嘴。编码器应用了 Math.min/max ，虽然我确实理解代码的作用，但我不明白它为什么起作用。

我很喜欢学习，因为哎呀，Math.max/min 肯定会在我的循环中击败字节数。

Given integers n, l and r, find the number of ways to represent n as a sum
of two integers A and B such that l ≤ A ≤ B ≤ r.

Example

For n = 6, l = 2 and r = 4, the output should be
countSumOfTwoRepresentations2(n, l, r) = 2.

There are just two ways to write 6 as A + B, where 2 ≤ A ≤ B ≤ 4: 6 = 2 + 4 and 6 = 3 + 3.

Input/Output

[time limit] 4000ms (js)
[input] integer n

A positive integer.

Constraints:
5 ≤ n ≤ 109.

[input] integer l

A positive integer.

Constraints:
1 ≤ l ≤ r.

[input] integer r

A positive integer.

Constraints:
l ≤ r ≤ 109,
r - l ≤ 106.

程序员的惊人回答:

function countSumOfTwoRepresentations2(n, l, r) {
    return Math.max(Math.min(Math.floor(n / 2) - l, r - Math.ceil(n / 2)) + 1, 0);
}

相比之下我的废话:

function countSumOfTwoRepresentations2(n, l, r) {
    var representations = 0;
    //Only travel the loop until n/2 , because l+r will never equal n
    // if l or r > n/2
    var limit = Math.floor(n/2);
    for(var i=l; i<=r && i<=limit; ++i){
        for(var j=i;j<=r;++j){ 
            if(i+j == n){
                ++representations;
                break; 
            }
        }
    }
    return representations;
}

Answer 1

Given integers n, l and r, find the number of ways to represent n as a sum of two integers A and B such that l ≤ A ≤ B ≤ r.

首先，考虑如果n甚至让x = n/2 , 我们至少有一个解决方案 ( x + x ) 当且仅当 l ≤ x ≤ r .如果x不在该范围内则没有解决方案，因为 x < l和 l + l > n或 r < x和 r + r < n .

可以概括为偶数或奇数 n : 有一个解决方案当且仅当:l ≤ floor(x) ≤ ceil(x) ≤ r .如果我们让 A = floor(x)和 B = ceil(x) ，该解决方案是 A + B .可以通过沿数轴从每个方向远离该点走一步来找到所有其他解决方案。 (A - 1) + (B + 1) = A + B = n ，因此 (A - 1) + (B + 1)是只要(A - 1)的解决方案还没有越过l边界和 (B + 1)还没有越过r边界。所以，如果你想要一个只有一个循环的解决方案，你可以这样做:

function countSumOfTwoRepresentations2(n, l, r) {
    var x = n/2;
    var A = Math.floor( x );
    var B = Math.ceil( x );
    for ( var count = 0; l <= A && B <= r; count++) {
        A--;
        B++;
    }
    return count;
}

但是这个循环迭代了多少次？好吧，它会一直迭代直到出现一种停止条件:

1. A变得小于 l
2. B变得大于 r

如果1.首先发生，然后迭代 Math.floor( x ) - l + 1次，而如果 2.首先发生它迭代r - Math.ceil( x ) + 1 (如果两种情况都发生在同一次迭代中，则为 Math.floor( x ) - l === r - Math.ceil( x ))。

只要有解决方案，循环就会迭代 Math.floor( x ) - l + 1 中较小的那个或 r - Math.ceil( x ) + 1次，这是编码人员得到答案的地方 Math.min(Math.floor(n / 2) - l, r - Math.ceil(n / 2)) + 1来自(将 x 替换回 n/2 并将 + 1 从每个术语中拉出并添加到后面。

如果没有解决方案，EG. n = 10, l = 20, r = 20 ，该公式将给出否定结果，但它应该给出 0相反，这就是他添加 Math.max( result, 0 ); 的原因.

为了清楚起见，编码器的解决方案可以写成(仍然没有循环):

function countSumOfTwoRepresentations2(n, l, r) {
    var x = n/2;
    var A = Math.floor( x );
    var B = Math.ceil( x );

    // Every solution is of the form (A - i) + (B + i), where i is an integer >= 0

    // How many values of i are valid for l <= (A - i)
    var stepsA = A - l + 1;

    // How many values of i are valid for (B + i) <= r
    var stepsB = r - B + 1;

    // If the formulas gave a negative amount of valid steps, 
    // there is no solution, so return 0
    if ( stepsA < 0 || stepsB < 0 )
        return 0;

    // Otherwise, return the smaller valid amount of steps,
    // that is the number of steps that are valid for both A and B
    return Math.min(stepsA, stepsB);
}