c++ - 斐波那契数列 : Elements do not make sense when array size > 28

Question

我有一个简短的 C++ 程序，它填充一个斐波那契数列，然后计算各项的总和，并将总和显示到屏幕上。

#include <iostream>

using namespace std;

const int SIZE = 10;

int main() {
    int sum = 0; // running sum
    int fib[SIZE]; // array of Fibonacci numbers

    // initialize 1st and 2nd elements = 1, the rest to 0
    for (int i = 2; i < SIZE; i++) { 
        fib[0] = 1; 
        fib[1] = 1; 
        fib[i] = 0; 
    }

    // populate the array:
    // next term in Fibonacci sequence: fib[current] - 1 + fib[current] - 2
    for (int i = 0; i < SIZE; i++) { 
        fib[i + 1] = fib[i] + fib[i - 1]; 
        sum = sum + fib[i + 1]; 
    }

    // display the contents and the sum
    for (int i = 0; i < SIZE; i++) { 
        cout << i + 1 << ": " << fib[i] << endl; 
    }
    cout << "\nSum of the Fibonacci numbers: " << sum << endl;

    //system("pause");
    return 0;
}

当我从 SIZE = 10 开始时，程序将总和相加...

输出:

1: 1
2: 1
3: 2
4: 3
5: 5
6: 8
7: 13
8: 21
9: 34
10: 55

Sum of the Fibonacci numbers: 231

--------------------------------
Process exited after 0.02942 seconds with return value 0
Press any key to continue . . .

事实上，SIZE 的任何值在 2 到 28 之间都可以。我得到了总和的正确正值。

但是，当我尝试定义 SIZE = 29 或更大时，会发生这种情况:

输出:

1: 1
2: 32764
3: 32765
4: 65529
5: 98294
6: 163823
7: 262117
8: 425940
9: 688057
10: 1113997
.
.
.
25: 1519229809
26: -1836801828
27: -317572019
28: 2140593449
29: 1823021430

Sum of the Fibonacci numbers: 1160283831

--------------------------------
Process exited after 0.05147 seconds with return value 0
Press any key to continue . . .

我不明白为什么第二个元素从 1 变为 32764，以及为什么当我定义 SIZE = 29 或更大时数组中有负值。实际上，我将开始获取随机值，并且在每次编译和运行后每个值都异常不同。

这与编译有关吗？也许将数据类型从 int 更改为 long？我只是用完了占位符来表示数字吗？欢迎提出意见。

附言我还没有递归地重写这个。但我不太担心。

编辑:非常感谢您的评论。我每次都能学到新东西。

Answer 1

你有:

for (int i = 0; i < SIZE; i++)
{
   fib[i + 1] = fib[i] + fib[i - 1];
   sum = sum + fib[i + 1];
}

对于 i == 0 ，您正在访问 fib[i-1] ，即 fib[-1] .
对于 i == SIZE-1 ，您正在访问 fib[SIZE] .
它们是未定义行为的原因。

你需要使用:

sum = 2; // Takes care of fib[0] and fib[1]
for (int i = 1; i < SIZE-1; i++)
{
   fib[i + 1] = fib[i] + fib[i - 1];
   sum += fib[i + 1];
}

附言

重要的是要注意 sum溢出 SIZE 的值大于 44 和 fib[SIZE-1]溢出 SIZE 的值大于 46 如果 sizeof(int)是 4. long 的使用或 long long当 SIZE 时将是必要的超出了这些限制。