下列递推方程的解是什么?
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 = 0r = 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/

10-14 16:08