我为查找计算 NCR 而编写的这个函数有什么问题？

Question

我尝试使用这个关系递归地找到 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。我试图追踪，但我得到了正确的答案。任何输入表示赞赏！谢谢

Answer 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;
}

Answer 2

想想当你这样做时会发生什么 comb(6, 2)。在第一次递归调用中，return 表达式变为：

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

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

由于 nCr 的最终答案实际上保证有一个整数的结果，您可以通过简单地计算在除法之前的所有分子来解决方程式它由任何分母组成，如下所示：

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

这里是 demo。

请注意，如果您担心分子值会溢出 int，您可以重构方程，或使用其他更容易抵消之前项的公式。

Answer 3

整数除法的典型陷阱：

多少钱：

(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);
}

祝你好运

What's wrong with this function that I wrote to find calculate NCR?