斐波那契数列 高精度

斐波那契数列是一个数列，其中每个数字都是前两个数字的和。通常，斐波那契数列的前两个数字是0和1。

如果要计算斐波那契数列中的第n个数字（n从0开始），可以使用高精度算法来处理，以避免溢出或精度丢失。以下是一个使用高精度算法计算斐波那契数列的示例代码：

#include <iostream>
#include <vector>

// 高精度加法
std::vector<int> add(const std::vector<int>& num1, const std::vector<int>& num2) {
    std::vector<int> result;
    int carry = 0;
    int i = num1.size() - 1;
    int j = num2.size() - 1;
    
    while (i >= 0 || j >= 0 || carry > 0) {
        int sum = carry;
        if (i >= 0) {
            sum += num1[i];
            i--;
        }
        if (j >= 0) {
            sum += num2[j];
            j--;
        }
        result.insert(result.begin(), sum % 10);
        carry = sum / 10;
    }
    
    return result;
}

// 计算斐波那契数列的第n个数字（高精度）
std::vector<int> fibonacci(int n) {
    std::vector<int> fibPrev{0};
    std::vector<int> fibCurr{1};
    
    for (int i = 2; i <= n; i++) {
        std::vector<int> fibNext = add(fibPrev, fibCurr);
        fibPrev = fibCurr;
        fibCurr = fibNext;
    }
    
    return fibCurr;
}

int main() {
    int n = 100;  // 计算斐波那契数列的第100个数字
    std::vector<int> result = fibonacci(n);
    
    std::cout << "Fibonacci number at position " << n << ": ";
    for (int digit : result) {
        std::cout << digit;
    }
    std::cout << std::endl;
    
    return 0;
}

在上述示例中，我们定义了一个 `add` 函数来实现高精度的加法。然后，我们使用 `fibonacci` 函数来计算斐波那契数列的第n个数字。通过使用高精度的加法来计算每个数字，我们可以避免溢出或精度丢失。

请注意，随着n的增加，计算斐波那契数列的高精度解决方案会变得更加耗时和占用内存。因此，在实际应用中，需要根据具体需求权衡使用高精度算法的必要性和性能要求。