---
title: "找规律与打表"
description: "先用小数据暴力求答案，观察规律后写通用解或直接打表。"
---

> Documentation Index
> Fetch the complete documentation index at: https://cppguide.xyz/llms.txt
> Use this file to discover all available pages before exploring further.

# 找规律与打表

![](https://img.dailyup.xyz/optimized/8208353660303-9cbfcf79-89f9-4909-a97d-ddd62f11bc7a.jpg)

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

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

```cpp
int f = 0;
for (int i = 2; i <= n; i++) {
    f = (f + k) % i;
}
cout << f + 1 << endl;

这个递推不是背下来的，是先暴力、再观察、再验证得到的。自己推一遍，比记住结论可靠得多。

## 方法二：直接打表

如果数据范围是固定的一小段，可以把每个 $n$ 的答案预先算好，写进数组直接查。下面这张表存的是卡特兰数的前 11 项：

```cpp
// 卡特兰数 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$ 代进去**，这是最容易漏的边界。

**参考代码**

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/algopatterns/brute-force/index.md

用 `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 错排列](https://dailyup.run/tasks/609)

#### 题目描述

有 $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$ 才开始，别忘了这两项。

猜完递推一定要拿暴力对一下前几项，确认没推错——这是本章反复强调的一步。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/algopatterns/brute-force/index.md

### 练习 2：汉诺塔的最少移动次数

在线评测练习：[P1527 汉诺塔的最少移动次数](https://dailyup.run/tasks/611)

#### 题目描述

有三根柱子和 $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` 移位会溢出）。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/algopatterns/brute-force/index.md

### 练习 3：不同二叉树的形态数

在线评测练习：[P1526 不同二叉树的形态数](https://dailyup.run/tasks/610)

#### 题目描述

由 $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` 早已溢出）。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/algopatterns/brute-force/index.md

### 练习 4（进阶）：计数问题

在线评测练习：[P1142 计数问题](https://dailyup.run/tasks/226)

#### 题目背景

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$ 时只有千把万次操作。

把它放在本章末尾是想提醒一句：找规律和打表是「暴力过不了」时的出路，不是默认选项。先看数据范围，**能暴力就暴力，暴力的正确率最高**。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/algopatterns/brute-force/index.md

### 练习 5：合法括号序列数

在线评测练习：[P1448 合法括号序列](https://dailyup.run/tasks/532)

#### 题目描述

求由 $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$ 更不容易漏。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/algopatterns/brute-force/index.md

### 练习 6：直线的平面分割数

在线评测练习：[P1524 直线的平面分割数](https://dailyup.run/tasks/608)

#### 题目描述

平面上画 $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 块）。这一项常常被忘记。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/algopatterns/brute-force/index.md

## 小结

找规律和打表都是「先求出小数据，再回头找规律」的具体做法，共同前提是**小数据容易算**。

- 找规律的四步：暴力出小数据、观察数列、猜通项或递推、用暴力验证。
- 打表只适合数据范围固定且很小的题，把答案预先算好硬编码；范围一变就失效。
- 常见数列（2 的幂、阶乘、斐波那契、卡特兰数）要认识，看到前几项能反应过来。
- 别急着找通项。数据范围允许暴力时，直接暴力就是最稳的解法。

学完这一章，下面这些事应该能独立完成：

- 拿到一道计数题，先判断「能不能暴力」，再决定要不要找规律。
- 写出暴力程序，把小数据跑成一个数列。
- 从数列里认出常见规律，并写出对应的递推式。
- 用暴力验证猜出来的公式，而不是直接写进最终代码。
- 说清打表的适用条件和它的风险。
- 用「看差分数列」的方法识别二次规律（差为等差 → 原数列二次）。
- 认出卡特兰数的多种等价形态（二叉树形态数、合法括号序列数、出入栈方案数）。
- 验证通项时把 $n = 0$、$n = 1$ 代进去，不漏边界。

Source: https://cppguide.xyz/algopatterns/brute-force/index.mdx
