1

这是我使用java实现的斐波那契数列

/**
 * Returns nth fibonacci number
 */
public class fib {

   public static void main(String[] args){
      System.out.println(fibonacci(12));
   }

   public static int fibonacci(int n) {
      if (n == 0){
         return 0;
      } else if (n == 1){
         return 1;
      } else {
         return fibonacci(n - 1) + fibonacci(n - 2);
      }
   }
}

但是使用递归可视化这种方法让我觉得它会快很多。这是 fib(5) 的可视化。http://imgur.com/a/2Rgxs 但这引起了我的思考,请注意,当我们从递归路径的底部冒泡时,我们计算 fib(2)、fib(3) 和 fib(4) 但随后我们在最右上角的分支上重新计算 fib(3)。所以我在想,当我们冒泡备份时,为什么不保存从左分支计算出的 fib(3),这样我们就不会像我目前的方法那样在右分支上进行任何计算,就像回来时的哈希表一样。我的问题是,我如何实现这个想法?

4

3 回答 3

2

当您想添加HashMap并保持原始方法时,请尝试以下操作:

static HashMap<Integer, Integer> values = new HashMap<Integer, Integer>();

public static void main(String[] args){
    values.put(0, 0);
    values.put(1, 1);
    System.out.println(fibonacci(12));
}

public static int fibonacci(int n) {
    if (values.containsKey(n)){
        return values.get(n);
    } else {
        int left = values.containsKey(n - 1) ? values.get(n - 1) : fibonacci(n - 1);
        values.put(n - 1, left);
        int right = values.containsKey(n - 2) ? values.get(n - 2) : fibonacci(n - 2);
        values.put(n - 2, right);
        return left + right;
    }
}

如果您更频繁地调用它,这种方法可能会非常快,因为斐波那契结果已经存储在中values(当然这也可以用其他方法完成):

public static void main(String[] args){
    values.put(0, 0);
    values.put(1, 1);
    System.out.println(fibonacci(12));
    System.out.println(fibonacci(11));
    System.out.println(fibonacci(10));
}
于 2017-02-07T10:46:31.017 回答
1

对于快速计算,您根本不需要递归 - 只需移动中间结果

public static int fibonacci(int n) {
  if (n == 0) {
  return 0;
  } else {
    int npp = 0; // pre-previous number
    int np = 1; // previouse number
    int r = 1; // current number, eventually the result
    for (int i = 2; i <= n; i++) {
      r = np + npp;
      npp = np;
      np = r;
    }

    return r;
  }
}
于 2017-02-07T10:43:57.570 回答
0

为了避免重复计算,可以使用动态规划。顺便说一句,这不是内存优化解决方案,但它可以比递归解决方案更快。

public static int fibonacci(int n)
{    
    int f[] = new int[n+1];

    for (int i = 0; i <= n; i++) {
        if(i == 0 || i == 1) {
            f[i] = i;
        }
        else {
            f[i] = f[i-1] + f[i-2];
        }
    }

    return f[n];
}
于 2017-02-07T10:45:52.823 回答