递推法 | 王老师信息学奥赛课件

模块 01

情景导航

从一个经典的数学问题开始，感受递推的力量。

故事兔子繁殖问题

1202年，意大利数学家斐波那契（Fibonacci）提出了一个有趣的问题：

假设一对刚出生的小兔子，一个月后长大成熟，成熟后每个月都会生一对新的小兔子。问：从一对刚出生的小兔子开始，第 n 个月共有多少对兔子？

🐰 第1月：1 对（刚出生）
🐰🐰 第2月：1 对（长大了，还没生）
🐰🐰 + 👶 第3月：2 对（老兔生了一对新兔）
🐰🐰 + 👶🐰 + 👶 第4月：3 对（老兔又生一对，第3月出生的长大）
🐰🐰 + 🐰🐰 + 👶🐰 + 👶 + 👶 第5月：5 对

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

你发现规律了吗？每一项 = 前两项之和！

F(n) = F(n-1) + F(n-2)

这就是著名的斐波那契数列，也是递推法最经典的例子。我们不需要模拟兔子的繁殖过程，只要找到递推关系，就能快速算出任意月份的兔子数！

💡 为什么 F(n) = F(n-1) + F(n-2)？

第 n 个月的兔子由两部分组成：

① 上个月就有的兔子 → F(n-1) 对（兔子不会死）

② 这个月新出生的兔子 → 只有成熟兔子才能生，而两个月前就存在的兔子现在都已成熟 → F(n-2) 对

所以 F(n) = F(n-1) + F(n-2)，这就是递推关系！

①生活类比：递推无处不在

🪜

爬楼梯

每次走1或2阶，到第n阶 = 从n-1走1步 + 从n-2走2步。

→ f(n) = f(n-1) + f(n-2)

💰

存钱复利

每月利息 = 上月本金 × 利率。本月总额 = 上月 + 利息。

→ f(n) = f(n-1) × (1+r)

🧱

铺地砖

铺到第n格：横着放占1格 + 竖着放占2格。

→ f(n) = f(n-1) + f(n-2)

🎯

击鼓传花

传到第n个人的方案数 = 上一轮所有可能 × 传递规则。

→ 状态递推

②编程定义

递推法（Recurrence）：从已知的初始条件出发，按照某种递推关系，逐步推算出所求结果的方法。即：用前面项的值来计算后面项的值。

核心公式：f(n) = G(f(n-1), f(n-2), ...) — 第 n 项由前面若干项通过某个函数 G 计算得到。

📌 本讲核心知识地图

板块	核心内容	对应大纲
递推三要素	初始值、递推关系、目标项	递推法
斐波那契数列	F(n) = F(n-1) + F(n-2)	经典递推模型
爬楼梯问题	f(n) = f(n-1) + f(n-2)（多种理解方式）	递推应用
汉诺塔	T(n) = 2T(n-1) + 1	递推应用
Catalan数	C(n) = Σ C(i)×C(n-1-i)	递推应用
递推 vs 递归	自底向上 vs 自顶向下	方法对比

③核心口诀

🔑 递推法三步曲

① 找关系：f(n) 和 f(n-1)、f(n-2) 有什么关系？
② 定初值：f(1)=? f(2)=? 基础情况不能错
③ 推到底：从初值开始循环，逐步推出 f(n)

🔑 递推 vs 递归

递推：从小到大，已知推未知，快且不爆栈；
递归：从大到小，未知拆已知，简洁但可能慢；
竞赛首选递推（自底向上），递归用来理解思路！

模块 02

知识探究

深入理解递推三要素，通过四个经典模型掌握递推法的核心技巧。

1递推法的三要素核心

任何一个递推问题都由以下三个要素组成：

要素① 初始值

递推的起点（base case）
如：f(1) = 1, f(2) = 1
初始值错了，后面全错！
通常通过手算小样例确定

要素② 递推关系

f(n) 与前面项的数学关系
如：f(n) = f(n-1) + f(n-2)
这是最难也最关键的部分
需要分析问题的结构

要素③ 目标项

最终要求的是 f(?)
如：求 f(n)、求 f(n) mod M
确定从哪里取答案
有时答案不是直接取 f(n)

🔑 递推法通用模板

// 1. 定义数组
int f[MAX];

// 2. 设定初始值
f[1] = ?, f[2] = ?;

