时间戳

首页 > 解决方案 > 二项式系数的代码适度

c++ - 二项式系数的代码适度

问题描述

我最近以时间和空间有效的方式看到了二项式系数的代码。

ll C(ll n,ll k)
{
    ll p=1;

    if(k>n-k)
    k=n-k;

    for(int i=0;i<k;i++)
    {
    p*=(n-i);
    p/=(i+1);
    }

return p;
}

让我们考虑以下三种不同的方法。

情况1：

for(int i=0;i<k;i++)
{
p*=(n-i);
p/=(i+1);
}

案例2：

for(int i=0;i<k;i++)
{
p*=(n-i)/(i+1);
}

案例3：

for(int i=0;i<k;i++)
p*=(n-i);

for(int i=0;i<k;i++)
p/=(n-i);

在案例 1 和案例 3 中，答案都是正确的，而在案例 2 中，答案是不同的。但是只有案例 3 应该产生正确的答案，而不是 2 和 1，因为在这两种情况下，小数部分都会在乘法之后由于除法而被删除。

谁能给我解释一下这些东西。

标签： c++

解决方案

考虑案例 1：

for(int i=0;i<k;i++)
{
  p*=(n-i); //statement 1
  p/=(i+1); //statement 2
}

在第一次迭代中，它将是一个没有截断的整数除法，就像i1 一样。在第二次迭代中，在语句 1 中，p它将是奇数和偶数的乘积（因为它们是连续的），因此可以被整除声明 2 中的 2。

在第三次迭代中，在语句 1 中，p将是三个连续数字的降序乘积，因此在语句 2 中可以被 3 整除。

等等...

考虑案例 2：
这失败了，因为在语句的 rhs 中首先执行整数除法

p*=(n-i)/(i+1);

这会导致截断，您已经正确地推测了这一点。

考虑案例 3： 我相信您的代码应该是这样的： 

for(int i=0;i<k;i++)
p*=(n-i);

for(int i=0;i<k;i++)
p/=(i+1);

在这里，我们看到了与案例 1 中发生的情况类似的情况，但非常明显。您首先以降序（最多 k）将连续整数相乘，然后将其除以以递增顺序（最多 k）的整数的乘积。这是二项式系数的公式，并给出了正确的结果。

注意：由于案例 3在除法开始之前有连续的乘法，因此可能会溢出。所以案例1是首选。

推荐阅读