中级 · 数列

斐波那契数

输出第 N 个斐波那契数:F(0)=0, F(1)=1, F(n)=F(n−1)+F(n−2)。练习场示例里见过的数列 — 这回是正式版,带着边界情况和性能讨论。

一句话答案用两个滚动变量走 N 步算出 F(N) —— F(0) = 0、F(1) = 1，而朴素递归会把同样的值重复计算指数次。

题目

输入: 一个整数 N(0 ≤ N ≤ 30)。

输出: F(N)。

样例:

输入输出
00
1055

你的解答

main.cpp — 你的解答
「运行我的输入」用的自定义输入

判题在浏览器本地运行。死循环会在 3 秒后被自动中断 —— 但还是确保每个循环都有出口。代码随打随存。

卡住了？提示

提示 1 — 带着一对走,别带整个数列

你从不需要更早的斐波那契数 — 只要最后两个。维护 a = F(i−1)、b = F(i);每步算 t = a + b 然后滑动窗口:a = b; b = t;。走 N 步后,a 就是 F(N)。

提示 2 — 两个基例

滑动对从 a = 0, b = 1 出发:循环跑零圈时 a = 0（N=0 的答案）,一圈后 a = 1（N=1 的答案）。循环免费处理了两个基例 — 和阶乘一样,结构对了,边界就消失了。

题解（先自己试试！） 
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a = 0, b = 1;
    for (int i = 0; i < n; i++) {
        int t = a + b;
        a = b;
        b = t;
    }
    cout << a << endl;
    return 0;
}

面试追问:递归版(fib(n) = fib(n−1) + fib(n−2))优雅但会把同样的值重算指数次 — O(2ⁿ) 对这里的 O(N)。用记忆化修好它,就是你的第一口动态规划。另外:F(47) 会溢出 int(见数据类型,英文),所以本题止步 30。

深度解析

为什么这样做对

两个变量就能扛住整条数列。存数组浪费内存，朴素递归浪费时间。这个「只留前两项」的技巧才是可复用的东西。

代价

迭代：O(n) 时间、O(1) 空间。朴素递归：O(2^n)——fib(40) 大约一秒，fib(50) 大约一天。

常见错法

  • 直接写 fib(n-1) + fib(n-2) 就是指数级。这是「为什么不要这么写」的标准反面教材。
  • F(90) 超过 64 位有符号整数。先搞清楚你的类型在哪停，再谈输出。

下一步

接下来是位级思维：二进制表示。

记住这两句

  • 两个变量就能推完整条数列。
  • 朴素 fib 递归是 O(2^n)——经典陷阱。
🐞 这段是错的 —— 点开,亲手让它挂一次

多跑了一轮，整体错开一项

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a = 0, b = 1;
    for (int i = 0; i <= n; i++) {
        int t = a + b;
        a = b;
        b = t;
    }
    cout << a << endl;
    return 0;
}