// 3. 递推计算
for(int i = 3; i <= n; i++)
f[i] = f[i-1] + f[i-2]; // 递推关系

// 4. 输出结果
cout << f[n] << endl;

案例经典案例1：斐波那契数列必会

📊 斐波那契数列可视化

F(1)1

F(2)1

F(3)2

F(4)3

F(5)5

F(6)8

F(7)13

F(8)21

F(9)34

F(10)55

F(11)89

F(n) = F(n-1) + F(n-2) | F(1)=1, F(2)=1

三要素	值	说明
初始值	F(1) = 1, F(2) = 1	第一、二月各1对兔子
递推关系	F(n) = F(n-1) + F(n-2)	本月兔子 = 上月 + 新出生
目标项	F(n)	第n个月的兔子对数

C++fibonacci.cpp — 递推实现

#include <iostream>
using namespace std;

int main() {
    int n; cin >> n;

long long f[100];  // 用 long long 防溢出
    f[1] = 1;          // 初始值
    f[2] = 1;

for (int i = 3; i <= n; i++) {
        f[i] = f[i-1] + f[i-2];  // 递推关系
    }

cout << f[n] << endl;  // 输出目标项
    return 0;
}

运行结果

输入：11
输出：89

💡 时间复杂度对比

递推（自底向上）：循环 n 次，每次 O(1) → 总复杂度 O(n)

朴素递归（自顶向下）：每层分裂两个子问题 → 总复杂度 O(2ⁿ) 💥

当 n=40 时：递推 ~0.0001秒，递归 ~10分钟！这就是递推的优势。

案例经典案例2：爬楼梯问题高频

一个楼梯有 n 阶，每次可以走 1 阶或 2 阶。问从底部到顶部共有多少种不同的走法？

🔍 递推关系分析

到达第 n 阶，只有两种方式：

① 从第 n-1 阶走 1 步上来 → 对应 f(n-1) 种走法

② 从第 n-2 阶走 2 步上来 → 对应 f(n-2) 种走法

所以：f(n) = f(n-1) + f(n-2)

初始值：f(1)=1（1阶只有1种走法），f(2)=2（2阶：1+1 或 2，共2种）

n	1	2	3	4	5	6	7	8
f(n)	1	2	3	5	8	13	21	34
递推	初值	初值	1+2	2+3	3+5	5+8	8+13	13+21

C++stairs.cpp

#include <iostream>
using namespace std;

int main() {
    int n; cin >> n;
    long long f[100];
    f[1] = 1;
    f[2] = 2;
    for (int i = 3; i <= n; i++)
        f[i] = f[i-1] + f[i-2];
    cout << f[n] << endl;
    return 0;
}

运行结果

输入：8
输出：34

💡 注意初始值的差异！

爬楼梯：f(1)=1, f(2)=2 → 数列 1, 2, 3, 5, 8, ...

斐波那契：F(1)=1, F(2)=1 → 数列 1, 1, 2, 3, 5, 8, ...

递推关系相同，但初始值不同，结果就不同。初始值一定要手算验证！

案例经典案例3：汉诺塔经典

有三根柱子 A、B、C，A 上有 n 个大小不同的盘子（大的在下，小的在上）。每次移动一个盘子到另一根柱子，大盘不能放在小盘上。问最少需要多少步？

A（源）

B（辅助）

C（目标）

🔍 递推关系分析

要把 n 个盘子从 A 移到 C，最优策略是：

① 先把上面 n-1 个盘子从 A 移到 B（借助 C）→ T(n-1) 步

② 把最底下的大盘子从 A 移到 C → 1 步

③ 把 B 上的 n-1 个盘子移到 C（借助 A）→ T(n-1) 步

所以：T(n) = 2 × T(n-1) + 1

初始值：T(1) = 1（1个盘子只需1步）

n	1	2	3	4	5	6	7	n
T(n)	1	3	7	15	31	63	127	2ⁿ-1
递推	初值	2×1+1	2×3+1	2×7+1	2×15+1	2×31+1	2×63+1	—

C++hanoi.cpp

#include <iostream>
using namespace std;

int main() {
    int n; cin >> n;
    long long T[65];
    T[1] = 1;
    for (int i = 2; i <= n; i++)
        T[i] = 2 * T[i-1] + 1;
    cout << T[n] << endl;
    return 0;
}

运行结果

输入：4
输出：15

🔑 汉诺塔的通项公式

