如何找出对nCr函数的调用次数

Question

下面的递归方程的解是什么？

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 );
}

这个递归方程是否适用于此目的？

Answer 1

我认为您的递归方程是完全正确的(您定义的函数确实总是返回0，但它与调用的次数无关)。

为了解决它，您应该看到它非常接近Pascal's triangle后面的递归，所以T(n,r)的值应该与binomial coefficient C(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，则关系为真，否则为else

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

希望这能有所帮助。

Answer 2

难道不应该是

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

Answer 3

我认为你是在正确的轨道上(说真的)，除了你的函数总是返回零。不过，修复这个问题很简单。