斐波那契数列

题目描述

题面数列为 $0,1,1,2,3,5,8,13,\ldots$ ，即首项为 $0$ 的斐波那契数列。给定正整数 $n$ ，用递归函数求第 $n$ 项。

输入：一个正整数 $n$ 。输出：第 $n$ 项。样例输入 3，输出 1（注意数列首项是 $0$ ，不是 $1$ ）。

思路

按定义 $F(0)=0$ 、 $F(1)=1$ 、 $F(i)=F(i-1)+F(i-2)$ 写递归，并为每个下标加记忆化，使同一项只算一次；题面数列首项是 $0$ ，第 $n$ 项对应 $F(n-1)$ 。

参考代码

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
26
27
28
29
30
31
32
33
34#!/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 21:26
# update_at: 2026-09-29 21:30

import sys
from functools import cache


@cache
def fib_pair(n: int) -> tuple[int, int]:
    """返回 (F(n), F(n+1))，其中 F(0)=0、F(1)=1。

    倍增恒等式：F(2m)=F(m)·(2F(m+1)−F(m))，F(2m+1)=F(m)²+F(m+1)²。
    把下标折半就能一次拿到相邻两项 F(2m)、F(2m+1)，递归深度只有 O(log n)。
    """
    if n < 2:                     # 边界：(F(0),F(1))=(0,1)，(F(1),F(2))=(1,1)——第二项恒为 1
        return n, 1
    lo, hi = fib_pair(n >> 1)     # 下标折半，m = ⌊n/2⌋
    even = lo * (2 * hi - lo)     # F(2m)
    odd = lo * lo + hi * hi       # F(2m+1)
    return (odd, even + odd) if n & 1 else (even, odd)  # 奇数时再向前迈一步


def solve() -> None:
    n = int(sys.stdin.buffer.read())
    # 题面数列 0,1,1,2,3,5,... 是零起编号的斐波那契：第 n 项就是 F(n-1)
    print(fib_pair(n - 1)[0])


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/**
 * 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 03:50
 * update_at: 2026-10-05 03:50
 */
#include <cstdio>

typedef long long ll;

ll n;                 // 输入的项号
ll fib_value[105];    // fib_value[i] = 零起编号斐波那契 F(i)，F(0)=0、F(1)=1
char computed[105];   // computed[i] 标记 F(i) 是否已经算过，只有 0/1，用 char 省内存

// 记忆化递归：返回 F(i)，每个下标只计算一次
ll fib(ll i) {
    if (i < 2) return i;
    if (computed[i]) return fib_value[i];
    fib_value[i] = fib(i - 1) + fib(i - 2);
    computed[i] = 1;
    return fib_value[i];
}

int main() {
    scanf("%lld", &n);

    // 题面数列 0,1,1,2,3,5,... 首项是 0，第 n 项对应零起编号的 F(n-1)
    printf("%lld\n", fib(n - 1));

    return 0;
}

目录

题目描述

思路

参考代码