5

我正在编写一个“简单”程序来确定斐波那契数列中的第 N 个数字。例如：序列中的第 7 个数字是：13。我已经完成了程序，它可以工作，但是从第 40 个数字开始它开始延迟，并且花费的时间越来越长。我的程序必须排到该系列的第 100 位。

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

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

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

在超过第 40 个任期之前，这很有效。我还必须添加什么其他语句才能使其更快地获得更高的数字？

4

15 回答 15

10

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

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

1) 第一次评估时缓存 F(n) 的值。在评估 F(n) 之前先检查缓存，看看您是否已经为这个 n 计算过它。

2) 使用迭代方法：计算 F(1)、F(2)、F(3) 等……直到达到所需的数字。

于 2009-11-25T21:17:32.610 回答
7

问题是您的算法虽然在数学上很纯（而且很好），但并不是很好。
对于它要计算的每个数字，它必须计算两个较低的数字，而后者又必须计算两个较低的数字，等等。您当前的算法的Big O 符号复杂度约为O(1.6 n )，因此对于非常大的数字 (例如 100）需要很长时间。

这本书，计算机程序的结构和解释有一个很好的图表：显示当你fib 5用你的算法生成时会发生什么（来源：mit.edu）

最简单的做法是存储 F-1 和 F-2，这样就不必每次都从头开始计算。换句话说，与其使用递归，不如使用循环。比意味着算法的复杂度从 O(1.6 n ) 到 O(n)。

于 2009-11-25T21:20:59.670 回答
6

有许多解决方案。最直接的就是使用memoization。还有比内公式，它可以在恒定时间内为您提供第 n 个斐波那契数。

对于记忆，您将 F[a_i] 的结果存储在某种地图或列表中。例如，在朴素递归中，您计算​​ F[4] 数十万次。通过在找到它们时存储所有这些结果，递归不再像树一样进行，看起来像直接的迭代解决方案。

如果这不是家庭作业，请使用比内公式。这是最快的方法。

于 2009-11-25T21:15:57.980 回答
5

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

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;
    }
}
于 2009-11-25T21:38:38.390 回答
2

创建一个包含 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];
于 2009-11-25T21:20:13.247 回答
1 
                           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 章的算法

于 2014-03-04T07:34:54.587 回答
1

问题不在于 JAVA，而在于您实现斐波那契算法的方式。您多次计算相同的值，这会减慢您的程序。

尝试这样的事情：Fibonacci with memoization

于 2009-11-25T21:18:04.853 回答
1

我使用 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;
    }
}
于 2017-07-14T21:03:26.260 回答
0

太慢了...

更好：（JavaScript 示例）

function fibonacci(n) {
    var a = 0, b = 1;

    for (var i = 0; i < n; i++) {
        a += b;
        b = a - b;
    }
    return a;
}
于 2011-10-03T20:55:27.070 回答
0

如果您使用幼稚的方法，您最终会得到大量相同的计算，即要计算 fib(n)，您必须计算 fib(n-1) 和 fib(n-2)。然后要计算 fib(n-1)，您必须计算 fib(n-2) 和 fib(n-3) 等。更好的方法是逆向计算。您从 fib(0)、fib(1)、fib(2) 开始计算并将值存储在表中。然后使用存储在表（数组）中的值来计算后续值。这也称为记忆。试试这个，你应该能够计算出大的 fib 数。

于 2009-11-25T21:19:56.850 回答
0

这是 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)
于 2010-03-05T20:37:18.357 回答
0 
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   */
于 2014-09-19T12:50:53.063 回答
0

朴素的实现是自然而优雅的，但在执行过程中递归调用正在创建二叉树。除了已经提到的记忆化、先前 F(n) 结果的兑现和避免不必要的树遍历之外，您还可以进行尾调用优化，已经提到了迭代或矩阵乘法。例如，Java 8 记忆：

private static final Map<Long, Long> 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<T, U, V, R> {
  public R apply(T t, U u, V v);
}

static FewArgs<Long, Long, Long, Long> 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 个斐波那契数，但必须小于 93。计算斐波那契数的更有效方法是矩阵平方，你可以在我的博客上找到示例，以及 Binet 公式

于 2015-05-16T03:54:34.893 回答
0

您可以使用缓存技术。由于 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<ithNumber; i++) {
        newValue = current + prev;
        prev = current;
        current = newValue;
    }
    return current;
}
于 2015-06-03T10:06:59.567 回答
0

使用三元运算符的多个语句看起来更好。

static int fib(int n) {
        return  n > 5 ? fib(n-2) + fib(n-1)
                      : n < 2 || n == 5 ? n
                                        : n - 1;
}
于 2016-01-30T21:46:04.837 回答