【深基4.习4】月落乌啼算钱（斐波那契数列）

解题思路

题给通项是斐波那契数列，使用 F0=0、F1=1 和 Fn=Fn-1+Fn-2 递推。两个变量滚动保存相邻项。

正确性说明

初始两个变量为 F0 与 F1，每次变为下一对相邻项，循环 n 次后第一个变量正是 Fn。

易错点

n 可为 0；F48 超出 32 位有符号整数，用 long long；结果按实数保留两位。

复杂度

时间 O(n)，空间 O(1)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    long long a = 0, b = 1;
    for (int i = 0; i < n; i++) {
        long long c = a + b;
        a = b;
        b = c;
    }
    cout << fixed << setprecision(2) << double(a) << "\n";
    return 0;
}