C++怎么实现一个斐波那契数列的多种解法_C++递归、迭代与动态规划-C++-PHP中文网

C++怎么实现一个斐波那契数列的多种解法_C++递归、迭代与动态规划

尼克

发布： 2025-11-23 19:46:52

原创

634人浏览过

0。斐波那契数列可通过递归、迭代与动态规划实现，递归法直观但时间复杂度达O(2^n)，存在大量重复计算；迭代法从下往上计算，仅用两个变量保存前两项，时间复杂度O(n)，空间复杂度O(1)，效率更高。

c++怎么实现一个斐波那契数列的多种解法_c++递归、迭代与动态规划

斐波那契数列是经典的数学问题，定义为：F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)（n ≥ 2）。在C++中，可以通过多种方式实现，每种方法在时间与空间效率上有明显差异。下面介绍三种常见解法：递归、迭代与动态规划。

C++递归实现（简单但低效）

最直观的方法是直接按照定义写递归函数：

#include <iostream>
using namespace std;
<p>int fib_recursive(int n) {
if (n <= 1) return n;
return fib_recursive(n - 1) + fib_recursive(n - 2);
}</p><p>int main() {
cout << fib_recursive(10); // 输出 55
return 0;
}</p>

登录后复制

这种方法代码简洁，但存在大量重复计算。例如计算fib(5)时，fib(3)会被调用多次。时间复杂度为O(2^n)，不适用于较大的n值。

迭代法（高效且节省空间）

通过从下往上计算，避免重复，使用两个变量保存前两项的值：

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

int fib_iterative(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; ++i) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

登录后复制

这种方法时间复杂度为O(n)，空间复杂度为O(1)，适合处理较大数值，是实际应用中的首选。

动态规划（记忆化递归或数组存储）

动态规划可以以两种形式实现：自顶向下（带备忘录的递归）和自底向上（数组填充）。

必应图像创建器

微软必应出品的AI绘图工具

593

查看详情

1. 记忆化递归：

#include <vector>
vector<int> memo(1000, -1); // 假设n不超过999
<p>int fib_memo(int n) {
if (n <= 1) return n;
if (memo[n] != -1) return memo[n];
memo[n] = fib_memo(n - 1) + fib_memo(n - 2);
return memo[n];
}</p>

登录后复制

通过缓存已计算结果，避免重复调用，时间复杂度降为O(n)，空间复杂度为O(n)。

2. 自底向上的DP数组：

int fib_dp(int n) {
    if (n <= 1) return n;
    vector<int> dp(n + 1);
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

登录后复制

这种方式逻辑清晰，适合理解动态规划思想，但空间占用比迭代法高。

基本上就这些。对于小规模计算，递归便于理解；追求效率时，推荐使用迭代法；学习算法思想时，动态规划帮助建立优化思维。不复杂但容易忽略的是，递归虽美，性能代价大。

以上就是C++怎么实现一个斐波那契数列的多种解法_C++递归、迭代与动态规划的详细内容，更多请关注php中文网其它相关文章！