c++ - 我为了计算 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

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

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

(5 / 2)将要进行整数除法并给出 2这是不正确的。
由于 nCr的最终答案实际上保证有一个整数的结果，您可以通过在除以任何分母之前简单地计算所有分子来修复方程，如下所示:

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

这是一个 demo .
请注意，如果您担心分子值溢出 int ，您可以重新构造方程，或使用另一个更容易提前消除项的公式。