我们来做个练习吧。
下面我留下一个代码，返回斐波那契数列 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);
}
}
运行代码时，您会注意到两个主要问题：
我们的循环永远不会结束，而且奇怪的是，负数开始出现在控制台中。
随着时间的推移，代码变得越来越慢。
暂时忽略所有这些斐波那契数，看看这段代码。
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 的数字，因此循环从未停止。
为了简单起见，我只需将 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 的最大数。
你注意到什么了吗？每次循环迭代时，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中文网其他相关文章！
