1

我正在使用名为BinomialCoefficients的程序。

我做了一个框跟踪C(5,3)，它返回10是正确的，但我注意到在我的完整递归树中C(5, 3)，该值C(3, 2)被评估了 2 次，并被C(2, 1)评估了 3 次。

什么可能是修改，以避免多次计算相同的值？

这只是显示上下文的功能。

public static int C(int n, int k) {
   if(k>n)
      return 0;
   else if(k==0 || k==n)
      return 1;
   else
      return C(n-1, k-1)+C(n-1, k);
  }
4

2 回答 2

1

一种修改是使用乘法公式。但是你必须考虑整数溢出......（编辑：看看@ajb在评论中所说的）

我建议使用 Map 来缓存结果：

Map<String, Integer> cache = new HashMap<>();    

public static int C(int n, int k) {
  String cacheKey=key(n,k);
  if (cache.containsKey(cacheKey){
    return cache.get(cacheKey);
  if(k>n)
    return 0;
  else if(k==0 || k==n)
    return 1;
  else {
    int result = C(n-1, k-1)+C(n-1, k);
    cache.put(cacheKey, result);
    return result ;
}

public String key(int n, int k){
  return n +"_"+k;
}

当然，使用字符串作为键并不是最有效的方法，但我猜它仍然比一遍又一遍地重新计算相同的值要快得多。

于 2016-04-19T04:53:00.490 回答
0

一种解决方案是每次从顶部重建帕斯卡三角形，使用循环而不是递归。您可能会执行一些您不需要的添加。我不确定有多少。弄清楚C(i,j)你要计算多少递归函数不需要，这将是一个有趣的练习。我猜平均不超过一半的计算值是不必要的，因此它仍然应该比重复重新计算相同值的递归方法更快，并且它可能比使用哈希表更快，它携带它自己的开销。

您应该能够“就地”计算每一行，而无需为每一行分配一个新数组，以使其尽可能高效。假设您正在计算C(12,3)；三角形的第 13 行将有 13 个元素，因此您可以分配一个长度为 13 的数组开始，并N在计算第 N 行时使用数组的第一个元素。假设您已经计算了第 5 行，所以数组将是

[1, 4, 6, 4, 1, x, x, ...]  // don't care about the x's

计算下一行的算法将像这样工作：

  • 将 1 保存在临时变量中。
  • 将 4 保存在临时变量中，并将 4 替换为 4 + 1（临时变量的先前值）。
  • 将 6 保存在临时变量中，将 6 替换为 6 + 4（临时变量之前的值）
  • 将 4 保存在一个临时变量中，并将 4 替换为 4 + 6 （之前的值....我想你可以弄清楚这将如何发挥作用）
于 2016-04-19T05:10:51.173 回答