为什么用电脑算斐波那契数算到第46为就变成负数了

Question

为什么用电脑算斐波那契数算到第46为就变成负数了

#include<bits/stdc++.h>
using namespace std;
int a[1000005]={0,1,1,2,3};
int main(){
    int k;
    cin>>k;
    int i;
    queue<int>q;
    int cnt=0;
    int t[1]={0};
    for(i=4;i<=k;i++)
    {
        a[i]=a[i-2]+a[i-1];
    }
    for(int i=1;i<=k;i++)
    {
        printf("第%d天",i);
        cout<<a[i]<<endl;
    }
    return 0;
}

Answer 1

以下回复参考：皆我百晓生、券券喵儿等免费微信小程序作答:

这个问题可能是由于在计算斐波那契数列的过程中出现了溢出。当数列中的数字变得非常大时，可能会导致数据类型超出其所能表示的范围。在计算斐波那契数列的第46项时，可能会因为数值过大而导致溢出，从而产生负数或其他错误的结果。解决这个问题的一个方法是使用更大的数据类型来存储斐波那契数列中的数字，例如使用 long long 类型来替代 int 类型。同时，在输出之前进行检查，确保结果仍然是正数。下面是修改后的代码示例：

#include <bits/stdc++.h>
using namespace std;
long long a[1000005] = {0, 1, 1}; // 使用 long long 类型来存储斐波那契数列的数字

int main() {
    int k;
    cin >> k;
    int i;
    for (i = 3; i <= k; i++) { // 从第3项开始计算斐波那契数列，因为已经初始化了前两个数字
        a[i] = a[i - 2] + a[i - 1]; // 计算斐波那契数列的第i项
        if (a[i] < 0) { // 检查是否溢出
            cout << "计算过程中发生了溢出！" << endl;
            return 1; // 如果溢出，返回错误码
        }
    }
    for (int i = 1; i <= k; i++) {
        printf("第%d项: ", i); // 输出为第i项，而不是第几天
        cout << a[i] << endl; // 输出斐波那契数列的第i项的值
    }
    return 0;
}

请注意，即使使用 long long 类型，对于非常大的斐波那契数列项，仍然可能会发生溢出。因此，对于非常大的输入值，可能需要使用特殊的算法或数据结构来处理斐波那契数列的计算。