观察：T(1)=1=2¹-1, T(2)=3=2²-1, T(3)=7=2³-1, ...

通项公式：T(n) = 2ⁿ - 1

n=64 时，T(64) = 2⁶⁴-1 ≈ 1.8×10¹⁹，传说僧侣移完64个盘子世界就毁灭了！

案例经典案例4：Catalan 数拓展

n 对括号正确匹配的方案数是多少？例如 n=3 时：((())), (()()), (())(), ()(()), ()()() 共 5 种。

🔍 递推关系分析

考虑最外层的匹配括号 (...)，设内部包含 k 对括号，则外部剩余 n-1-k 对括号。

内部 k 对的匹配方案 = C(k)，外部 n-1-k 对 = C(n-1-k)

k 从 0 到 n-1 取遍，所以：

C(n) = Σ C(k) × C(n-1-k) （k = 0, 1, ..., n-1）

初始值：C(0) = 1（空序列也算一种合法匹配）

n	0	1	2	3	4	5	6	7
C(n)	1	1	2	5	14	42	132	429

C++catalan.cpp

#include <iostream>
using namespace std;

int main() {
    int n; cin >> n;
    long long C[35] = {0};
    C[0] = 1;  // 初始值

for (int i = 1; i <= n; i++) {
        for (int k = 0; k < i; k++) {
            C[i] += C[k] * C[i - 1 - k];  // 递推关系
        }
    }

cout << C[n] << endl;
    return 0;
}

运行结果

输入：5
输出：42

💡 Catalan 数的经典应用

• n 对括号的正确匹配数 → C(n)

• n+1 个叶子的二叉树形态数 → C(n)

• n×n 网格从 (0,0) 到 (n,n) 不越过对角线的路径数 → C(n)

• n 个元素的出栈序列数 → C(n)

• 凸 n+2 边形的三角剖分数 → C(n)

通项公式：C(n) = C(2n,n) / (n+1)，也可以直接用递推算。

⚡递推 vs 递归辨析

递推和递归都基于"用已知求未知"的思想，但方向相反：

📈 递推（自底向上）

从小规模到大规模
f(1) → f(2) → ... → f(n)
用循环实现
每项只算一次，快
不存在栈溢出风险
竞赛首选！

📉 递归（自顶向下）

从大规模到小规模
f(n) → f(n-1) → ... → f(1)
用函数调用自身实现
可能重复计算，慢
n 太大可能栈溢出
需要记忆化优化

✅ 递推版（O(n)）

C++递推

long long f[100];
f[1]=1; f[2]=1;
for(int i=3;i<=n;i++)
    f[i]=f[i-1]+f[i-2];
cout<<f[n];

❌ 朴素递归（O(2ⁿ)）

C++递归

long long fib(int n){
    if(n<=2) return 1;
    return fib(n-1) 
         + fib(n-2);
}
cout<<fib(n);

n	递推耗时	朴素递归耗时	差距
n=10	< 0.001ms	< 0.001ms	差不多
n=30	< 0.001ms	~5ms	~5000倍
n=40	< 0.001ms	~10秒	~千万倍
n=50	< 0.001ms	~数小时	无法接受

🔑 竞赛箴言

看到递推关系 → 优先写递推（循环），又快又安全！
递归只在以下情况使用：① 题目要求输出递归过程 ② 配合记忆化搜索 ③ 分治/回溯类问题

模块 03

实践应用

通过分析和编程题，巩固递推法的设计与分析能力。

题1递推公式推导

题目：用 1×2 的多米诺骨牌铺满 2×n 的棋盘，有多少种铺法？请推导递推关系。

提示：考虑最左边一列的两种铺法。

查看参考答案

分析最左列的铺法：

① 竖着放一块（1×2）→ 占掉1列，剩下 2×(n-1) → f(n-1) 种

② 横着放两块（2×1×2）→ 占掉2列，剩下 2×(n-2) → f(n-2) 种

递推关系：f(n) = f(n-1) + f(n-2)

初始值：f(1) = 1, f(2) = 2

这就是斐波那契数列！f(n): 1, 2, 3, 5, 8, 13, 21, ...

验证：n=3 → 竖+竖+竖 / 横横+竖 / 竖+横横 = 3 种 ✅

题2数列求值

题目：已知数列 a(1)=2, a(2)=3, a(n)=2×a(n-1)-a(n-2)+1。求 a(10)。

