P4363 斐波那契数列（入门）

解题思路

斐波那契数列很有名，它来自于"兔子生小兔子"的故事，不过我们只记规则：数列的第一项和第二项都是 1，从第三项开始，每一项都等于它前面两项的和。所以数列是 1、1、2、3、5、8、13……题目要我们输出前 k 个数，k 最大是 46。

怎么输出呢？不需要开一个大数组把所有数都存下来，只要两个变量 a 和 b 就够了：a 存"当前要输出的数"，b 存"下一个数"。像传接力棒一样，每次输出 a，然后算出下一项 t = a + b，再把 b 交给 a、把 t 交给 b，两个变量就一起往前走一格。

举个例子，k = 5：先输出 1，算出 t = 1 + 1 = 2；下一轮输出 b = 1，算出 t = 1 + 2 = 3；接着输出 2、3、5……最后得到 1 1 2 3 5，和样例一致。

边界情况：k 最小是 3，这时只输出 1 1 2；k 最大是 46，第 46 项是 1836311903，已经非常接近 21 亿，虽然 int 刚好装得下，但为了保险我们用 long long 来存。输出格式上，数之间用空格隔开，第一个数前面不能有空格，用 if (i > 1) cout << " " 来控制。

参考代码

// 程序用途：输入k，输出斐波那契数列的前k个数
#include <iostream>
using namespace std;

int main() {
    int k;
    cin >> k;
    long long a = 1, b = 1;   // a存当前项，b存下一项（前两项初始都是1）
    for (int i = 1; i <= k; i++) {
        if (i > 1) cout << " ";       // 从第2个数起，前面加一个空格
        cout << a;
        long long t = a + b;          // 下一项 = 前两项之和
        a = b;                        // 两个变量像接力棒一样往前传
        b = t;
    }
    cout << endl;
    return 0;
}

复杂度分析

循环从第 1 项走到第 k 项，一共执行 k 次，k 最大只有 46，所以时间复杂度是 O(k)；空间上只用了 a、b、t 几个变量，额外空间复杂度是 O(1)。