このコードが動作する理由の説明

Question

2つのループで解決したCodeFightサイトで問題が発生しました。他の答えを見ている間、私はループなしでそれを解決し、私の口を開いて私を残しました。コーダーは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

考えると整数n、lとr、Nとして表現するために、いくつかの方法を見つけます2つの整数の和はAとBです。それは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 - 1)が境界を越えておらず、(B + 1)が境界を越えていない限り、解決策である。(A - 1) + (B + 1) = A + B = nは、(B + 1)が境界を越えていない限り、解決策である。あなたが唯一のループを備えたソリューションを望んでいたのであれば、あなたはこのような何かを行うことができます：

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が1.が最初に発生した場合であれば、一方、それは、Math.floor(x) - l + 1回反復しr

よりも大きくなるよりも小さくなり、 2.が最初に発生し、それはr - Math.ceil(x) + 1を繰り返します（両方の条件が同じ反復で発生する場合は、Math.floor(x) - l === r - Math.ceil(x)）。

限りコーダはバックn/2ためxを代入し、各用語のうち+ 1を引いて、それを追加した後（から回答Math.min(Math.floor(n/2) - l, r - Math.ceil(n/2)) + 1を得たところで、ループ反復小さいMath.floor(x) - l + 1又はr - Math.ceil(x) + 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); 
}