Skip to content

找规律与打表

先用小数据暴力求答案,观察规律后写通用解或直接打表。

Updated View as Markdown

有些题一眼看不出通项,有些题的数据范围小得可以做文章。这两类题都有同一个突破口:先用小数据把答案算出来,看看有没有规律。

本章的知识点与 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。

方法一:小数据暴力找规律

流程只有四步:

  1. 写一个暴力程序,对 n = 1, 2, 3, \dots 依次算出答案。
  2. 把答案列成数列,观察规律:等差、等比、斐波那契、卡特兰,还是别的。
  3. 猜出通项公式或递推式。
  4. 用暴力在小数据上验证这个猜测,确认无误后再写成高效解法。

例:约瑟夫环。 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;

打表有两种做法:

  1. 本地写一个暴力程序,把 n 在范围内的答案全部打印出来,手工粘进代码。适合范围很小、答案很难现算的题。
  2. 在程序开头跑一遍预处理,把结果存进数组再查。严格说这属于「预处理」,不算打表,但通用性更好。

打表的适用条件很苛刻:数据范围固定,而且不大。范围一变,表就失效了。

常见数列

看到一串数能认出它的来历,是初赛常识题和复赛计数题的基本功。

数列 前几项 常见出处
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: 42

1 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 代进去,不漏边界。
Navigation

Type to search…

↑↓ navigate↵ selectEsc close