查看参考答案

#include <iostream>
using namespace std;
int main() {
    long long a[11];
    a[1] = 2; a[2] = 3;
    for(int i=3; i<=10; i++)
        a[i] = 2*a[i-1] - a[i-2] + 1;
    cout << a[10] << endl;
    return 0;
}

n	1	2	3	4	5	6	7	8	9	10
a(n)	2	3	5	8	12	17	23	30	38	47

答案：a(10) = 47

观察差值：1, 2, 3, 4, 5, 6, 7, 8, 9 — 是等差递增！

题3综合编程

题目：在一个 n×1 的格子里填色，每格可涂红色或蓝色，但不能有连续三格同色。求 n=20 时的填色方案数。

查看参考答案

分析：设 f(n) 为 n 格的合法方案数。考虑最后一格：

如果最后 1 格和前 1 格颜色不同：前 n-1 格合法即可 → f(n-1) 种

如果最后 1 格和前 1 格颜色相同：倒数第 3 格必须不同色 → f(n-2) 种

递推关系：f(n) = f(n-1) + f(n-2)

初始值：f(1) = 2（红或蓝）, f(2) = 4（红红、红蓝、蓝红、蓝蓝都行）

#include <iostream>
using namespace std;
int main() {
    long long f[21];
    f[1] = 2; f[2] = 4;
    for(int i=3; i<=20; i++)
        f[i] = f[i-1] + f[i-2];
    cout << f[20] << endl;
    return 0;
}

运行结果

知识板块	必须记住的核心
递推三要素	初始值 + 递推关系 + 目标项
斐波那契	F(n) = F(n-1) + F(n-2), F(1)=F(2)=1
爬楼梯	f(n) = f(n-1) + f(n-2), f(1)=1, f(2)=2
汉诺塔	T(n) = 2T(n-1) + 1 = 2ⁿ - 1
Catalan数	C(n) = Σ C(k)×C(n-1-k), C(0)=1
递推 vs 递归	递推 O(n) 快，朴素递归 O(2ⁿ) 慢
竞赛首选	自底向上递推（循环实现）

✅ 正确

数组大小开 f[MAX]，MAX 至少是 n+1 或更大。推荐直接开大一点。

口诀：数组开大点，n+5 保平安！

速查递推法速查表

经典模型	递推关系	初始值	复杂度
斐波那契	F(n) = F(n-1) + F(n-2)	F(1)=F(2)=1	O(n)
爬楼梯	f(n) = f(n-1) + f(n-2)	f(1)=1, f(2)=2	O(n)
汉诺塔	T(n) = 2T(n-1) + 1	T(1)=1	O(n)
多米诺铺砖	f(n) = f(n-1) + f(n-2)	f(1)=1, f(2)=2	O(n)
Catalan数	C(n) = Σ C(k)×C(n-1-k)	C(0)=1	O(n²)
杨辉三角	C(n,k) = C(n-1,k-1) + C(n-1,k)	C(n,0)=C(n,n)=1	O(n²)

📌知识点笔记卡

🧩 递推三要素

初始值（base case）

递推关系（核心）

目标项（答案）

🐰 斐波那契

F(n)=F(n-1)+F(n-2)

兔子、爬楼梯、铺砖

都是这个模型

🗼 汉诺塔

T(n)=2T(n-1)+1

= 2ⁿ-1

指数级增长

🔢 Catalan数

C(n)=Σ C(k)C(n-1-k)

括号匹配/二叉树

出栈序列/三角剖分

⚡ 递推 vs 递归

递推：小到大，快

递归：大到小，慢

竞赛首选递推

🚀 矩阵快速幂

线性递推 → 矩阵乘法

O(n) → O(log n)

n=10¹⁸也能算

课后练习

分层练习作业

考点：自底向上递推与自顶向下朴素递归的差别，来自子问题是否被重复求解。

易错：认为递推的优势是“代码更短”或“更省空间”——它的核心优势是每个子问题只计算一次。

A4编程题

用递推法计算斐波那契数列的第 n 项（n≤50）。注意使用 long long 防溢出。

查看参考答案

#include <iostream>
using namespace std;
int main() {
    int n; cin >> n;
    long long f[55];
    f[1] = 1; f[2] = 1;
    for(int i=3;i<=n;i++) f[i]=f[i-1]+f[i-2];
    cout << f[n] << endl;
    return 0;
}

