2

所以我只是在练习为斐波那契数列编写一个动态解决方案，它会返回第 n 个斐波那契数，但我一直遇到一个我无法弄清楚的问题。我得到两个正数加上一个负数！

代码：

int fib(int n) {
    vector<int> v;
    v.push_back(1);
    v.push_back(1);
    for (int i = 2; i <= n; i++) {
        v.push_back( v.at(i-1) + v.at(i-2) );
        cout << v.at(i-1) << " + " << v.at(i-2) << " = " << (v.at(i-1) + v.at(i-2)) << endl;
    }
    return v.at(n);
}

尝试运行 fib(50)，注意 cout 仅用于调试

在此处输入图像描述

4

2 回答 2

7

int你需要改成unsigned int甚至更好unsigned long long。您的结果超出了系统上的最大值int。因为int是有符号的，所以当最高有效位被设置时，它变成一个负数。有关更多信息，请参阅标题为 int 的最大值的 Stack Overflow 问题，以及有关二进制算术的 Swarthmore College 页面。如果您使用的是 Visual Studio，请查看 MSDN 上的数据类型范围文章。

除了切换到 之外unsigned long long，您还应该检查诸如此类的溢出错误并抛出异常。您的代码的修订版本可能如下所示。

unsigned long long fib(int n) {
    vector<unsigned long long> v;
    v.push_back(1);
    v.push_back(1);
    for (int i = 2; i <= n; i++) {
        if( v.at(i-1) > (std::numeric_limits<unsigned long long>::max() - v.at(i-2)) )
            throw std::overflow_error("number too large to calculate");
        v.push_back( v.at(i-1) + v.at(i-2) );
        cout << v.at(i-1) << " + " << v.at(i-2) << " = " << (v.at(i-1) + v.at(i-2)) << endl;
    }
    return v.at(n);
}

您还需要确保调用您的函数的代码可以使用try... catch.... 这是一个例子

try {
    std::cout << "2000th number = " << fib(2000) << std::endl;
} catch( std::overflow_error& ex ) {
    std::cerr << ex.what() << std::endl; 
}
于 2013-09-08T04:22:18.083 回答
2

由于 C 如何将您的int(signed int) 存储在内存中，最高有效位表示负数。所以如果你用大数溢出它，你会得到负数。

参考：

于 2013-09-08T04:32:31.470 回答