c++怎么实现一个斐波那契数列_c++斐波那契数列实现方法

递归法时间复杂度高，仅适合理解；推荐使用迭代法，时间复杂度O(n)、空间O(1)；动态规划通过记忆化避免重复计算，适合多次查询场景。

实现斐波那契数列在C++中有多种方式，常见的有递归、循环（迭代）和动态规划。每种方法各有特点，适用于不同场景。

1. 递归实现（简单但效率低）

代码如下：

#include <iostream><br>using namespace std;<br><br>int fib(int n) {<br>    if (n <= 1) return n;<br>    return fib(n - 1) + fib(n - 2);<br>}<br><br>int main() {<br>    int n = 10;<br>    cout << "第 " << n << " 项是：" << fib(n) << endl;<br>    return 0;<br>}

2. 迭代实现（推荐，效率高）

使用两个变量保存前两项的值，逐项推进：

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

#include <iostream><br>using namespace std;<br><br>int fib(int n) {<br>    if (n <= 1) return n;<br>    int a = 0, b = 1, c;<br>    for (int i = 2; i <= n; ++i) {<br>        c = a + b;<br>        a = b;<br>        b = c;<br>    }<br>    return b;<br>}<br><br>int main() {<br>    int n = 10;<br>    cout << "第 " << n << " 项是：" << fib(n) << endl;<br>    return 0;<br>}

Cutout.Pro

AI驱动的视觉设计平台

下载

3. 动态规划（记忆化递归）

用数组保存已计算的结果：

#include <iostream><br>using namespace std;<br><br>int fibHelper(int n, int* memo) {<br>    if (n <= 1) return n;<br>    if (memo[n] != -1) return memo[n];<br>    memo[n] = fibHelper(n - 1, memo) + fibHelper(n - 2, memo);<br>    return memo[n];<br>}<br><br>int fib(int n) {<br>    int* memo = new int[n + 1];<br>    fill(memo, memo + n + 1, -1); // 初始化为-1<br>    int result = fibHelper(n, memo);<br>    delete[] memo;<br>    return result;<br>}<br><br>int main() {<br>    int n = 10;<br>    cout << "第 " << n << " 项是：" << fib(n) << endl;<br>    return 0;<br>}

总结： 对于实际应用，推荐使用迭代法，它效率高且不易栈溢出。递归仅用于教学演示。若需多次查询，可考虑预打表或记忆化优化。

基本上就这些，不复杂但容易忽略性能差异。