斐波那契数列 c++

以下是三种不同的方法来实现 C++ 中的斐波那契数列： ### 方法一：递归方式 这种方法通过函数调用自身的方式来计算斐波那契数列中的某一项。虽然简单易懂，但对于较大的 `n` 值效率较低。 ```cpp #include <iostream> using namespace std; int fib(int n) { if (n <= 1) { return n; } return fib(n-1) + fib(n-2); } int main() { int n; cout << "请输入需要计算的斐波那契数列项数: "; cin >> n; cout << "第 " << n << " 项斐波那契数是: " << fib(n) << endl; return 0; } ``` 此代码展示了如何利用递归来获取指定位置上的斐波那契数值[^1]。 --- ### 方法二：迭代方式 相比递归，迭代的方法更加高效，因为它不需要重复计算相同的子问题。 ```cpp #include <iostream> using namespace std; long long fibonacciIterative(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 << " 项斐波那契数是: " << fibonacciIterative(n) << endl; return 0; } ``` 该版本采用循环结构逐步构建序列，从而显著提高了性能[^3]。 --- ### 方法三：预计算存储法 如果需要频繁查询不同索引处的斐波那契值，则可以预先计算并保存这些值到数组中以便快速访问。 ```cpp #include <bits/stdc++.h> #define MAXN 1000 using namespace std; int fibn[MAXN]; void precomputeFibonacci() { fibn[1] = fibn[2] = 1; for (int i = 3; i < MAXN; ++i) { fibn[i] = fibn[i - 1] + fibn[i - 2]; } } int main() { precomputeFibonacci(); int n; cout << "请输入需要查询的斐波那契数列项数: "; cin >> n; if (n >= 1 && n < MAXN) { cout << "第 " << n << " 项斐波那契数是: " << fibn[n] << endl; } else { cout << "超出范围!" << endl; } return 0; } ``` 这段代码先将所有可能的结果存入全局变量 `fibn[]` 数组里，在实际运行过程中只需读取对应下标的值即可得到结果。 --- ### 性能对比分析 上述三种算法各有优劣： - **递归版**易于理解但时间复杂度高 O(2^n)，适合教学演示； - **迭代版**的时间复杂度降为线性的O(n)，空间消耗也较小； - **预处理表查法**适用于多次随机访问的情况，初始开销较大但后续操作极快。 ---