c++ fib函数

### 使用C++实现斐波那契函数 #### 方法一：递归方法 递归是一种直观的方式用于计算斐波那契数列中的某一项。这种方法基于定义直接翻译成代码，简单易懂。 ```cpp int fib_recursive(int n) { if (n == 1 || n == 2) { // 基础情况 return 1; } return fib_recursive(n - 1) + fib_recursive(n - 2); // 递归调用 } ``` 此方法的时间复杂度较高 \(O(2^n)\)，因为它会重复计算许多子问题[^3]。 --- #### 方法二：动态规划（自底向上） 为了提高效率，可以采用动态规划的思想来存储中间结果，从而减少冗余计算。 ```cpp int fib_dp(int n) { if (n == 1 || n == 2) { return 1; } int dp[n + 1]; dp[1] = 1; dp[2] = 1; for (int i = 3; i <= n; ++i) { dp[i] = dp[i - 1] + dp[i - 2]; // 动态转移方程 } return dp[n]; } ``` 该方法的时间复杂度为 \(O(n)\)，空间复杂度也为 \(O(n)\)[^4]。 --- #### 方法三：优化的空间复杂度版本 如果只需要返回第 \(n\) 项的结果，则可以通过只保存最近的两个状态进一步降低空间复杂度至 \(O(1)\)。 ```cpp int fib_optimized(int n) { if (n == 1 || n == 2) { return 1; } int prev1 = 1, prev2 = 1, current; for (int i = 3; i <= n; ++i) { current = prev1 + prev2; // 当前值等于前两者的和 prev2 = prev1; // 更新第二个前驱 prev1 = current; // 更新第一个前驱 } return current; } ``` 这种实现方式既高效又简洁[^4]。 --- #### 完整程序示例 下面是一个完整的 C++ 程序，允许用户输入一个正整数并输出对应的斐波那契数值： ```cpp #include <iostream> using namespace std; // 函数声明 int fib_optimized(int n); int main() { int n; cout << "请输入要查询的斐波那契序列位置: "; cin >> n; if (n <= 0) { cout << "请输入有效的正整数!" << endl; return 1; } cout << "斐波那契数列为：" << fib_optimized(n) << endl; return 0; } // 实现优化后的斐波那契函数 int fib_optimized(int n) { if (n == 1 || n == 2) { return 1; } int prev1 = 1, prev2 = 1, current; for (int i = 3; i <= n; ++i) { current = prev1 + prev2; prev2 = prev1; prev1 = current; } return current; } ``` 上述代码实现了高效的斐波那契数列求解功能，并具有良好的用户体验[^1]。 ---