菲波那契递推的水表题：两个变量滚动递推 k-2 次即得第 k 项，时间 O(k)、空间 O(1)。
OJ: roj
题目 ID: 1071
难度:入门
标签:递推循环python
创建: 2026-09-29 17:20
更新: 2026-10-05 00:10
题目描述
菲波那契数列是指这样的数列：数列的第一个和第二个数都为 1，接下来每个数都等于前面 2 个数之和。给出一个正整数 k，要求菲波那契数列中第 k 个数是多少。
输入一行，包含一个正整数 k（1 ≤ k ≤ 46）。
输出一行，包含一个正整数，表示菲波那契数列中第 k 个数的大小。
样例：k = 19 时输出 4181。
思路
直接按定义递推：用两个变量 a、b 保存最近两项，从第 3 项起循环做 t = a + b; a = b; b = t，共推 k-2 次即可。k = 1、2 时直接输出 1；最大项 F(46) = 1836311903 在 int 范围内，但按习惯用 ll 存数据更稳。
参考代码
Python 版：
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-29 17:23
# update_at: 2026-09-29 17:23
# 递推：F(0)=0、F(1)=1，F(i)=F(i-1)+F(i-2)。滚动窗口 (a, b) 表示 (F(i-1), F(i))，
# 一次加法和一次元组重绑定即推进一位，含 F(46)=1836311903 在内全在 Python 的 int 里精确。
from functools import reduce # 用 (a, b) -> (b, a + b) 表示一步递推：F(i)=a+b 就是新元组的第二项
import sys
def fib_step(state: tuple[int, int], _step: int) -> tuple[int, int]:
"""一次递推：当前窗口 (F(i-1), F(i)) 推进到 (F(i), F(i+1))；步数下标不参与计算。"""
a, b = state
return b, a + b
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
k = next(data) # 题面 1 <= k <= 46
# 种子 (F(0), F(1)) = (0, 1)，推进 k 步后窗口为 (F(k), F(k+1))，首项就是答案。
answer, _ = reduce(fib_step, range(k), (0, 1))
print(answer)
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-05 00:11
* update_at: 2026-10-05 00:11
*/
#include <cstdio>
typedef long long ll;
ll k; // 要求的项数，1 <= k <= 46
ll a, b; // 滚动窗口：递推中依次保存最近两项 F(i-2)、F(i-1)
int main() {
scanf("%lld", &k);
// 前 1、2 项都为 1，无需递推
if (k <= 2) {
printf("1\n");
return 0;
}
a = 1; // F(1)
b = 1; // F(2)
// 从第 3 项推到第 k 项：每次 t = F(i-1) + F(i-2)，窗口右移一位
for (ll i = 3; i <= k; ++i) {
ll t = a + b;
a = b;
b = t;
}
printf("%lld\n", b);
return 0;
}