使用数组来改善递归二项分布算法的执行时间?

作为一名初学程序员,我最近买了Robert Sedgewick / Kevin Wayne的书“算法 – 第四版”,我非常感谢每一章末尾的练习.然而,有一个练习(看起来很简单)让我疯狂,因为我无法找到解决方案.

你必须采用这种递归算法,找出在n次试验中获得完全k次成功的概率,其中p是一个事件成功的可能性.给出的算法基于递归二项分布论坛.

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

本练习的目的是通过在数组中保存计算值来加快此算法的速度.通过使用另一种获得二项分布[p(x)= nCr * p ^ k *(1 – p)^(n – k)]的方法,我已经使这个算法变得更快了,它使用迭代方法来寻找阶乘.但是,我不明白如何使用数组来改善此上下文中的执行时间.

任何帮助将不胜感激!

……在有人问之前,这不是作业!

本书试图教你一种叫做 memoization的特殊编程技术,这种技术被称为 dynamic programming.当然,在现实生活中,知道封闭形式的解决方案要好得多,但不能解决这个问题.

无论如何,我们的想法是将2D数组作为第四个参数传递,最初用NaN填充它,并在计算任何东西之前检查数组中n和k的给定组合是否有解.如果有,请归还;如果没有,则递归计算,存储在数组中,然后返回它.

相关文章
相关标签/搜索