计算 C 中的二项式系数

我找到了以下代码进行计算nCr，但不明白其背后的逻辑。为什么这段代码有效？

long long combi(int n,int k)
{
    long long ans=1;
    k=k>n-k?n-k:k;
    int j=1;
    for(;j<=k;j++,n--)
    {
        if(n%j==0)
        {
            ans*=n/j;
        }else
        if(ans%j==0)
        {
            ans=ans/j*n;
        }else
        {
            ans=(ans*n)/j;
        }
    }
    return ans;
}

这是一个聪明的代码！

一般来说，它的目的是计算以下公式：

ans = n! / (k!)(n-k)!

它等于：

ans = n(n-1)(n-2) ... (n-k)...1 / k(k-1)...1 * (n-k)(n-k-1) ... 1

明显取消后：

ans = n(n-1)(n-2)..(n-k+1) / k!

现在请注意分子和分母具有相同数量的元素（k 元素）

所以 ans 的计算如下：

ans  = 1 // initially
ans *= n/1
ans *= (n-1)/2
ans *= (n-2)/3
.
.
.
ans *=  (n-k+1)/k

再次查看代码，您会发现：

1. ans正在乘以n在每次迭代时
2. n每次迭代时减少 1 (n--)
3. ans除以j在每次迭代时

这正是发布的代码所做的，现在让我们看看循环中不同条件的含义，提名者从n和分母从 1 到k，所以变量j分配给分母对吗？

1) if(n%j==0)

在每一步如果n/j是（可计算）所以我们首先计算它而不是乘以整体ans，这种做法将结果保持在尽可能小的值。

2) else if(ans%j==0)

如果我们无法计算每一步n/j但实际上可以计算ans/j所以这样说也不错：

ans /= j; //first we divide
ans *= n; //then we multiply

这总是使我们的总体输出尽可能小，对吗？

3) last condition

在每一步，如果我们都无法计算n/j nor ans/j在这种情况下，我们不够幸运，不能先除然后乘（因此保持结果很小）。但我们还是需要继续前进——尽管我们只剩下一个选择：

ans *= n; // multiply first
ans /= j; // then divide

瞧瞧！

Example考虑这个案例3C7我们知道答案是 7!/ 3!*4! 因此 ：ans = 7*6*5 / 1*2*3

让我们看看每次迭代会发生什么：

//1 
ans = 1

//2 
n = 7
j = 1
ans = ans * n/j 
first compute 7/1 = 7
then multiply to ans
ans = 1*7
ans = 7

//3
n = 6
j = 2
ans = ans* n/j

evaluate n/j = 6/2 (can be divided)
         n/j = 3
ans = ans *(n/j)
    = 7 * 3
    = 21

// 4
n = 5
j = 3

ans = ans * n/j
evaluate n/j = 5/3 oppsss!! (first if)
evaluate ans/j = 21/3 = 7 YES (second if)

ans = (ans/j)*n
    = 7*5
    = 35

// end iterations

请注意，在最后一次迭代中，如果我们直接计算，我们会说：

ans = ans*n/j
    = 21 * 5 / 3
    = 105 / 3
    = 34 

是的，它确实找到了正确的结果，但同时该值飞升至 105，然后又回到 35。现在想象一下计算真正的大数？！

结论该代码仔细计算二项式系数，试图在计算的每一步中保持输出尽可能小，它通过检查是否可以除以（int）然后执行，因此它能够计算一些非常大的kCn直接编码无法处理（可能会发生溢出）