斐波那契、整数溢出、记忆 e um exagero

我们来做个练习吧。
下面我留下一个代码，返回斐波那契数列 n 位置上的数字：

public static int fib(int n){
   if (n <= 1){
     return n;
   }
   return fib(n-1) + fib(n-2);
}

我们尝试在终端中显示斐波那契数列中小于 2147483647 的所有数字怎么样？

    public static int fib(int n){
       if (n <= 1){
           return n;
       }
       return fib(n-1) + fib(n-2);
    }

    public static void main(String[] args) {
        int position = 1;
        int currentNumber = fib(position);

        while (currentNumber < 2147483647) {
            System.out.println(currentNumber);
            position++;
            currentNumber = fib(position);
        }
    }

存在的问题

运行代码时，您会注意到两个主要问题：

• 我们的循环永远不会结束，而且奇怪的是，负数开始出现在控制台中。
  

• 随着时间的推移，代码变得越来越慢。

问题1：负数

暂时忽略所有这些斐波那契数，看看这段代码。

public static void main(String[] args) {
   int a = 2_000_000_000;
   int b = 2_000_000_000;
   System.out.println(a + b);
}

你认为这样做的结果会是多少？ 20亿20亿=40亿对吗？所以在我们的代码中结果将是 40 亿...对吧？

错误！

出路其实是这样的：

造成这个结果的原因是溢出。 int 类型的最大限制为 2147483647（或 2^31 - 1）。当超过此限制时，该值将“返回”为 int 类型的最低可能值，即 -2147483648。

为什么我们的循环没有停止？

当我们达到大于或等于 2147483647 的数字时，我们的循环应该停止，但是当斐波那契值超过 int 限制时，开始生成负数。由于我们从未达到大于 2147483647 的数字，因此循环从未停止。

问题1的解决方案

为了简单起见，我只需将 fib 函数的返回类型从 int 更改为 long，后者具有更大的限制。我们的代码将如下所示：

    public static long fib(long n){
       if (n <= 1){
           return n;
       }
       return fib(n-1) + fib(n-2);
    }

    public static void main(String[] args) {
        long position = 1;
        long currentNumber = fib(position);

        while (currentNumber < 2147483647) {
            System.out.println(currentNumber);
            position++;
            currentNumber = fib(position);
        }
    }

现在，使用 long 类型，我们可以正确打印斐波那契数列，直到小于 2147483647 的最大数。

解决问题2：缓慢

你注意到什么了吗？每次循环迭代时，fib 函数都会重新计算序列中所有先前的数字。换句话说，我们正在重复不必要的计算。

如何避免不必要的重新计算？我向您介绍：记忆化。记忆技术是一种保存已计算结果的方法，以免再次进行计算过程。

让我们实现一个 HashMap 来存储已经找到的值，其中键是位置，值是数字本身。

    static HashMap<Long, Long> memo = new HashMap<>();

    public static long fib(long n) {
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        if (n <= 1) {
            return n;
        }
        long result = fib(n - 1) + fib(n - 2);
        memo.put(n, result);
        return result;
    }

    public static void main(String[] args) {
        long position = 1;
        long currentNumber = fib(position);

        while (currentNumber < 2147483647) {
            System.out.println(currentNumber);
            position++;
            currentNumber = fib(position);
        }
    }

美丽！现在我们的代码运行得更快了，我们解决了问题。

夸张之处

实际上，这里不需要记忆。我只是想把这个概念带到教学中。我们可以简单地计算每个斐波那契数，直到完成我们的条件，如下所示：

    public static void main(String[] args) {
        long prev1 = 0;
        long prev2 = 1;
        long current;

        System.out.println(prev1);

        while (prev2 < 2147483647) {
            System.out.println(prev2);
            current = prev1 + prev2;
            prev1 = prev2;
            prev2 = current;
        }
    }

我已经玩够了，对吧？对不起！但至少你学到了一些新东西。

---

文章封面作者：Gerd Altmann，来自 Pixabay

以上是斐波那契、整数溢出、记忆 e um exagero的详细内容。更多信息请关注PHP中文网其他相关文章！