
有些题一眼看不出通项,有些题的数据范围小得可以做文章。这两类题都有同一个突破口:先用小数据把答案算出来,看看有没有规律。
本章的知识点与 GESP、CSP-J/S 大纲的对应关系如下。
| 考试 | 大纲要求 | 本章位置 |
|---|---|---|
| NOI 入门级 | 1.4.1 算法概念与描述 | 小数据暴力找规律 |
| CSP-J/S 第一轮 | 找规律是阅读程序和完善程序里常见的解题突破口 | 全章 |
| CSP-J/S 入门级 | 4.3 基础算法:递推与计数(错排列、卡特兰数) | 练习 1、练习 3、练习 5 |
| GESP C++ 六级 | 常见数列的识别与递推式推导 | 常见数列、练习 1~5 |
什么时候用
- 题目给了递推或计数的定义,但直接按定义算规模太大。
- 一眼看不出通项,但写一个暴力程序很容易。
- 数据范围固定在很小的一段,比如
n \le 20。
方法一:小数据暴力找规律
流程只有四步:
- 写一个暴力程序,对
n = 1, 2, 3, \dots依次算出答案。 - 把答案列成数列,观察规律:等差、等比、斐波那契、卡特兰,还是别的。
- 猜出通项公式或递推式。
- 用暴力在小数据上验证这个猜测,确认无误后再写成高效解法。
例:约瑟夫环。 n 个人围成一圈,从第一个人开始报数,每次数到第 k 个人出圈,求最后剩下的人的编号。
直接模拟能算出小数据。把 n 从 1 开始列出来观察,会发现一个递推关系:
f(1) = 0, \qquad f(n) = (f(n-1) + k) \bmod n
答案是 f(n) + 1。
int f = 0;
for (int i = 2; i <= n; i++) {
f = (f + k) % i;
}
cout << f + 1 << endl;这个递推不是背下来的,是先暴力、再观察、再验证得到的。自己推一遍,比记住结论可靠得多。
方法二:直接打表
如果数据范围是固定的一小段,可以把每个 n 的答案预先算好,写进数组直接查。下面这张表存的是卡特兰数的前 11 项:
// 卡特兰数 C(0)、C(1)、...、C(10)
int table[11] = {1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796};
cout << table[n] << endl;打表有两种做法:
- 本地写一个暴力程序,把
n在范围内的答案全部打印出来,手工粘进代码。适合范围很小、答案很难现算的题。 - 在程序开头跑一遍预处理,把结果存进数组再查。严格说这属于「预处理」,不算打表,但通用性更好。
打表的适用条件很苛刻:数据范围固定,而且不大。范围一变,表就失效了。
常见数列
看到一串数能认出它的来历,是初赛常识题和复赛计数题的基本功。
| 数列 | 前几项 | 常见出处 |
|---|---|---|
| 2 的幂 | 1, 2, 4, 8, 16, 32 | 子集个数、满二叉树节点数 |
| 阶乘 | 1, 1, 2, 6, 24, 120 | 全排列个数 |
| 斐波那契 | 1, 1, 2, 3, 5, 8, 13 | 爬楼梯、递推计数 |
| 卡特兰数 | 1, 1, 2, 5, 14, 42, 132 | 出入栈方案数、二叉树形态数、括号匹配 |
| 三角形数 | 1, 3, 6, 10, 15 | 1 + 2 + \dots + n |
| 错排列数 | 0, 1, 2, 9, 44, 265 | 全装错信封、礼物交换 |
| 平面分割数 | 1, 2, 4, 7, 11, 16 | n 条直线最多分出的区域数 |
看到 1 1 2 5 14 42 想到卡特兰数,看到 1 1 2 3 5 8 想到斐波那契。这一条能省下不少现场推导的时间。
示例:从暴力到规律——直线的平面分割数
题目描述
平面上画 n 条直线,任意两条不平行、任意三条不共点。这些直线最多把平面分成多少个区域?
输入格式
一个整数 n。
输出格式
输出一个整数,表示最多划分出的区域数。
输入输出样例
输入
3输出
7数据范围
0 \le n \le 10^4。
题目分析
这道题是完整演练「暴力 → 找规律 → 验证」四步的最佳素材,因为直接暴力的几何模拟很难写,而小数据可以手工推。
第一步:小数据。 动手画一画:
n = 0:1 个区域(整个平面);n = 1:2 个区域;n = 2:2 条直线相交,4 个区域;n = 3:3 条直线两两相交、不共点,7 个区域。
得到数列:1, 2, 4, 7。
第二步:看差分。 相邻两项的差是 1, 2, 3——正好是 n!也就是说:
f(n) - f(n-1) = n
第三步:验证这个猜测。 第 n 条直线会被前 n-1 条直线切成 n 段(因为它和前 n-1 条各交于一个不同的点,产生 n-1 个交点,把这条直线分成 n 段),每一段都把一个已有区域一分为二,所以新增 n 个区域。猜对了。
第四步:写出通项。 累加得到
f(n) = 1 + \sum_{i=1}^{n} i = 1 + \frac{n(n+1)}{2} = \frac{n^2 + n + 2}{2}
这道题给的启示:当通项不好直接猜时,先看「相邻项的差」。差分数列往往比原数列更容易看出规律——这和「前缀和 / 差分」那一章是同一个思路。
注意
n = 0时公式给出\dfrac{0+0+2}{2} = 1,正好正确。验证通项时一定要把n = 0和n = 1代进去,这是最容易漏的边界。
参考代码
用 long long:n 到 10^4 时 n^2 = 10^8,int 勉强够,但 n 再大一点就溢出了,养成习惯。
常见易错点
- 暴力程序本身写错。 找出来的规律自然也是错的。先用已知答案的小数据检查暴力程序,再拿它去生成数列。
- 猜出来的公式不验证。 两个数列前几项一样、后面分道扬镳的情况很常见,猜完必须在小数据上对一遍。
- 一心找通项,忽略了题目本来就允许递推。 能找到递推就不必强求通项,
O(n)的递推往往比通项更好写。 - 打表数组开小了。
n超出范围后越界,读到的是一段垃圾数据。 - 打表时忘了边界。
n = 0、n = 1这类情况最容易漏,导致第一个元素就对不上。 - 取模搞错。 答案要求对
10^9+7取模时,打表出来的数也要取模,别把中间结果算爆。 - 把打表当常规手段。 数据范围一旦变大,表就存不下;打表是竞赛里的应急办法,工程代码里不会这么写。
- 忽略
n = 0的边界。卡特兰数、平面分割数这类问题,n = 0往往有非零答案(1 或 1 块),递推从n = 1起步就会漏掉。 - 只盯原数列不看差分。通项不好猜时先算相邻项的差,二次规律一眼就能看出来。
- 认不出同一个数列的不同形态。二叉树形态数、合法括号数、出入栈方案数都是卡特兰数,认出这一点能省掉重新推导的时间。
练习
练习 1:错排列
在线评测练习:P1525 错排列
题目描述
有 n 封信和 n 个写好地址的信封。如果 n 封信全部装错(即每一封信都没有放进它对应的信封),一共有多少种装法?
输入格式
一个整数 n。
输出格式
输出一个整数,表示全部装错的方案数。
数据范围
1 \le n \le 20
输入输出样例
输入
3输出
2题目分析
这是本章「小数据暴力找规律」四步的典型演练:直接按定义算(枚举全排列、删掉有不动点的)规模是 n!,n \le 20 时完全跑不动,所以先用暴力求小数据、再找递推。
写一个全排列暴力,把 n = 1, 2, 3, 4, 5 的答案跑出来(这正是「错排列数」数列):
0 1 2 9 44观察相邻项的关系,可以得到错排列的经典递推:
D(1) = 0,\quad D(2) = 1,\quad D(n) = (n-1)\bigl(D(n-1) + D(n-2)\bigr)\ (n \ge 3)
直观理解:考虑第 n 封信,它必须放入某个信封 k(k \ne n,共 n-1 种选择);分两类——若第 k 封信恰好放入第 n 个信封,剩下 n-2 封信是子问题 D(n-2);否则把「第 n 个信封」当成第 k 封信该去的位置,剩下 n-1 封信又是子问题 D(n-1)。
按递推从 D(1)、D(2) 起步,n \le 20 一瞬间就跑完。注意边界 D(1)=0、D(2)=1 是手算出来的,递推从 n=3 才开始,别忘了这两项。
猜完递推一定要拿暴力对一下前几项,确认没推错——这是本章反复强调的一步。
参考代码
练习 2:汉诺塔的最少移动次数
在线评测练习:P1527 汉诺塔的最少移动次数
题目描述
有三根柱子和 n 个大小不同的盘子,开始时盘子按小到大叠在第一根柱子上。每次只能移动一个盘子,且大盘子不能放在小盘子上面。把所有盘子移到第三根柱子上,最少要移动多少次?
输入格式
一个整数 n。
输出格式
输出一个整数,表示最少移动次数。
数据范围
1 \le n \le 60
输入输出样例
输入
3输出
7题目分析
按本章套路,先写一个「真模拟」的暴力:把 n 个盘子按规则真的搬一遍、数一共搬了多少步。对小数据跑出:
n = 1, 2, 3, 4, 5 \;\longrightarrow\; 1, 3, 7, 15, 31
数列一眼能认出是 2^n - 1(也就是本章「常见数列」里的 2 的幂减一)。
规律也好推:要把 n 个盘子移到第三根柱子,必须先把上面 n-1 个移到第二根(f(n-1) 步),再把最大的那个移过去(1 步),最后把 n-1 个移回第三根(f(n-1) 步)。所以
f(1) = 1,\qquad f(n) = 2f(n-1) + 1
展开就是 f(n) = 2^n - 1。用暴力在小数据上验证这个通项,确认无误后再写高效解——这正是本章强调的四步。
n = 60 时答案是 2^{60} - 1 \approx 1.15 \times 10^{18},int 装不下,必须用 long long(1LL << n 的位移也要带 1LL,否则按 int 移位会溢出)。
参考代码
练习 3:不同二叉树的形态数
在线评测练习:P1526 不同二叉树的形态数
题目描述
由 n 个节点组成的不同二叉树有多少种形态?左右子树交换算不同。
输入格式
一个整数 n。
输出格式
输出一个整数,表示不同形态的二叉树个数。
数据范围
1 \le n \le 30
输入输出样例
输入
3输出
5题目分析
先按本章的思路用「小数据」把答案列出来:手工或写个小暴力枚举 n = 1, 2, 3, 4, 5 的形态,得到
1, 2, 5, 14, 42
看到 1 2 5 14 42,应该立刻想到卡特兰数(本章「常见数列」表里就有它;注意这里 n 个节点对应的是 C_n,而非 C_{n-1})。
递推也很好想:固定根节点,枚举左子树有几个点。设左边 j 个、右边 n-1-j 个,左右子树各自独立,所以
C_0 = 1,\qquad C_n = \sum_{j=0}^{n-1} C_j \times C_{n-1-j}
这是一个 O(n^2) 的递推,n \le 30 瞬间跑完。
推理过程要和暴力对上:算出 C_3 = 5 后,用暴力的结果核对一下;递推算出的前几项必须和暴力枚举的前几项一致,才能确认没错。这也是为什么本章强调「先暴力、再找规律、再验证」。
n = 30 时答案约 3.8 \times 10^{15},仍然在 long long 范围内(int 早已溢出)。
参考代码
练习 4(进阶):计数问题
在线评测练习:P1142 计数问题
题目背景
NOIP2013 普及组 T1
题目描述
试计算在区间 1 到 n 的所有整数中,数字 x(0\le x\le9)共出现了多少次?例如,在 1 到 11 中,即在 1,2,3,4,5,6,7,8,9,10,11 中,数字 1 出现了 4 次。
输入格式
2 个整数 n,x,之间用一个空格隔开。
输出格式
1 个整数,表示 x 出现的次数。
数据范围
对于 100\% 的数据,1\le n\le 10^6,0\le x \le 9。
输入输出样例
输入
11 1输出
4题目分析
这一题和前面三题的方向相反:数据范围小到可以直接暴力,根本不需要找规律。
枚举 1 到 n 的每个整数,用 % 10 和 / 10 拆出每一位,统计其中等于 x 的个数即可。复杂度 O(n \log n),n = 10^6 时只有千把万次操作。
把它放在本章末尾是想提醒一句:找规律和打表是「暴力过不了」时的出路,不是默认选项。先看数据范围,能暴力就暴力,暴力的正确率最高。
参考代码
练习 5:合法括号序列数
在线评测练习:P1448 合法括号序列
题目描述
求由 n 对括号组成的合法括号序列的个数。例如 n = 3 时,合法序列是 ((()))、(()())、(())()、()(())、()()(),共 5 个。
输入格式
一个正整数 n。
输出格式
输出一个整数,表示合法括号序列的个数。
数据范围
1 \le n \le 30。
输入输出样例
输入
3输出
5题目分析
先用暴力把前几项跑出来,这是本章的核心动作。写个 DFS 枚举所有 2n 位、且恰好 n 个左括号的串,检查合法性,得到:
n=1: 1
n=2: 2
n=3: 5
n=4: 14
n=5: 421 2 5 14 42 —— 这正是卡特兰数(和练习 3「二叉树形态数」的数列完全一样)。
为什么两题数列相同?因为「n 对括号的合法序列数」和「n 个节点的二叉树形态数」之间存在一一对应(括号序列 ↔ 二叉树),这是组合数学里一个漂亮的结论。能在暴力数据里认出「这两题答案一样」,本身就是找规律的收获。
递推式和练习 3 完全一样:
C_0 = 1, \qquad C_n = \sum_{j=0}^{n-1} C_j \times C_{n-1-j}
直观理解:看第一个左括号和它匹配的右括号,两者之间夹着 j 对括号、外面剩下 n-1-j 对,两段独立。
虽然本题 n 从 1 开始,递推仍要从 C_0 = 1 起步——空序列算一种合法序列,它是递推的种子;从 C_1 = 1 起手同样可行,但统一用 C_0 更不容易漏。
参考代码
练习 6:直线的平面分割数
在线评测练习:P1524 直线的平面分割数
题目描述
平面上画 n 条直线,任意两条不平行、任意三条不共点。这些直线最多把平面分成多少个区域?
输入格式
一个整数 n。
输出格式
输出一个整数,表示最多的区域数。
数据范围
0 \le n \le 10^4
输入输出样例
输入
3输出
7题目分析
正文「示例」里完整推过。这里重点练**「差分数列」这个找规律的技巧**:
原数列 f(n):1, 2, 4, 7, 11, 16
差分数列:1, 2, 3, 4, 5
差不难看出就是 n 本身,所以 f(n) - f(n-1) = n,累加得 f(n) = 1 + \dfrac{n(n+1)}{2}。
遇到「差是等差」的数列,原数列就是二次的——这个判断能省掉很多瞎猜:
| 差分情况 | 原数列类型 |
|---|---|
| 差为常数 | 一次(等差) |
| 差为等差(二阶差为常数) | 二次 |
| 比值为常数 | 等比 |
| 差成斐波那契 | 斐波那契型 |
边界照例验一遍:n = 0 时公式给 \dfrac{0 + 0 + 2}{2} = 1,是正确答案(0 条直线把平面分成 1 块)。这一项常常被忘记。
参考代码
小结
找规律和打表都是「先求出小数据,再回头找规律」的具体做法,共同前提是小数据容易算。
- 找规律的四步:暴力出小数据、观察数列、猜通项或递推、用暴力验证。
- 打表只适合数据范围固定且很小的题,把答案预先算好硬编码;范围一变就失效。
- 常见数列(2 的幂、阶乘、斐波那契、卡特兰数)要认识,看到前几项能反应过来。
- 别急着找通项。数据范围允许暴力时,直接暴力就是最稳的解法。
学完这一章,下面这些事应该能独立完成:
- 拿到一道计数题,先判断「能不能暴力」,再决定要不要找规律。
- 写出暴力程序,把小数据跑成一个数列。
- 从数列里认出常见规律,并写出对应的递推式。
- 用暴力验证猜出来的公式,而不是直接写进最终代码。
- 说清打表的适用条件和它的风险。
- 用「看差分数列」的方法识别二次规律(差为等差 → 原数列二次)。
- 认出卡特兰数的多种等价形态(二叉树形态数、合法括号序列数、出入栈方案数)。
- 验证通项时把
n = 0、n = 1代进去,不漏边界。