C++利用高精度算法计算斐波那契

在C++中，当斐波那契数列的项数较大时，普通的整型变量无法存储这些数值，因为它们会超出标准数据类型如`int`或`long long`的存储范围。为了处理这种情况，需要使用高精度算法来计算斐波那契数列的数值。高精度算法通常通过数组或向量等数据结构来存储大数，通过模拟手工计算的方式来实现加法。

以下是一个简单的高精度算法实现斐波那契数列的例子：

#include <iostream>
#include <vector>

std::vector<int> add(const std::vector<int>& a, const std::vector<int>& b) {
    std::vector<int> result;
    int carry = 0;  // 进位
    int sum = 0;
    
    // 确保a是较长的数
    const std::vector<int>& first = (a.size() > b.size()) ? a : b;
    const std::vector<int>& second = (a.size() > b.size()) ? b : a;
    
    for (size_t i = 0; i < first.size(); ++i) {
        sum = carry + first[i];
        if (i < second.size()) {
            sum += second[i];
        }
        result.push_back(sum % 10); // 当前位的数字
        carry = sum / 10;           // 计算进位
    }
    
    if (carry > 0) {
        result.push_back(carry);
    }
    
    return result;
}

std::vector<int> fibonacci(int n) {
    if (n <= 1) {
        return {n};
    }
    
    std::vector<int> fib(2, 0);
    fib[1] = 1;
    
    for (int i = 2; i <= n; ++i) {
        fib = add(fib, fib);
        // 移除前导零
        while (fib.size() > 1 && fib.back() == 0) {
            fib.pop_back();
        }
    }
    
    return fib;
}

int main() {
    int n;
    std::cout << "请输入要计算的斐波那契数列项数: ";
    std::cin >> n;
    
    std::vector<int> result = fibonacci(n);
    
    // 由于结果是从最低位开始存储的，因此需要反向打印
    for (auto it = result.rbegin(); it != result.rend(); ++it) {
        std::cout << *it;
    }
    
    return 0;
}

这段代码定义了两个函数：`add`用于执行高精度加法，`fibonacci`用于计算斐波那契数列。在`fibonacci`函数中，我们使用两个`std::vector<int>`类型的数组来存储大整数，并通过模拟手工加法的方式来计算斐波那契数列。