4

作为一名初级程序员，我最近购买了 Robert Sedgewick/Kevin Wayne 所著的《Algorithms - Forth Edition》一书，我非常感谢每章末尾的练习。但是，有一个练习（看起来很简单）让我发疯，因为我找不到解决方案。

您必须采用这种递归算法来计算在 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)] 的方法使该算法变得更快，该方法使用迭代方法来查找阶乘。但是，我不明白在这种情况下如何使用数组来提高执行时间。

任何帮助将不胜感激！

...在有人问之前，这不是作业！

4

3 回答 3

5

这本书试图教你一种特殊的编程技术，称为记忆化，一种更广泛的技术，称为动态编程。当然，在现实生活中知道一个封闭形式的解决方案要好得多，但不是在解决这个练习的背景下。

无论如何，这个想法是传递一个二维数组作为你的第四个参数，最初用 s 填充它，并在计算任何东西之前检查数组中NaN的给定组合是否有解决方案。如果有，请退还；如果没有，则递归计算，存储在数组中，然后才返回它。nk

于 2012-04-27T19:55:04.547 回答
3

这里的递归算法最终会一遍又一遍地调用特定条件。例如：

3, 3
  2, 3
    1, 3
      0, 3
      0, 2
    1, 2
      0, 2
      0, 1
  2, 2
    1, 2
      0, 2
      0, 1
    1, 1
      0, 1
      0, 0

例如，通过记住 (1, 2) 的值，并在再次使用这些参数调用时立即返回该值，可以提高效率。使用番石榴Table，这看起来像：

public static double binomial(int n, int k, double p, Table<Integer, Integer, Double> memo) {
    if(memo.contains(n, k))
        return memo.get(n, k);

    double result;
    if (n == 0 && k == 0)
        result = 1.0;
    else if (n < 0 || k < 0)
        result = 0.0;
    else 
        result = (1 - p) * binomial(n - 1, k, p) + p * binomial(n - 1, k - 1, p);

    memo.put(n, k, result);
    return result;
}
于 2012-04-27T20:01:27.113 回答
1

有点晚了，但对于那些正在寻找完整解决方案的人来说，下面是我的。首先，我建议其他人阅读此处给出的答案：https ://stackoverflow.com/a/6165124/4636721以了解动态编程、记忆和制表的含义

无论如何，关于我的解决方案，所以基本上我们有给定的方法：

// Not efficient at all
private 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;
    }
    else
    {
        return (1.0 - p) * binomial(N - 1, k, p) + p * binomial(N - 1, k - 1, p);
    }
}

是的，这真的很慢......递归调用的数量有点大（大约〜N ^ 2）

是的，您可以使用基本上就像其他人已经说明的那样基本上缓存先前计算的值的记忆方法。对于某些人来说，记忆意味着保持递归策略并检查我们需要的值是否已计算，如果没有程序必须计算并缓存它，它真的很容易实现：

private static double binomialTopDown(int N, int k, double p)
{
    double[][] cache = new double[N + 1][k + 1];

    for (int i = 0; i < (N + 1); i++)
    {
         Arrays.fill(cache[i], Double.NaN);
    }

    return binomialTopDown(N, k, p, cache);
}

// More efficient
private static double binomialTopDown(int N, int k, double p, double[][] cache)
{
    if ((N == 0) && (k == 0))
    {
        return 1.0;
    }
    else if ((N < 0) || (k < 0))
    {
        return 0.0;
    }
    else if (Double.isNaN(cache[N][k]))
    {
        cache[N][k] = (1.0 - p) * binomialTopDown(N - 1, k, p, cache) + p * binomialTopDown(N - 1, k - 1, p, cache);
    }

    return cache[N][k];
}

诀窍实际上是使用自下而上的方法（也称为制表法）以更有效的方式对计算进行排序。这通常是通过使用上述算法的迭代版本来实现的。

// Much more efficient
private static double binomialBottomUp(int N, int k, double p)
{
    /*
    double[][] cache = new double[N + 1][k + 1];

    cache[0][0] = 1.0;

    for (int i = 1; i <= N; i++)
    {
        cache[i][0] = Math.pow(1.0 - p, i);

        for (int j = 1; j <= k; j++)
        {
            cache[i][j] =  p * cache[i - 1][j - 1] + (1.0 - p) * cache[i - 1][j];
        }
    }

    return cache[N][k];
    */

    // Optimization using less memory, swapping two arrays
    double[][] cache = new double[2][k + 1];
    double[] previous = cache[0];
    double[] current = cache[1];
    double[] temp;

    previous[0] = 1.0;

    for (int i = 1; i <= N; i++)
    {
        current[0] = Math.pow(1.0 - p, i);

        for (int j = 1; j <= k; j++)
        {
            current[j] =  p * previous[j - 1] + (1.0 - p) * previous[j];
        }

        temp = current;
        current = previous;
        previous = temp;
    }

    return previous[k];
}

这是使用自下而上方法的动态编程最有效的方法。

希望这可以帮助。

于 2016-03-30T06:34:30.623 回答