java Java程序斐波那契数列
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1799990/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Java Program Fibonacci Sequence
提问by Javadork
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.
我正在编写一个“简单”的程序来确定斐波那契数列中的第 N 个数字。例如：序列中的第 7 个数字是：13。我已经完成了程序的编写，它可以工作，但是从第 40 个数字开始它开始延迟，并且花费的时间越来越长。我的节目必须排在系列赛的第 100 位。
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);
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??
这很好用，直到它超过第 40 个学期。我还必须添加什么其他语句才能使其更快地获得更高的数字？
回答by Mark Byers
The problem is that because you are using simple recursion, you re-evaluate F(n) multiple times, so your execution time is exponential.
问题在于，因为您使用的是简单递归，所以您多次重新评估 F(n)，因此您的执行时间是指数级的。
There are two simple ways to fix this:
有两种简单的方法可以解决这个问题：
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.
1) 在第一次评估 F(n) 时缓存它们的值。在评估 F(n) 之前先检查缓存，看看你是否已经为这个 n 计算过它。
2) Use an iterative approach: Calculate F(1), F(2), F(3), etc... until you reach the number you need.
2) 使用迭代方法：计算 F(1)、F(2)、F(3) 等...直到达到您需要的数字。
回答by Yacoby
The issue is that your algorithm, while mathematically pure (and nice) isn't very good.
For every number it wants to calculate, it has to calculate two lower ones which in turn have to calculate two lower ones, etc. Your current algorithm has a Big O notationcomplexity of about O(1.6n), so for very large numbers (100 for example) it takes a long time.
问题是你的算法虽然在数学上纯粹（而且很好）并不是很好。
对于它想要计算的每个数字，它必须计算两个较低的数字，而后者又必须计算两个较低的数字，依此类推。您当前的算法的大 O 符号复杂度约为O(1.6 n)，因此对于非常大的数字（例如 100）需要很长时间。
This book, Structure and Interpretation of Computer programs has a nice diagram: showing what happens when you generate fib 5with your algorithm
(source: mit.edu)
这本书，计算机程序的结构和解释有一个很好的图表：显示当你fib 5用你的算法生成时会发生什么（来源：mit.edu）
The simplest thing to do is to store F - 1 and F - 2, so that you don't have to calculate them from scratch every time. In other words, rather than using recursion, use a loop. Than means that the complexity of the algorithm goes from O(1.6n) to O(n).
最简单的做法就是存储F-1和F-2，这样就不用每次都从头开始计算了。换句话说，与其使用递归，不如使用循环。Than 意味着算法的复杂度从 O(1.6 n) 到 O(n)。
回答by Stefan Kendall
There are a number of solutions. The most straightforward is to use memoization. There's also Binet's formulawhich will give you the nth fibonacci number in constant time.
有多种解决方案。最直接的是使用memoization。还有比奈公式，它会在恒定时间内为您提供第 n 个斐波那契数。
For memoization, you store your results for F[a_i] in a map or list of some kind. In the naive recursion, you compute F[4] hundreds of thousands of times, for example. By storing all these results as you find them, the recursion ceases to proceed like a tree and looks like the straightforward iterative solution.
为了记忆，您将 F[a_i] 的结果存储在某种地图或列表中。例如，在朴素递归中，您计算 F[4] 数十万次。通过在您找到所有这些结果时存储它们，递归不再像一棵树一样进行，而看起来像是直接的迭代解决方案。
If this isn't homework, use Binet's formula. It's the fastest method available.
如果这不是家庭作业，请使用比奈公式。这是最快的方法。
回答by Peter Lawrey
Try this example, it calculates the millionth Fibonacci number in a reasonable time frame without any loss of precision.
试试这个例子，它在合理的时间范围内计算出百万分之一的斐波那契数，而不会损失任何精度。
import java.math.BigInteger;
/*
250000th fib # is: 36356117010939561826426 .... 10243516470957309231046875
Time to compute: 3.5 seconds.
1000000th fib # is: 1953282128707757731632 .... 93411568996526838242546875
Time to compute: 58.1 seconds.
*/
public class Fib {
public static void main(String... args) {
int place = args.length > 0 ? Integer.parseInt(args[0]) : 1000 * 1000;
long start = System.nanoTime();
BigInteger fibNumber = fib(place);
long time = System.nanoTime() - start;
System.out.println(place + "th fib # is: " + fibNumber);
System.out.printf("Time to compute: %5.1f seconds.%n", time / 1.0e9);
}
private static BigInteger fib(int place) {
BigInteger a = new BigInteger("0");
BigInteger b = new BigInteger("1");
while (place-- > 1) {
BigInteger t = b;
b = a.add(b);
a = t;
}
return b;
}
}
回答by Simon Righarts
Create an array with 100 values, then when you calculate a value for Fib(n), store it in the array and use that array to get the values of Fib(n-1) and Fib(n-2).
创建一个包含 100 个值的数组，然后在计算 Fib(n) 的值时，将其存储在数组中并使用该数组来获取 Fib(n-1) 和 Fib(n-2) 的值。
If you're calling Fib(100) without storing any of the previously calculated values, you're going to make your java runtime explode.
如果您调用 Fib(100) 而不存储任何先前计算的值，您将使您的 Java 运行时爆炸。
Pseudocode:
伪代码：
array[0] = 0;
array[1] = 1;
for 2:100
array[n] = array[n-1] + array[n-2];
回答by Igor Rybak
My solution using Java 8 Stream:
我使用 Java 8 Stream 的解决方案：
public class Main {
public static void main(String[] args) {
int n = 10;
Fibonacci fibonacci = new Fibonacci();
LongStream.generate(fibonacci::next)
.skip(n)
.findFirst()
.ifPresent(System.out::println);
}
}
public class Fibonacci {
private long next = 1;
private long current = 1;
public long next() {
long result = current;
long previous = current;
current = next;
next = current + previous;
return result;
}
}
回答by Amandeep Kamboj
F(n)
/ \
F(n-1) F(n-2)
/ \ / \
F(n-2) F(n-3) F(n-3) F(n-4)
/ \
F(n-3) F(n-4)
Notice that many computations are repeated! Important point to note is this algorithm is exponential because it does not store the result of previous calculated numbers. eg F(n-3) is called 3 times.
请注意，许多计算是重复的！需要注意的重要一点是这个算法是指数的，因为它不存储先前计算的数字的结果。例如 F(n-3) 被调用 3 次。
Better solution is iterative code written below
更好的解决方案是下面写的迭代代码
function fib2(n) {
if n = 0
return 0
create an array f[0.... n]
f[0] = 0, f[1] = 1
for i = 2...n:
f[i] = f[i - 1] + f[i - 2]
return f[n]
}
For more details refer algorithm by dasgupta chapter 0.2
有关更多详细信息，请参阅 dasgupta 第 0.2 章的算法
回答by Soufiane Hassou
The problem is not JAVA, but the way you are implementing your Fibonacci algorithm. You are computing the same values many times, which is slowing your program.
问题不在于 JAVA，而在于您实现斐波那契算法的方式。您多次计算相同的值，这会减慢您的程序速度。
Try something like this : Fibonacci with memoization
尝试这样的事情：Fibonacci with memoization
回答by paweloque
If you use the naive approach, you'll end up with an exploding number of same calculations, i.e. to calc fib(n) you have to calc fib(n-1) and fib(n-2). Then to calc fib(n-1) you have to calc fib(n-2) and fib(n-3), etc. A better approach is to do the inverse. You calc starting with fib(0), fib(1), fib(2) and store the values in a table. Then to calc the subsequent values you use the values stored in a table (array). This is also caled memoization. Try this and you should be able to calc large fib numbers.
如果你使用天真的方法，你最终会得到大量相同的计算，即计算 fib(n) 你必须计算 fib(n-1) 和 fib(n-2)。然后计算 fib(n-1) 你必须计算 fib(n-2) 和 fib(n-3) 等等。更好的方法是做相反的事情。您从 fib(0)、fib(1)、fib(2) 开始计算并将值存储在表中。然后使用存储在表（数组）中的值来计算后续值。这也称为记忆。试试这个，你应该能够计算出大的 fib 数字。
回答by Swapneel Patil
This is the code in Python, which can easily be converted to C/Java. First one is recursive and second is the iterative solution.
这是 Python 中的代码，可以很容易地转换为 C/Java。第一个是递归的，第二个是迭代的解决方案。
def fibo(n, i=1, s=1, s_1=0):
if n <= i: return s
else: return fibo(n, i+1, s+s_1, s)
def fibo_iter_code(n):
s, s_1 = 1, 0
for i in range(n-1):
temp = s
s, s_1 = s+s_1, temp
print(s)
