c++怎么实现一个斐波那契数列_c++斐波那契数列实现方法-C++-PHP中文网

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

尼克

发布： 2025-10-06 14:32:02

原创

638人浏览过

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

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

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

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

适合理解逻辑，但时间复杂度为 O(2^n)，存在大量重复计算。

代码如下：

<pre class="brush:php;toolbar:false;">#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. 迭代实现（推荐，效率高）

时间复杂度 O(n)，空间复杂度 O(1)，适合大数值计算。

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

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

<pre class="brush:php;toolbar:false;">#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>}

登录后复制

腾讯智影-AI数字人

基于AI数字人能力，实现7*24小时AI数字人直播带货，低成本实现直播业务快速增增，全天智能在线直播

查看详情

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

结合递归思想与缓存机制，避免重复计算。

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

<pre class="brush:php;toolbar:false;">#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>}

登录后复制

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

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

以上就是c++++怎么实现一个斐波那契数列_c++斐波那契数列实现方法的详细内容，更多请关注php中文网其它相关文章！