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，您可以重新构造方程，或使用另一个更容易提前取消项的公式。