Java程序Fibonacci序列
我正在编写一个“简单”程序来确定Fibonacci序列中的第N个数字。 例如：序列中的第7个数字是：13。我已经完成了程序的编写，它可以工作，但从第40个数字开始它开始延迟，并且需要更长，更长。 我的节目必须到系列中的第100个位置。
我怎么解决这个问题所以它不需要这么长时间？ 这是非常基本的程序，所以我不知道所有花哨的语法代码..我的公式是：
if n =1 || n = 0 return n; else return F(n-1) + F(n-2); 这很有效，直到它超过第40个学期。 我需要添加什么其他声明才能更快地获得更高的数字？
问题是因为您使用简单递归，所以多次重新评估F（n），因此执行时间是指数级的。
有两种简单的方法可以解决这个问题：
1）第一次评估F（n）时的缓存值。 在评估F（n）之前先检查缓存，看看你是否已为此n计算了它。
2）使用迭代方法：计算F（1），F（2），F（3）等……直到达到所需的数字。
问题是你的算法虽然在数学上是纯粹的（并且很好）但并不是很好。
对于它想要计算的每个数字，它必须计算两个较低的数字，而这又需要计算两个较低的数字等。您当前的算法具有大约O（1.6 n ）的Big O符号复杂度，因此对于非常大的数字（例如100）它需要很长时间。
本书“计算机程序的结构和解释”有一个很好的图表 ：显示使用算法生成fib 5时会发生什么 
最简单的方法是存储F – 1和F – 2，这样您就不必每次都从头开始计算它们。 换句话说，不是使用递归，而是使用循环。 比意味着算法的复杂性从O（1.6 n ）变为O（n）。
有很多解决方案。 最直截了当的是使用memoization 。 还有Binet的公式 ，它会在恒定的时间内给你第n个斐波纳契数。
对于记忆，您将F [a_i]的结果存储在地图或某种列表中。 例如，在天真的递归中，你计算F [4]数十万次。 通过在找到它们时存储所有这些结果，递归停止像树一样继续，看起来就像直接的迭代解决方案。
如果这不是作业，请使用Binet的公式。 这是最快的方法。
试试这个例子，它在合理的时间范围内计算出百万分之斐波纳契数，而不会有任何精度损失。
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; } }
创建一个包含100个值的数组，然后在计算Fib（n）的值时，将其存储在数组中并使用该数组获取Fib（n-1）和Fib（n-2）的值。
如果你在不存储任何先前计算的值的情况下调用Fib（100），那么你将使你的java运行时爆炸。
伪代码：
array[0] = 0; array[1] = 1; for 2:100 array[n] = array[n-1] + array[n-2];
问题不是JAVA，而是你实现Fibonacci算法的方式。 您多次计算相同的值，这会降低您的程序速度。
试试这样的事： Fibonacci和memoization
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)
请注意，许多计算都会重复！ 需要注意的重要一点是此算法是指数的，因为它不存储先前计算的数字的结果。 例如，F（n-3）被称为3次。
更好的解决方案是下面写的迭代代码
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] }
有关更多详细信息，请参阅dasgupta第0.2章的算法
我使用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; } }
如果你使用天真的方法，你最终会得到爆炸数量相同的计算，即钙质（n）必须钙化（n-1）和fib（n-2）。 然后到calc fib（n-1）你必须钙化（n-2）和fib（n-3）等。更好的方法是反向。 您以fib（0），fib（1），fib（2）开始计算并将值存储在表中。 然后计算后续值，使用存储在表（数组）中的值。 这也是cao memoization。 试试这个，你应该能够计算大的纤维数。
这是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)
太慢了…
更好:( JavaScript示例）
function fibonacci(n) { var a = 0, b = 1; for (var i = 0; i < n; i++) { a += b; b = a - b; } return a; }
import java.util.*; public class FibonacciNumber { public static void main(String[] args) { int high = 1, low = 1; int num; Scanner in = new Scanner(System.in); try { System.out.print("Enter Number : " ); num = in.nextInt(); System.out.println( low); while(high < num && num < 2000000000) { System.out.println(high); high = low + high; low = high - low; } } catch (InputMismatchException e) { System.out.print("Limit Exceeded"); } } } /* Ouput : Enter Number : 1999999999 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 -1323752223 512559680 -811192543 -298632863 -1109825406 -1408458269 1776683621 368225352 */
朴素的实现是自然而优雅的，但在执行过程中，递归调用正在创建二叉树。 除了已经提到的memoization，兑现以前的F（n）结果并避免不必要的树遍历，你可以进行尾调用优化，已经提到了迭代或矩阵乘法。 例如，Java 8 memoization：
private static final Map memo = new HashMap<>(); static { memo.put(0L, 0L); memo.put(1L, 1L); } public static void main(String[] args) { System.out.println(fibonacci(0)); System.out.println(fibonacci(43)); System.out.println(fibonacci(92)); } public static long fibonacci(long n) { return memo.computeIfAbsent(n, m -> fibonacci(m - 1) + fibonacci(m - 2)); }
或者也许尾部调用优化版本：
interface FewArgs { public R apply(T t, U u, V v); } static FewArgs tailRecursive; static { tailRecursive = (a, b, n) -> { if (n > 0) return tailRecursive.apply(b, a + b, n - 1); return a; }; }
你用a = 0，b = 1来调用它，n是第n个Fibonacci数，但必须小于93.计算Fibonacci数的更有效的方法是矩阵平方，你会在我的博客上找到例子，Binet公式
您可以使用缓存技术。 由于f（n）= f（n-1）+ f（n-2），因此在计算f（n-1）时，再次计算f（n-2）。 所以简单地将它们视为两个增量数字，如下所示：
public int fib(int ithNumber) { int prev = 0; int current = 1; int newValue; for (int i=1; i
使用三元运算符的多个语句看起来更好。
static int fib(int n) { return n > 5 ? fib(n-2) + fib(n-1) : n < 2 || n == 5 ? n : n - 1; }