时间戳

首页 > 解决方案 > 使用 BigInteger 的斐波那契数列不产生答案

java - 使用 BigInteger 的斐波那契数列不产生答案

问题描述

我要找到斐波那契数列的第 100 个元素，我最初尝试使用 an 存储数字的值，int但它溢出并切换到负值，就像long.
然后我发现BigInteger我确实使用一个简单的for循环和一个array来存储结果并访问以前的元素得到了解决方案。
现在，当我尝试使用该程序来解决相同的问题时，recursion该程序似乎并没有终止。我在这里错过了什么吗？或者BigInteger不建议与递归一起使用？

这是代码：

import java.math.BigInteger;

class Test {
  public static void main(String[] args) {
    BigInteger n = BigInteger.valueOf(100);
    System.out.println(fib(n));
  }

  public static BigInteger fib(BigInteger n) {
    if (n.compareTo(BigInteger.valueOf(1)) == 0 || n.compareTo(BigInteger.valueOf(1)) == -1)
      return n;
    return fib(n.subtract(BigInteger.valueOf(1))).add(fib(n.subtract(BigInteger.valueOf(2))));
  }
}

标签： javarecursionfibonacci

解决方案

在评论中，您提到您认为程序不会终止的假设是基于它运行了 5 分钟以上的事实。这不是你证明不终止的方式。

如果您观察到程序在一定时间内终止，那么您可以得出结论，它确实终止了。但是，如果您没有观察到它在一定时间内终止，那么您就无法准确地说它是否终止。如果你等待的时间长一点它可能会终止，如果你等待的时间更长它可能会终止，甚至理论上它可能会终止但比宇宙的热寂需要更长的时间。

在您的特定情况下，该算法是完全正确的，并且它总是终止。它根本不是一个非常有效的算法：对于计算fib(n)，fib被称为 fib(n) 次，因为你一遍又一遍地计算相同的数字。

如果我们假设您可以fib每个时钟周期执行一次（这是一个乐观的假设，因为在大多数情况下，一次调用fib执行一个条件、两次减法、一次加法和两次调用fib，并且一次加法可能已经花费了多个时钟周期取决于 CPU），我们进一步假设你有一个 100 核 CPU，你的代码实际上是并行执行的，你有 100 个 CPU，每个 CPU 的时钟频率为 100 GHz，你有一个由 100 台计算机组成的集群，那么它仍然需要你大约一个小时。

在一些更现实的假设下，您的程序完成所需的时间更多的是数万年。

由于您的代码没有并行化，为了让您的代码在更真实的 4 GHz CPU 上在 5 分钟内完成，它需要在每个时钟周期fib执行近 3亿次。

对代码的预期性能进行一些非常粗略的猜测通常会有所帮助。如您所见，您无需成为 Java 或 JVM 或编译器或优化或计算机组织或 CPU 设计或性能工程方面的专家。你不需要知道你的代码究竟被编译成什么。您不需要知道整数ADD需要多少个时钟周期。因为即使你做了一些完全过分荒谬的假设，你仍然可以很容易地看到你的代码不可能在几分钟甚至几小时内完成。

推荐阅读