快速生成斐波那契C++语言

### 高效 C++ 斐波那契数列实现方法 #### 动态规划法 动态规划是一种通过存储子问题的结果来减少重复计算的技术。这种方法可以显著降低时间复杂度，使其达到 \(O(n)\)，空间复杂度也可以优化到 \(O(1)\)[^1]。 以下是基于动态规划的高效实现代码： ```cpp #include <iostream> using namespace std; long long fibonacci(int n) { if (n <= 1) return n; long long prev = 0, curr = 1; for (int i = 2; i <= n; ++i) { long long next = prev + curr; prev = curr; curr = next; } return curr; } int main() { int n; cout << "请输入要计算的斐波那契数："; cin >> n; cout << "第" << n << "个斐波那契数是：" << fibonacci(n) << endl; return 0; } ``` 此代码利用两个变量 `prev` 和 `curr` 来保存最近两项的值，在每次迭代中更新它们并计算下一项[^3]。 #### 矩阵快速幂法 矩阵快速幂是一种更高级的方法，能够进一步提升效率至 \(O(\log{n})\) 的时间复杂度。其核心思想在于使用矩阵乘法规则表达斐波那契关系，并结合二分求幂技术加速运算。 下面是采用矩阵快速幂算法的 C++ 实现： ```cpp #include <iostream> #include <vector> using namespace std; // 定义二维向量作为矩阵 typedef vector<vector<long long>> Matrix; Matrix multiply(const Matrix& a, const Matrix& b) { Matrix result(a.size(), vector<long long>(b[0].size())); for (size_t i = 0; i < a.size(); ++i) { for (size_t j = 0; j < b[0].size(); ++j) { for (size_t k = 0; k < b.size(); ++k) { result[i][j] += a[i][k] * b[k][j]; } } } return result; } Matrix matrixPower(Matrix base, int exp) { Matrix result(base.size(), vector<long long>(base.size())); for (size_t i = 0; i < result.size(); ++i) result[i][i] = 1; // 初始化单位矩阵 while (exp > 0) { if (exp % 2 == 1) result = multiply(result, base); base = multiply(base, base); exp /= 2; } return result; } long long fibonacci(int n) { if (n <= 1) return n; Matrix F = {{1, 1}, {1, 0}}; F = matrixPower(F, n - 1); return F[0][0]; } int main() { int n; cout << "请输入要计算的斐波那契数："; cin >> n; cout << "第" << n << "个斐波那契数是：" << fibonacci(n) << endl; return 0; } ``` 上述代码定义了一个通用函数用于执行矩阵相乘操作，并实现了指数次方的功能以支持快速幂运算。 --- ### 性能对比分析 | 方法 | 时间复杂度 | 空间复杂度 | |----------------|------------------|-----------------| | **递归** | \(O(2^n)\) | \(O(n)\) | | **循环/动态规化** | \(O(n)\) | \(O(1)\) 或 \(O(n)\) | | **矩阵快速幂** | \(O(\log{n})\) | \(O(1)\) | 可以看出，尽管递归方法简单易懂，但由于存在大量冗余调用，性能较差；而动态规划和矩阵快速幂则是更为高效的解决方案[^2]。