斐波那契数列：当数组大小 > 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？我只是简单地用运行占位符来表示数字吗？欢迎评论。

P.S。我还没有递归地重写这个。不过我不太担心。

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

Answer 1

您的循环 for (int i = 0; i < SIZE; i++) { fib[i + 1] = fib[i] + fib[i - 1]; sum = sum + fib[i + 1]; } 正在 fib 数组外写入。具体是写在i=fib[i + 1]-1的位置fib[i + 1]=SIZE。总和 sum = sum + fib[i + 1];

也是如此

为 i==0

访问 fib[i - 1] 时发生类似错误

Answer 2

你有：

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];
}

PS

重要的是要注意，如果 SIZE 的值大于 44，sum 会溢出，如果 sizeof(int) 为 4。当 SIZE 超出这些限制时，将需要使用 long 或 long long。

Answer 3

请格式化您的代码以便更好地阅读 for 循环。

为什么把fib[0]和fib[1]设为1.SIZE次？

所以 fib[0] 之后肯定是 1 :)

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

但是不管第二个循环的开销如何fib[0]仍然是1但是fib[1]变成了fib[0] + fib[-1]

fib[-1] 是一个非常糟糕的索引，会导致随机行为。

这是它的工作原理：http://cpp.sh/54dg

#include <iostream>
#include <string>

using namespace std;

const int SIZE = 30;
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 = 1; i < SIZE-1; 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;
}

斐波那契数列：当数组大小 > 28 时，元素没有意义

Array of Fibonacci numbers: Elements do not make sense when array size > 28

c++

arrays

iteration

fibonacci

dev-c++