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