algorithm - 如何找出nCr函数的调用次数

下列递推方程的解是什么？
T（n，0）=1，
t（n，n）=1，
t（n，r）=t（n-1，r-1）+t（n-1，r）+1
我是在试图找出对nCr函数的调用次数时得到这个的，在nCr的以下定义中

int nCr ( int n, int r ) {
  if( n == r || r == 0 )
    return 0;
  return nCr( n-1, r-1 ) + nCr( n-1, r );
}

这个递归方程适合这个目的吗？

最佳答案

我认为你的递归公式是完全正确的（你定义的函数确实总是返回0，但它与调用的次数无关）。
为了解决这个问题，您应该看到它非常接近Pascal's triangle后面的递归，所以T(n,r)的值应该与binomial coefficientC(n,r)相关。
如果你试着写下这个新三角形的前几行，你会得到：

1
1 1
1 3 1
1 5 5 1
1 7 11 7 1
1 9 19 19 9 1
1 11 29 39 29 11 1
...

从中，您可以使用OEIS，或者找出自己的T(n,r) = 2 * C(n,r) - 1。
然后你可以用归纳法证明：如果r = 0或r = n，则关系成立，否则

T(n,r) = T(n-1,r) + T(n-1,r-1) + 1
       = (2 * C(n-1,r) - 1) + (2 * C(n-1,r-1) - 1) + 1
       = 2 * (C(n-1,r) + C(n-1,r-1)) - 1
       = 2 * C(n,r) - 1

希望这有帮助。

关于algorithm - 如何找出nCr函数的调用次数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7513157/