有人可以直观地向我解释这段代码吗（找到没有溢出错误的 nCr）？

Question

https://www.geeksforgeeks.org/program-to-calculate-the-value-of-ncr-efficiently/

这是我想看懂的代码。这是一个视频，更深入地解释了它 https://www.youtube.com/watch?v=lhXwT7Zm3EU -> 但是，我仍然不了解它的某个方面。这是代码：


// Java implementation to find nCr
 
class GFG {
 
    // Function to find the nCr
    static void printNcR(int n, int r)
    {
 
        // p holds the value of n*(n-1)*(n-2)...,
        // k holds the value of r*(r-1)...
        long p = 1, k = 1;
 
        // C(n, r) == C(n, n-r),
        // choosing the smaller value
        if (n - r < r) {
            r = n - r;
        }
 
        if (r != 0) {
            while (r > 0) {
                p *= n;
                k *= r;
 
                // gcd of p, k
                long m = __gcd(p, k);
 
                // dividing by gcd, to simplify
                // product division by their gcd 
                // saves from the overflow
                p /= m;
                k /= m;
 
                n--;
                r--;
            }
 
            // k should be simplified to 1
            // as C(n, r) is a natural number
            // (denominator should be 1 ) .
        }
        else {
            p = 1;
        }
 
        // if our approach is correct p = ans and k =1
        System.out.println(p);
    }
 
    static long __gcd(long n1, long n2)
    {
        long gcd = 1;
 
        for (int i = 1; i <= n1 && i <= n2; ++i) {
            // Checks if i is factor of both integers
            if (n1 % i == 0 && n2 % i == 0) {
                gcd = i;
            }
        }
        return gcd;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int n = 50, r = 25;
 
        printNcR(n, r);
    }
}

具体来说，为什么这段代码有效：

if (n - r < r)
  r = n - r;

为什么通过这个简单的操作，在经历并退出主while循环后最终得到正确答案？我不明白为什么这是必要的或为什么这样做有意义。比如，为什么没有这段代码会使 nCr 计算失败或无法按预期方式工作？？？？如果有人可以解释这一点或将我指向确实解释它的地方或数学概念或一些很棒的东西:)也许另一种编码相同事物的方法会有所帮助。我只是想了解为什么这会产生作为数学和编码学生的正确答案。为了对我的能力有一些看法（所以你知道我处于什么水平），我正在学习面向对象的编程，并且已经完成了高中数学和基础计算机科学。我绝不是专家。

Answer 1

nCr 操作具有特殊性，在 if 条件上方的评论中提到：// C(n, r) == C(n, n-r)。现在，while 循环在 r>0 时迭代，并且每次迭代时 r 的值递减 1。所以为了减少循环的执行次数，我们需要减小r的值（如果可能的话）。由于C(n, r) == C(n, n-r)，我们取r和n-r中较小的值，使迭代次数最小化，但结果保持不变。

假设 n = 100 和 r=99。在这种情况下，如果我们跳过 if 条件，那么循环将执行 99 次，而使用 if 条件我们可以将 r 更新为 r = n-r所以 r=1 那么循环只会执行一次。因此，我们节省了 98 不需要的迭代。

所以如果我们包含 if 条件，性能会有很大的提高。

有人可以直观地向我解释这段代码吗（找到没有溢出错误的 nCr）？

Can someone explain this code to me intuitively (finding nCr without overflow error)?

java

math

factorial