计算C中的二项式系数

  • Z时代
  • 2024-01-10
  • 分类：问答

我找到了以下代码来计算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在每次迭代（n--）时减少1

  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不能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那直接编码无法处理（可能会发生溢出）

以上是 计算C中的二项式系数 的全部内容， 来源链接： utcz.com/qa/424737.html

回到顶部