帮我用C++写一段计算斐波那契数的代码
- User
帮我用C++写一段计算斐波那契数的代码
Assistant
好的,我将为您提供几种计算斐波那契数的C++实现方法:
- 递归实现(简单但效率低):
int fibonacci(int n) { if (n <= 1) return n; return fibonacci(n-1) + fibonacci(n-2); }- 动态规划实现(推荐):
int fibonacci(int n) { if (n <= 1) return n; int prev = 0, curr = 1; for (int i = 2; i <= n; i++) { int next = prev + curr; prev = curr; curr = next; } return curr; }- 完整的示例程序:
#include <iostream> using namespace std; int fibonacci(int n) { if (n <= 1) return n; int prev = 0, curr = 1; for (int i = 2; i <= n; i++) { int next = prev + curr; prev = curr; curr = next; } return curr; } int main() { int n; cout << "请输入要计算的斐波那契数的位置:"; cin >> n; cout << "第 " << n << " 个斐波那契数是:" << fibonacci(n) << endl; return 0; }推荐使用第2种动态规划的方法,因为:
- 时间复杂度为O(n)
- 空间复杂度为O(1)
- 避免了递归方法的重复计算问题
- 计算效率高
如果您需要处理更大的斐波那契数,可能需要使用长整型或大数处理。
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.