Ex_1_1_27.md

title	date	draft	tags	categories
算法4 Java解答 1.1.27	2019-03-02 19:38:48 +0800	false	JAVA	技术 归档

1.1.27

问题：

Binomial distribution.

Estimate the number of recursive calls that would be used by the code

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*binomial(N-1, k-1);
}

to compute binomial(100, 50, 0.25). Develop a better implementation that is based on saving computed values in an array.

估计计算binomial(100, 50, 0.25)的递归调用次数。

分析：

binomial distribution with parameters n and p is the discrete probability distribution of the number of successes in a sequence of n independent experiments, each asking a yes–no question, and each with its own boolean-valued outcome: success/yes/true/one (with probability p) or failure/no/false/zero (with probability q = 1 − p).

binomial(100, 50, 0.25)的递归调用次数上限: 2^(102) - 1

将上面的递归算法改成非递归算法。

二项分布：N次伯努利实验中，成功的次数为k，成功概率为p

概率为 = C(N,k) p^k * (1-p)^(N-k)

参考：

Binomial_distribution

老外讲二项分布入门