思路：先固定两个边界 f[1]=f[2]=1，再从 i=3 开始用 f[i]=f[i-1]+f[i-2] 顺序推下去。

易错：用 int 存 f[50]（约 1.2×10¹⁰）会溢出，必须用 long long。

🟡 B组 · 提高（4题）

B1编程题

爬楼梯问题：每次可以走 1、2 或 3 阶，求走到第 n 阶的方案数。推导递推关系并编程。

查看参考答案

递推关系：到第 n 阶有3种方式到达 → f(n) = f(n-1) + f(n-2) + f(n-3)

初始值：f(1)=1, f(2)=2, f(3)=4

#include <iostream>
using namespace std;
int main() {
    int n; cin >> n;
    long long f[55];
    f[1]=1; f[2]=2; f[3]=4;
    for(int i=4;i<=n;i++)
        f[i]=f[i-1]+f[i-2]+f[i-3];
    cout << f[n] << endl;
    return 0;
}

思路：最后一步可能是走 1、2 或 3 阶，因此 f(n) 等于三种来源之和，边界为 f(1)=1、f(2)=2、f(3)=4。

易错：把初始值照搬成斐波那契的 f(1)=1、f(2)=1，或从 i=3 起循环把已经算好的 f(3) 覆盖成错误值。

B2编程题

错排问题：n 封信装 n 个信封，全部装错的方案数 D(n)。推导递推关系并求 D(10)。

查看参考答案

递推关系：D(n) = (n-1) × [D(n-1) + D(n-2)]

分析：第 n 封信放到第 k 个信封（k≠n，共 n-1 种选择）：

• 第 k 封信放到了第 n 个信封 → 剩下 n-2 封错排 → D(n-2)

• 第 k 封信没放到第 n 个信封 → 相当于 n-1 封错排 → D(n-1)

初始值：D(1) = 0, D(2) = 1

#include <iostream>
using namespace std;
int main() {
    long long D[21];
    D[1]=0; D[2]=1;
    for(int i=3;i<=10;i++)
        D[i]=(i-1)*(D[i-1]+D[i-2]);
    cout << D[10] << endl; // 1334961
    return 0;
}

易错：把初始值写成 D(1)=1（正确应为 D(1)=0）；或用 int 存 D(21) 数组，后续项会溢出。

B3编程题

用递推法计算 Catalan 数 C(n)（n≤20），并验证 C(5)=42。

查看参考答案

#include <iostream>
using namespace std;
int main() {
    int n; cin >> n;
    long long C[25]={};
    C[0]=1;
    for(int i=1;i<=n;i++)
        for(int k=0;k<i;k++)
            C[i]+=C[k]*C[i-1-k];
    cout << C[n] << endl;
    return 0;
}

运行结果

输入：5
输出：42

思路：Catalan 数递推为 C(i)=ΣC(k)·C(i−1−k)，外层 i 从小到大递推，保证用到的都是已算好的值。

易错：忘记给数组清零（long long C[25]={}），累加时把随机值算进去；或用 int 存储导致 C(20) 溢出。

B4分析题

杨辉三角的第 n 行第 k 个数 C(n,k) 满足递推关系 C(n,k)=C(n-1,k-1)+C(n-1,k)。用递推法打印前 8 行杨辉三角。

查看参考答案

#include <iostream>
using namespace std;
int C[10][10];
int main() {
    for(int i=0;i<=7;i++){
        C[i][0]=C[i][i]=1;
        for(int j=1;j<i;j++)
            C[i][j]=C[i-1][j-1]+C[i-1][j];
    }
    for(int i=0;i<=7;i++){
        for(int j=0;j<=i;j++)
            cout << C[i][j] << " ";
        cout << endl;
    }
    return 0;
}

运行结果

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1

初始值：dp[0][1] = 1, 其余为 0

#include <iostream>
using namespace std;
int dp[1005][35];
int main() {
    int n, m; cin >> n >> m;
    dp[0][1] = 1;
    for(int j=1; j<=m; j++)
        for(int i=1; i<=n; i++){
            int left = (i-2+n)%n+1;   // 环形左邻
            int right = i%n+1;        // 环形右邻
            dp[j][i] = dp[j-1][left] + dp[j-1][right];
        }
    cout << dp[m][1] << endl;
    return 0;
}

这是经典的二维递推，状态是 (传球次数, 球在谁手中)。

