c++如何计算斐波那契数列_c++斐波那契算法实现讲解-C++-PHP中文网

c++如何计算斐波那契数列_c++斐波那契算法实现讲解

冰火之心

发布： 2025-10-21 20:54:01

原创

330人浏览过

斐波那契数列在C++中可通过递归、迭代、动态规划和矩阵快速幂实现；2. 递归简洁但低效，时间复杂度O(2^n)；3. 迭代法时间复杂度O(n)，空间复杂度O(1)，推荐日常使用；4. 动态规划通过记忆化优化递归，时间复杂度O(n)，需额外空间；5. 矩阵快速幂适用于大数值，时间复杂度O(log n)，适合高性能场景。

c++如何计算斐波那契数列_c++斐波那契算法实现讲解

计算斐波那契数列在C++中有多种实现方式，每种方法在效率和可读性上各有特点。斐波那契数列定义为：第0项是0，第1项是1，从第2项开始，每一项都等于前两项之和（即 F(n) = F(n-1) + F(n-2)）。下面介绍几种常见的C++实现方法。

递归实现（简单但低效）

最直观的方法是使用递归：

#include <iostream>
using namespace std;
<p>int fib(int n) {
if (n <= 1)
return n;
return fib(n - 1) + fib(n - 2);
}</p><p>int main() {
int n = 10;
cout << "F(" << n << ") = " << fib(n) << endl;
return 0;
}</p>

登录后复制

这种方法代码简洁，但存在大量重复计算，时间复杂度为O(2^n)，当n较大时性能急剧下降，不推荐用于实际应用。

迭代实现（推荐）

使用循环避免重复计算，效率更高：

立即学习“C++免费学习笔记（深入）”；

#include <iostream>
using namespace std;
<p>int fib(int n) {
if (n <= 1)
return n;</p><pre class='brush:php;toolbar:false;'>int a = 0, b = 1, c;
for (int i = 2; i <= n; ++i) {
    c = a + b;
    a = b;
    b = c;
}
return b;

登录后复制

}

int main() { int n = 10; cout << "F(" << n << ") = " << fib(n) << endl; return 0; }

该方法时间复杂度为O(n)，空间复杂度为O(1)，适合大多数场景，是实际开发中的首选方案。

算家云

高效、便捷的人工智能算力服务平台

查看详情

动态规划（记忆化递归）

如果仍想使用递归结构，可通过记忆化优化性能：

#include <iostream>
#include <vector>
using namespace std;
<p>int fib_helper(int n, vector<int>& memo) {
if (n <= 1)
return n;
if (memo[n] != -1)
return memo[n];
memo[n] = fib_helper(n - 1, memo) + fib_helper(n - 2, memo);
return memo[n];
}</p><p>int fib(int n) {
vector<int> memo(n + 1, -1);
return fib_helper(n, memo);
}</p><p>int main() {
int n = 10;
cout << "F(" << n << ") = " << fib(n) << endl;
return 0;
}</p>

登录后复制

通过保存已计算的结果，避免重复调用，时间复杂度降为O(n)，但需要额外的内存空间。