11907.斐波那契数列

题目分析

斐波那契数列：F(1)=0, F(2)=1, F(n)=F(n-1)+F(n-2)

解题思路

使用递推，从第3项开始逐步计算到第n项，用三个变量滚动更新。

代码实现

cpp
复制
1#include <iostream>
2using namespace std;
3
4int main() {
5    int n;
6    cin >> n;
7    
8    long long a = 0, b = 1, c;
9    
10    if (n == 1) { cout << 0 << endl; return 0; }
11    if (n == 2) { cout << 1 << endl; return 0; }
12    
13    for (int i = 3; i <= n; i++) {
14        c = a + b;
15        a = b;
16        b = c;
17    }
18    
19    cout << c << endl;
20    return 0;
21}

核心要点

• 递推：O(n) 时间，O(1) 空间
• 注意：n=1 输出0，n=2 输出1
• 数据类型：使用 long long 防止溢出
• 不推荐递归：效率低（指数级）