思路：按“传球次数 j”分层设计状态 dp[j][i]，由上一层的左右邻居转移而来，环形下标用取模处理。

易错：环形左右邻居直接用 i±1 而不取模（下标会变成 0 或 n+1）；或用一维数组却没处理好层次依赖。

C4综合编程

给定递推 a(1)=1, a(2)=2, a(n)=3a(n-1)-2a(n-2)（n≥3）。求 a(n) mod 1000000007 的值（n≤10⁹）。提示：用矩阵快速幂。

查看参考答案

矩阵形式：

[a(n) ] [3 -2] ^ (n-2) [a(2)]
[a(n-1)] = [1 0] × [a(1)]

用快速幂计算矩阵的 (n-2) 次方，时间复杂度 O(log n)。

#include <iostream>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
struct Mat { ll m[2][2]; };
Mat mul(Mat A, Mat B) {
    Mat C = {{{0,0},{0,0}}};
    for(int i=0;i<2;i++)
        for(int k=0;k<2;k++)
            for(int j=0;j<2;j++)
                C.m[i][j]=(C.m[i][j]+A.m[i][k]*B.m[k][j])%MOD;
    return C;
}
Mat power(Mat A, ll p) {
    Mat R = {{{1,0},{0,1}}}; // 单位矩阵
    while(p > 0) {
        if(p & 1) R = mul(R, A);
        A = mul(A, A);
        p >>= 1;
    }
    return R;
}
int main() {
    ll n; cin >> n;
    if(n==1){cout<<1; return 0;}
    if(n==2){cout<<2; return 0;}
    Mat T = {{{3,MOD-2},{1,0}}};
    Mat R = power(T, n-2);
    ll ans = (R.m[0][0]*2 + R.m[0][1]*1) % MOD;
    cout << ans << endl;
    return 0;
}

注意：递推中有减法 -2a(n-2)，在模运算中需要写成 (MOD-2) 来避免负数。

思路：把二阶递推写成 2×2 矩阵的幂次形式，再用矩阵快速幂把 O(n) 降到 O(log n)。

情景导航

爬楼梯

存钱复利

铺地砖

击鼓传花

知识探究

要素① 初始值

要素② 递推关系

要素③ 目标项

💡 时间复杂度对比

💡 注意初始值的差异！

💡 Catalan 数的经典应用

📈 递推（自底向上）

📉 递归（自顶向下）

✅ 递推版（O(n)）

❌ 朴素递归（O(2ⁿ)）

实践应用

总结提升

💡 当 n 非常大（10¹⁸）时怎么办？

💡 学完本讲，你应该掌握的6项能力

学习检测

初始值设错

递推方向搞反

整数溢出

用朴素递归算斐波那契

数组越界

🧩 递推三要素

🐰 斐波那契

🗼 汉诺塔

🔢 Catalan数

⚡ 递推 vs 递归

🚀 矩阵快速幂

分层练习作业

🟢 A组 · 基础（4题）

斐波那契数列的第 8 项是（）（F(1)=1, F(2)=1）

汉诺塔问题中，移动 n 个盘子的最少步数是（）

递推法相比朴素递归的优势是（）

用递推法计算斐波那契数列的第 n 项（n≤50）。注意使用 long long 防溢出。

🟡 B组 · 提高（4题）

爬楼梯问题：每次可以走 1、2 或 3 阶，求走到第 n 阶的方案数。推导递推关系并编程。

错排问题：n 封信装 n 个信封，全部装错的方案数 D(n)。推导递推关系并求 D(10)。

用递推法计算 Catalan 数 C(n)（n≤20），并验证 C(5)=42。

杨辉三角的第 n 行第 k 个数 C(n,k) 满足递推关系 C(n,k)=C(n-1,k-1)+C(n-1,k)。用递推法打印前 8 行杨辉三角。

🔴 C组 · 挑战（4题）

斐波那契数列 F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2)。F(20) 的值为（）

5个元素的出栈序列共有多少种？

编号为 1~n 的人传球，球从 1 号开始。每次可以传给相邻的人（i-1 或 i+1，环形）。传 m 次后球回到 1 号手中的方案数。用递推法求解。

给定递推 a(1)=1, a(2)=2, a(n)=3a(n-1)-2a(n-2)（n≥3）。求 a(n) mod 1000000007 的值（n≤10⁹）。提示：用矩阵快速幂。