菲波那契数列

题目描述

菲波那契数列的第 1、2 个数都为 1，之后每个数都等于前面 2 个数之和。输入第 1 行是测试数据的组数 $n$ ，后面 $n$ 行每组一个正整数 $a$ （ $1\leqslant a\leqslant 20$ ）；输出 $n$ 行，每行输出菲波那契数列中第 $a$ 个数的大小。

样例输入 4 5 2 19 1，样例输出 5 1 4181 1（输入输出均为每行一个数）。

思路

按定义从 $F(1)=F(2)=1$ 自底向上递推出 $F(3),\dots,F(20)$ 预处理进数组，之后每个询问 $a$ 直接输出 $F(a)$ 即可。 $F(20)=6765$ 很小，用 ll 存也不存在溢出问题。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25#!/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 23:16
# update_at: 2026-09-29 23:28

import sys
from functools import cache


@cache
def fib(a: int) -> int:
    """返回斐波那契数列第 a 项：F(1)=F(2)=1，F(a)=F(a-1)+F(a-2)。"""
    return 1 if a <= 2 else fib(a - 1) + fib(a - 2)  # 递归定义，@cache 把算过的 a 记下来


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)  # 题面的测试数据组数
    print('\n'.join(str(fib(next(data))) for _ in range(n)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33/**
 * 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 05:26
 * update_at: 2026-10-05 05:26
 */
#include <cstdio>

typedef long long ll;

ll fib[25]; // fib[i] 表示菲波那契数列第 i 项，下标从 1 开始和题面对应

// 自底向上递推预处理：F(1)=F(2)=1，F(a)=F(a-1)+F(a-2)
void init_fib() {
    fib[1] = 1;
    fib[2] = 1;
    for (int i = 3; i <= 20; ++i)
        fib[i] = fib[i - 1] + fib[i - 2];
}

int main() {
    init_fib(); // a<=20，预处理一遍后面每个询问 O(1) 回答

    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        int a;
        scanf("%d", &a);
        printf("%lld\n", fib[a]);
    }
    return 0;
}

目录

题目描述

思路

参考代码