C++数字增加了一个负数

Question

所以我只是练习编码斐波那契序列的动态解决方案,它将返回第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只是用于调试

Answer 1

您需要更改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);
}

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

try {
    std::cout << "2000th number = " << fib(2000) << std::endl;
} catch( std::overflow_error& ex ) {
    std::cerr << ex.what() << std::endl; 
}