C++ 高精度斐波那契数列教程（0基础通俗易懂）

📚 什么是高精度斐波那契数列？

斐波那契数列是这样一个数列：

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)   （n ≥ 2）

它的前几项是：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

问题来了：
当 n 很大时（比如 n = 1000），斐波那契数的值会远远超过 long long 的范围，这时候就不能用普通整型来保存了。

所以我们就要用高精度算法，手动模拟加法运算，从而计算出非常大的斐波那契数。

---

🧠 基本思路

我们使用 字符串或 vector 来表示大数，然后实现一个高精度加法函数，用于计算斐波那契数列中的每一项。

关键点：

• 使用 vector<int> 存储每一位数字（便于进位操作）
• 实现高精度加法函数 add(const vector<int>& a, const vector<int>& b)
• 使用循环依次计算每一项：f[n] = f[n-1] + f[n-2]

---

💡 数据结构选择：vector

我们将每个数字按个十百千万顺序存储在一个 vector<int> 中。例如：

数字 123 表示为 {3, 2, 1}

这样从前往后就可以一位一位相加，方便处理进位。

---

💻 示例代码（完整可运行）

#include <iostream>
#include <vector>
using namespace std;

// 打印结果：把 vector<int> 反转输出
void print(const vector<int>& v) {
    for (int i = v.size() - 1; i >= 0; i--)
        cout << v[i];
    cout << endl;
}

// 高精度加法：a + b
vector<int> add(const vector<int>& a, const vector<int>& b) {
    vector<int> res;
    int carry = 0;

    // 同时遍历两个数组
    int i = 0;
    while (i < a.size() || i < b.size()) {
        int sum = carry;
        if (i < a.size()) sum += a[i];
        if (i < b.size()) sum += b[i];
        res.push_back(sum % 10);
        carry = sum / 10;
        i++;
    }

    // 处理最后的进位
    if (carry > 0)
        res.push_back(carry);

    return res;
}

// 计算第 n 项斐波那契数
vector<int> fib(int n) {
    if (n == 0) return {0};
    if (n == 1) return {1};

    vector<int> a = {0}; // F(0)
    vector<int> b = {1}; // F(1)

    for (int i = 2; i <= n; ++i) {
        vector<int> c = add(a, b); // c = a + b
        a = b;                     // 更新 a
        b = c;                     // 更新 b
    }

    return b;
}

int main() {
    int n;
    cout << "请输入要计算的斐波那契数的序号 n：";
    cin >> n;

    if (n < 0) {
        cout << "负数没有斐波那契数！" << endl;
        return 0;
    }

    vector<int> result = fib(n);

    cout << "F(" << n << ") = ";
    print(result);

    return 0;
}

---

📖 示例运行

输入：

请输入要计算的斐波那契数的序号 n：50

输出：

F(50) = 12586269025

再试一个更大的：

输入：

请输入要计算的斐波那契数的序号 n：100

输出：

F(100) = 354224848179261915075

---

✅ 总结知识点

内容	说明
使用 vector	存储每一位数字，便于进位操作
高精度加法	自定义实现两个大数相加
斐波那契逻辑	从 F(0) 和 F(1) 开始，循环累加到 F(n)
输出方式	逆序打印 vector 中的每一位

---

🧪 练习建议

你可以试着扩展以下功能：

• 把结果写入文件保存（如 fibonacci.txt）
• 统计执行时间，看看不同 n 对性能的影响
• 实现一个函数，把 vector<int> 转成字符串返回
• 支持输出多个斐波那契数（比如前 100 项）

---

📌 进阶学习建议

如果你已经掌握高精度斐波那契数列，可以挑战以下内容：

• 实现高精度矩阵快速幂加速斐波那契数列计算（O(log n) 算法）
• 实现高精度卢卡斯数列（Lucas Sequence）
• 尝试使用类封装你的高精度库（面向对象编程）
• 探索模意义下的斐波那契数列（Fibonacci Modulo）

---

📚 附录：常见斐波那契数长度参考

n	F(n) 的位数
10	3 位
50	11 位
100	21 位
500	104 位
1000	209 位
10000	2089 位

---

如果你希望我继续扩展以下内容，请告诉我：

• 如何优化性能？
• 如何支持浮点数版本的斐波那契数列？
• 如何把结果保存为文件？
• 如何用矩阵快速幂加速？

😊