我写的查找计算NCR的函数有什么问题？

提问者：小点点

我尝试使用这个关系递归地找到NCR的值:

nCr=（n-r+1）/r*nC（r-1）

int comb(int n, int r){
    if(r == 0) return 1;
    return ((n - r + 1) / r) * comb(n , r - 1);
}

对于6C2的呼叫，我得到12而不是15。我试过追踪，但我得到了正确的答案。欢迎您的任何意见！谢谢

共3个答案

匿名用户

考虑一下当您执行comb(6，2)时会发生什么。在第一个递归调用中，返回表达式变为:

return (5 / 2) * comb(6, 1);

(5/2)将进行整数除法，并给出2，这是不正确的。

由于ncr的最终答案实际上保证有一个整数结果，所以您可以通过简单地计算所有分子，然后除以任何分母来修复该等式，如下所示:

return (n - r + 1) * comb(n , r - 1) / r ;

这是一个演示。

注意，如果您担心分子值溢出int，您可以重新构造等式，或者使用另一个公式，这样更容易在较早时取消项。

匿名用户

整数除法的典型陷阱:

多少钱:

(3/2)*(4/3)

实际上是2，在C++中是1:

3/2的整数除法等于1.
4/3的整数除法等于1。

因此，您需要强制浮点除法，例如:

int comb(int n, int r){
    if(r == 0) return 1;
    return ((double)(n - r + 1) / r) * comb(n , r - 1);
}

祝你好运

匿名用户

用这个公式。

nCr=(n/r)*n-1cr-1；

代码更改为，

int comb(int n, int r)
{
    if(r > 0)
        return (n/r)*comb(n-1,r-1);
    else 
        return 1;
}