Java程序Fibonacci序列 [英] Java Program Fibonacci Sequence

问题描述

我正在编写一个简单程序来确定Fibonacci序列中的第N个数字。例如：序列中的第7个数字是：13。我已经完成了程序的编写，它可以工作，但从第40个数字开始它开始延迟，并且需要更长，更长。我的节目必须到系列中的第100个位置。

I am writing a "simple" program to determine the Nth number in the Fibonacci sequence. Ex: the 7th number in the sequence is: 13. I have finished writing the program, it works, but beginning at the 40th number it begins to delay, and takes longer, and longer. My program has to go to the 100th spot in the series.

我如何解决这个问题，所以它不需要这么长时间？这是非常基本的程序，所以我不知道所有花哨的语法代码..我的公式是：

How can I fix this so it doesn't take so long? This is very basic program, so I don't know all the fancy syntax codes.. my formula is:

if n =1 || n = 0
   return n;

else 
    return F(n-1) + F(n-2);

这项工作非常有效，直到超过第40个学期。我必须添加什么其他声明才能更快地获得更高的数字？

This works great until it goes past the 40th term. What other statement do I have to add to make it go quicker for higher numbers??

推荐答案

问题是因为你是使用简单递归，您可以多次重新评估F（n），因此执行时间是指数级的。

The problem is that because you are using simple recursion, you re-evaluate F(n) multiple times, so your execution time is exponential.

有两种简单的方法可以解决这个问题：

There are two simple ways to fix this:

1）第一次评估F（n）时的缓存值。在评估F（n）之前先检查缓存，看看你是否已经为此计算了它。

1) Cache values of F(n) when they are evaluated the first time. Check the cache first before evaluating F(n) to see if you have already calculated it for this n.

2）使用迭代方法：计算F（1）， F（2），F（3）等......直到达到你需要的数字。

2) Use an iterative approach: Calculate F(1), F(2), F(3), etc... until you reach the number you need.

这篇关于Java程序Fibonacci序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！