Ex_1_1_19.md

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

1.1.19

问题：

What is the largest value of N for which this program takes less 1 hour to compute the value of F(N)? Develop a better implementation of F(N) that saves computed values in an array.

分析：

改进：递归的缺点之一就是可能重复计算。将中间步骤的计算结果保存在散列表中。这个题目中的数组实现了这个功能。

    private static long[] result = new long[100];

    public static long F(int N) {
      if (N == 0)
        return 0;
      if (N == 1)
        return 1;
      if (result[N] != 0) {
        return result[N];
      } else {
        result[N] = F(N - 1) + F(N - 2);
      }
      return result[N];
    }
  }

参考：