3

我正在研究 Robert Sedgewick 和 Kevin Wayne 的第四版算法，并且对练习 1.1.27 感到困惑，该练习询问：

估计代码将使用的递归调用的数量

public static double binomial(int N, int k, double p)
{
  if ((N == 0) || (k < 0)) return 1.0;
  return (1.0 - p)*binomial(N-1, k, p) + p*binomial(N-1, k-1, p);
}

计算二项式（100, 50）。

虽然我想帮助回答这个问题，但我也想更好地理解和推理这种性质的问题，因此任何帮助或指示将不胜感激。

4

2 回答 2

6

该算法遍历帕斯卡三角形。

您可以将三角形遍历安排为矩形 N * K。如果算法只访问每个单元格一次，则总数为 100 * 50 = 5000。

这是一个例子：

帕斯卡三角形与矩形

在本例中，N=6 和 K=4。

然而，问题是该算法不记得它已经访问过哪些单元格，因此它是冗余访问单元格。每次通话都会使通话次数翻倍（糟糕，糟糕）。

所以它是 1 + 2 + 4 + 8 + 16 + 32 + ...

2 的幂和为 2^(n+1)-1，因此为 2^101 - 1 = 2535301200456458802993406410751

这是一个很大的数字。不要运行这个程序。

（注意，这个数字只是近似值，因为如果 K<0，有些调用不会加倍，所以可能是上面的数字除以 2 左右）。

于 2013-05-26T18:34:03.910 回答
1

如果您从具体示例开始，您将立即看到该模式。对于 N=0，显然它是 0。对于 N=1，它是 2 次递归调用（因为每个调用在直接较低的级别产生两个递归调用，即对于 N-1。

对于 N=2，则为 2*2 = 4

对于 N=3，则为 2*2*2（即 2^3）

对于 N=4，则为 2^4

我假设你看到了模式。

于 2013-05-26T18:33:37.297 回答