Algorithmfourth-edition二项分布的递归与非递归实现

jiezi

5 年前

1.1 Basic Programming Model
Creative Problems
1.1.27
Estimate the number of recursive calls that would be used by the code to compute binomial(100,50).Develop a better implementation that is based on saving computed values in an array.

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

因为对于递归其实了解得还不算太深刻，所以乍一看到这个 code 还是有点懵（这和我想象中的二项分布不一样啊 xxx
然后去谷歌了一下发现正好有人写了分析这道题的 blog
链接在此
主要是对于这个和排列组合有关的递推式不是很了解（就是不知道），所以也看不明白这个递归的 code

不过原 code 来算二项分布真的很灾难，N=10 的时候调用次数就有 2000+ 了，按原题给的那个 100 的数据我 IDEA 直接就 3s 之内跑不完了

非递归
- 要算二项分布的话第一反应其实就是直接根据公式来，计算组合数和幂运算
- 但测试了一下发现，计算组合数需要用到阶乘，N 过大算出来的阶乘会 overflow，结果为 0（用 int 和 long 都不可以），所以不能直接算组合数
- 只要进行一点小小的调整：
  - 组合数写成阶乘的形式时上下是可以约分的，不需要真的算出 N 的阶乘（如链接中的做法）
递归
- 根据题目中给的提示“saving computed values in an array”
- 原链接中有答案
网站上给出的题解（递归思想的非递归写法）

/**
解释：利用的思想仍旧是(n,k) = p * (n-1,k-1) + (1-p) * (n-1,k)
(n,k)指 N = n, k = k 的情况
理解：想象要在 n 个人里面挑 k 个人，假设第 k 个人被选中了 (概率为 p)，那么就是(n-1,k-1) 的情况，假设第 k 个人没有被选中 (概率为 1 -p)，那么就是(n-1,k) 的情况
*/
public static double binomial2(int N, int k, double p) {double[][] b = new double[N+1][k+1];

    // base cases
    // 当 k 为 0 时，都为(1-p)^i
    for (int i = 0; i <= N; i++)
        b[i][0] = Math.pow(1.0 - p, i);
    b[0][0] = 1.0;

    // recursive formula
    for (int i = 1; i <= N; i++) {for (int j = 1; j <= k; j++) {// (n,k) = p * (n-1,k-1) + (1-p) * (n-1,k)
            b[i][j] = p * b[i-1][j-1] + (1.0 - p) *b[i-1][j];
        }
    }
    return b[N][k];
}

Algorithmfourth-edition二项分布的递归与非递归实现

原题：

改进方法