二项分布算法（递归）_二项分布 递归

关于用递归实现的二项分布算法

   最近在看Sedgewick的《算法》的时候有一题习题是关于改进用递归实现的二项分布算法。这里我令服从二项分布为$X\sim b(N,k,p)$，书本上习题给出的算法是：
1

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-p)*binomial(N-1,k,p)+p*binomial(N-1,k-1,p);
}
1
2
3
4
5
6
7
8

我们可能刚开始看这个递归算法的时候会不太明白（当时我都看懵逼了），那我们就从小一点的值来分析一下，假如$N=2,\ k=1,\ p=0.5$，即$b(2,\ 1,\ 0.5)$。那么我们按照这个算法来分析一下接下来的递归过程：
我们可以看到每一次都可以分开两部分然后再继续递归，直到出现$N=0\ ,k=0$，可能刚会不太明白为什么这个算法可以算出二项分布，如果我们看一下我们的概率统计相关的书就可以知道有这样一条递归公式：

$$\left(\begin{matrix} N \\ k \\ \end{matrix}\right)p^k(1-p)^{N-k} =(1-p)\left(\begin{matrix} N-1 \\ k \\ \end{matrix}\right)p^k(1-p)^{N-1-k} +p\left(\begin{matrix} N -1 \\ k -1 \\ \end{matrix}\right)p^{k-1}(1-p)^{N}$$
你就会懂为什么有这个递推算法了，而且上面的公式本质上其实是组合递推公式：
$$\left(\begin{matrix} N \\ k \\ \end{matrix}\right) =\left(\begin{matrix} N-1 \\ k \\ \end{matrix}\right) +\left(\begin{matrix} N-1 \\ k -1\\ \end{matrix}\right)$$
那么我们搞懂了这个算法之后，我们会发现这个算法在 $N$很大的时候会发生递归层数很深，从我们上面这幅图也可以看出来，每一个递归又会产生两个递归，所以假设$b(100,\ 50,\ 0.25)$的情况下函数将被递归调用大约在 $2.252*10^{15}\sim1.267*10^{30}$数量相当的庞大，反正我用这个算法运行的时候压根就等不到运算结果。
所以后来就改了一下算法，改用大量循环，不用递归实现。

    //计算组合数
    public static double zuhe(double N, double k)
    {
        //模拟人类计算的约分过程从而减少阶乘数量
        double m = N-k;
        double min = k;
        double max = m;
        double t = 0;

        double NN=1;
        double kk=1;
        if(min>max)
        {
            t=min;
            min = max;
            max=t;
        }
        //把大的阶乘约分去掉
        while(N>max)
        {
            NN=NN*N;
            N--;
        }
        //计算小的阶乘
        while(min>0)
        {
            kk=kk*min;
            min--;
        }
        //算出组合数
        return NN/kk;
    }
    //计算二项分布值
    public static double binomial(int N,int k,double p)
    {
        double y=1;
        double s=1;
        //计算组合数
        double a =binomial(N,k);
        //计算(1-p)的(N-k)次方
        while((N-k)>0)
        {
            s=s*(1-p);
            N--;
        }
        //计算p的k次方
        while(k>0)
        {
            y=y*p;
            k--;
        }
        //最后三个值相乘得出二项分布值
        return a*y*s;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

经过去掉递归后的算法就能很快的算出<script id="MathJax-Element-10" type="math/tex">N</script>值比较大的情况下的二项分布值。
如果你们还有更好的算法，可以告诉我，大家交流一下学习一下。