计算ncr的说明

Question

我正在阅读可能有效的计算方法当我看到这篇帖子时，ncr。

哪种方法计算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;
}

这其中的复杂性是什么？我试着用一个例子来做，结果是对的，但这些条件是什么？

Answer 1

这只是优化的结果，它计算

n! / k! (n-k)! = n * (n-1) * ... (n - k + 1) / k * (k-1) * ... * 1

第一：算法优化：当Cn k=Cn（n-k）时：计算项较少的项-很好。

下一步的计算优化：当计算ans * n / j时，在进行运算之前尝试简化分数-IMHO，这一次是高度不可讨论的，因为这是人类会做的事情（你和我计算的6 / 3比12345678 / 9)更快，但对于处理器来说，这种优化只会添加多余的运算。

Answer 2

作为链接中的状态，循环中的多重条件是在执行ans = (ans * n) / j时处理溢出。

所以功能是：

long long ans = 1;
k = std::min(k, n-k);
int j = 1;
for (; j <= k; j++, n--) {
    ans = (ans * n) / j;
}
return ans;

我们有C（n，r）=n！/（n-r）！r，并且大多数因素都可以被简化。

复杂度为k。