c++ - c++对二项式系数递归函数的误解

Question

代码：

#include<stdio.h>
int binomialCoeff(int n, int k)
{
  // Base Cases
  if (k==0 || k==n)
    return 1;
 else
  return  binomialCoeff(n-1, k-1) + binomialCoeff(n-1, k);
}
int main()
{
    int n = 5, k = 2;
    printf("Value of C(%d, %d) is %d ", n, k, binomialCoeff(n, k));
    return 0;
}

我想我可以理解基本情况。当我们对 n 使用 0 并且 k=n 时，结果是 0!/0! 即 = 1。所以我们返回 1。公式

但我无法理解这部分代码：

 return  binomialCoeff(n-1, k-1) + binomialCoeff(n-1, k);

n 值为 5，k 值为 2，我得到的结果为 10。（在公式中替换时）。公式 但是为什么我们使用加法？

还有一件事情。为什么当我从键盘设置“n”和“k”时程序不起作用？像这样：

int main()
{
    int n,k;
    cin>>n;
    cin>>k;
    printf("Value of C(%d, %d) is %d ", n, k, binomialCoeff(n, k));
    return 0;
}

Answer 1

但是为什么我们使用加法呢？

这是数学问题而不是编程问题，有众所周知的二项式系数计算递归公式。正是这个公式在你的程序中使用。

为什么当我从键盘设置“n”和“k”时程序不起作用

代码看起来是正确的，除了您使用 std::istream 输入和 printf 输出。究竟是什么行不通？你输入 n >= k 吗？

Answer 2

return binomialCoeff(n-1, k-1) + binomialCoeff(n-1, k);

还记得帕斯卡三角吗？它完全使用这个带有加法的递归公式。

但是我可以看到您并没有构建这个三角形，而只是在使用递归时一次又一次地尝试计算一些二项式系数。记住已经计算的结果可能会大大提高您的程序性能。您的第二个问题可能是这种情况：

为什么当我从键盘设置“n”和“k”时程序不起作用。像这样：

n它应该可以工作，但是如果您输入相当大的 和 ，您的程序可能需要很长时间才能完成k。运行时间复杂度为 O(n ² )。n > 30您可能会注意到执行时间很长。

Answer 3

二项式系数的性质之一是：对于所有 1 <= k <= n-1，C(n, k) 可以写为 C(n-1,k-1) + C(n-1,k) .

所以 C(3,2) = C(2,1) + C(2,2) 或 3 = 2 + 1

这就是您共享的简单递归示例中使用的内容。

关于你的第二个问题，不知道你为什么会有任何问题。