Java程序Fibonacci序列

Question

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

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

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

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

这很有效,直到它超过第40个学期.我必须添加什么其他声明才能更快地获得更高的数字？

Answer 1

问题是因为您使用简单递归,所以多次重新评估F(n),因此执行时间是指数级的.

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

1)第一次评估F(n)时的缓存值.在评估F(n)之前先检查缓存,看看你是否已经为此计算了它.

2)使用迭代方法:计算F(1),F(2),F(3)等......直到达到所需的数字.

Answer 2

问题是你的算法虽然在数学上是纯粹的(而且很好)但并不是很好.
对于它想要计算的每个数字,它必须计算两个较低的数字,而这又需要计算两个较低的数字等.您当前的算法具有大约O(1.6 ⁿ)的Big O符号复杂度,因此对于非常大的数字(例如100)它需要很长时间.

本书"计算机程序的结构和解释"有一个很好的图表:显示fib 5使用算法生成时会发生什么

最简单的方法是存储F - 1和F - 2,这样您就不必每次都从头开始计算它们.换句话说,使用循环而不是使用递归.比意味着算法的复杂性从O(1.6 ⁿ)变为O(n).

Answer 3

有很多解决方案.最直接的是使用memoization.还有Binet的公式,它会在恒定的时间内给你第n个斐波纳契数.

对于memoization,您将F [a_i]的结果存储在地图或某种列表中.例如,在天真的递归中,你计算F [4]数十万次.通过在找到它们时存储所有这些结果,递归就像树一样停止,看起来就像直接的迭代解决方案.

如果这不是作业,请使用Binet的公式.这是最快的方法.

Answer 4

试试这个例子，它在合理的时间范围内计算出百万分之一的斐波那契数，而不会损失任何精度。

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;
    }
}