C++ 求解斐波那契数列：迭代法详解与实现

好的，这是一个非常经典的斐波那契数列问题。虽然题目描述中 `a` 的范围是 1 到 30，但我们依然可以采用高效的解法。下面我会给出 **C++ 的完整实现**，并分析几种常见解法及其优劣。 --- ## 🧠 解题思路 斐波那契数列定义： - `f(1) = 1` - `f(2) = 1` - `f(n) = f(n-1) + f(n-2)` （n ≥ 3） 由于 `a ≤ 30`，我们可以： 1. **直接递归**（简单但效率低，指数级） 2. **迭代**（推荐，O(n)） 3. **记忆化递归**（O(n)） 4. **矩阵快速幂**（O(log n)，但本题不需要，因为范围小） 这里我会给出 **迭代法**，这是最清晰且高效的选择。 --- ## 💻 C++ 代码实现（迭代法） ```cpp #include <iostream> using namespace std; int main() { int n; cin >> n; // 读取测试数据组数 while (n--) { int a; cin >> a; // 处理边界情况 if (a == 1 || a == 2) { cout << 1 << endl; continue; } // 迭代计算 long long prev2 = 1; // f(1) long long prev1 = 1; // f(2) long long current = 0; for (int i = 3; i <= a; ++i) { current = prev1 + prev2; prev2 = prev1; prev1 = current; } cout << current << endl; } return 0; } ``` --- ## 📘 代码解读 - `cin >> n` 读取测试用例数量。 - 每轮循环中读取 `a`。 - 如果 `a == 1` 或 `a == 2`，直接输出 `1`（因为前两项都是 1）。 - 否则用三个变量 `prev2`、`prev1`、`current` 滚动计算： - `prev2` 存储 `f(i-2)` - `prev1` 存储 `f(i-1)` - `current` 存储 `f(i)` - 循环结束后输出 `current`。 **复杂度分析**： - 时间复杂度：O(n) 次运算，其中 n 为测试组数，每次计算最多 30 项，非常快。 - 空间复杂度：O(1)，只用了几个变量。 --- ## ⚖️ 常见解法比较 | 方法 | 时间复杂度 | 空间复杂度 | 适用场景 | |------|------------|------------|----------| | 朴素递归 | O(2^a) | O(a) 调用栈 | a 很小（≤20） | | 迭代法 | O(a) | O(1) | 本题最优解 | | 记忆化递归 | O(a) | O(a) | 需要多次查询时 | | 矩阵快速幂 | O(log a) | O(1) | a 非常大（≥10^18） | > 对于本题目（a ≤ 30），**迭代法** 最简洁高效，也最容易理解。 --- ## 🛠️ 开发建议 1. **注意数据溢出**：虽然 a ≤ 30，f(30) = 832040，int 足够，但使用 `long long` 更安全，便于扩展。 2. **输入处理**：使用 `while(n--)` 比 `for(int i=0;i<n;i++)` 更简洁，但注意不要影响后续逻辑。 3. **可读性优先**：将斐波那契计算封装成函数更利于复用，例如 `long long fib(int n)`。 4. **边界条件测试**：务必测试 `a=1`、`a=2`、`a=30` 等极端值。 --- ## 📚 扩展学习 - 如果 `a` 可以到 10^18，就需要用 **矩阵快速幂** 或 **通项公式**（含浮点，有精度问题）。 - 如果想快速求解多个不同的 `a`，可以 **预处理** 前 30 项存入数组，查询时 O(1)。 --- ######[AI写代码神器 | 981点数解答 | 2026-07-31 19:49:36]