为什么斐波那契数列的计算中偶尔会出现负值？ [重复]

Question

我用C++编写了一个计算斐波那契数列的程序。代码如下：

#include <iostream>
using namespace std;

int main() {
    int n, t1 = 0, t2 = 1, nextTerm = 0;

    cout << "Enter the number of terms: ";
    cin >> n;
    cout << endl;

    cout << "Fibonacci Series: ";

    for (int i = 1; i <= n; ++i) {
        // Prints the first two terms.
        if(i == 1) {
            cout << t1 << ", ";
            continue;
        }
        if(i == 2) {
            cout << t2 << ", ";
            continue;
        }
        nextTerm = t1 + t2;
        t1 = t2;
        t2 = nextTerm;

        cout << nextTerm << ", ";
    }
    cout << endl;
    return 0;
}

当我输入

n = 100

时，列表就会增长。并且出现了一些负数。

我知道这是由于数据类型值限制而发生的。但我的问题是 为什么有些是负面的，有些是正面的价值。
喜欢

-285007387, -945834654, -1230842041, 2118290601, 887448560, -1289228135, -401779575, -1691007710, 

这是输出中间某处的示例。

Enter the number of terms: 100
Fibonacci Series: 0, 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, 2144908973, -1781832971, 363076002, -1418756969, -1055680967, 1820529360, 764848393, -1709589543, -944741150, 1640636603, 695895453, -1958435240, -1262539787, 1073992269, -188547518, 885444751, 696897233, 1582341984, -2015728079, -433386095, 1845853122, 1412467027, -1036647147, 375819880, -660827267, -285007387, -945834654, -1230842041, 2118290601, 887448560, -1289228135, -401779575, -1691007710, -2092787285, 511172301, -1581614984, -1070442683, 1642909629, 572466946, -2079590721, -1507123775, 708252800, -798870975, -90618175, -889489150, 
Process finished with exit code 0

Answer 1

斐波那契数列中同时出现正数和负数是由于整数溢出。

当整数溢出时，它的值会回绕。对于有符号整数（通常使用二进制补码表示），当值超过数据类型可表示的最大正值时，它会“回绕”到最大负值并继续减小。这解释了为什么在达到较大的正值后您会看到负值。

例如，使用 32 位有符号整数：

• 当超过最大正值（2,147,483,647）时，该值 环绕到最大负值 (-2,147,483,648)。
• 然后它继续向更多负值减小，直到 达到最小可表示值 (-2,147,483,648)，之后 它会再次溢出并环绕到最大正值 值，形成正值到负值的循环。

这就是为什么在斐波那契数列中，在达到导致溢出的大正数后，您开始看到负值，并且当溢出结束时，序列继续以正负数交替。

Answer 2

如您所知，负数的出现是由数据类型值限制引起的。
让我们考虑一下您在代码中使用的数据类型，

int

。数据类型

int

的值限制为

from -2^31 to 2^31-1

，等于

from -2147483648 to 2147483647

。
当

int

类型的值溢出范围外时，它会增加或减少范围跨度的倍数，等于

2^32

，以保持该值在

int

范围内。
例如，如果将

2147483648

放入

int

类型的变量中，则该变量中的实际值为

2147483648-2^32

，等于

-2147483648

。
现在让我们考虑一下示例的输出：

-285007387, -945834654, -1230842041, 2118290601, 887448560, -1289228135, -401779575, -1691007710

第三个数字等于前两个数字

-285007387

和

-945834654

之和，等于

(-285007387)+(-945834654)=-1230842041

，并且该数字在范围内，所以第三个数字是

-1230842041

。第四个数字等于

(-945834654)+(-1230842041)=-2176676695

，但是这个数字超出了范围，所以我们将它增加

2^32

，所以它变成了

(-2176676695)+2^32=2118290601

。

计算示例输出后，我们可以看到输出满足此定律，确保值在类型

int

的值范围内。而且因为只是保证在范围之内，实际上没有什么特殊的理由或方法可以知道它是正数还是负数。换句话说，除了计算之外，没有什么特殊的原因来决定该值的正负。