C ++中的斐波那契数溢出

Question

我是c++新手，同时通过学习算法开始学习。但是，我在写这个算法的时候遇到了一些问题---数字溢出，这和我想的溢出有很大的不同。为了解决这个问题，我找了很久，没有用。这是我的代码：

#include <iostream>
using namespace std;

long long Fs[101];
long long F(int N) {
    if (Fs[N] != -1) {
        return Fs[N];
    }
    int res = F(N - 1) + F(N - 2);
    Fs[N] = res;
    return res;
}

void main() {
    // initialize Fs array
    for (auto& item : Fs) {
        item = -1;
    }
    Fs[0] = 0;
    Fs[1] = 1;
    cout << F(60) << endl;
    cout << endl;
    for (auto& item : Fs) {
        cout << item << endl;
    }
}

部分结果显示如下：

165580141
267914296
433494437
701408733
1134903170
1836311903
-1323752223
512559680
-811192543

问题:
可以看到溢出数比long long类型的最小值小很多。为什么会这样？

附录
我找到了一些在生成fibonacci时打印无符号类型溢出索引的方法，这里是代码：

#include <iostream>
#include <limits>
using namespace std;
 
#define outFibonacci(nType) { int i = 1;\
    while (i++)\
        if (Fibonacci<nType>(i+1)==Fibonacci<nType>(i+2)){\
            cout<<"F("<<i<<")\t= "<<Fibonacci<nType>(i)<<endl;\
            break;\
        }\
    cout<< "Max Num\t= " << numeric_limits<nType>::max() << endl << endl;\
    }
 
template<typename _T> _T Fibonacci(_T n){
    _T f, f1, f2;
    f = f1 = f2 = 1;
    for (auto i=3; i<=n; ++i){
        f = f1 + f2;
        if (f<f2){ // Set overflow condition
            f=-1;
            break;
        }
        f1 = f2;
        f2 = f;
    }
    return f;
}
 
int main(void)
{   
    outFibonacci(unsigned short);
    
    outFibonacci(unsigned int);
    outFibonacci(unsigned long);
    
    outFibonacci(unsigned long long);
    outFibonacci(size_t);
    
    return 0;
}

这是我的结果：

F(24)   = 46368
Max Num = 65535

F(47)   = 2971215073
Max Num = 4294967295

F(47)   = 2971215073
Max Num = 4294967295

F(93)   = 12200160415121876738
Max Num = 18446744073709551615

F(93)   = 12200160415121876738
Max Num = 18446744073709551615

Answer 1

函数中的这一行 int res = F(N - 1) + F(N - 2); 使你的结果成为 int，然后将其转换为 long long .所以溢出发生在这里。应该被一些编译器标志标记。

long long F(int N) {
    if (Fs[N] != -1) {
        return Fs[N];
    }
    // int res = F(N - 1) + F(N - 2); // HERE !
    long long res = F(N - 1) + F(N - 2);
    Fs[N] = res;
    return res;
}

C ++中的斐波那契数溢出

Fibonacci number overflow in c++

c++

algorithm