计算C中的二项式系数

Question

我找到了以下用于计算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

这是一个聪明的代码!

一般来说,它的目的是计算以下公式:

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. ansn在每次迭代时乘以
2. n每次迭代减少1(n--)
3. ansj在每次迭代时除以

这正是所发布的代码所做的,现在让我们看一下循环中不同条件的含义,n分母从1 开始,分母从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也不能计算,ans/j在这种情况下,我们没有幸运地先划分再乘以(因此保持结果很小).但是我们需要继续进行 - 尽管我们只剩下一个选择

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

ET VOILA!

例子 考虑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那简单的编码无法处理(可能会出现OverFlow)