信息学竞赛 C++ 教材

Appearance

第 44 章 递归深潜——汉诺塔与全排列 ​

🏗️ 前情回顾：第 26 章你用递归写了阶乘和斐波那契，掌握了"自己调用自己"的基本功。但那些都是单线递归——一条路走到黑。真正强大的递归能展开分支，每条分支都探索一种可能性，然后选一条走、走不通就退回来换另一条。这就是本章的主角——回溯。

🎯 本章目标 ​

学完这一章，你能：

  • 用递归三要素分析汉诺塔问题，写出优雅的移动方案
  • 理解"回溯"思想：试一条路、不行就退、换下一条
  • 用回溯生成全排列——"n 个人拍照，有多少种排队方式"
  • 用回溯解决组合枚举——"从 n 个东西里选 k 个"
  • 掌握回溯的"试—记—撤"三步曲
  • 初步了解可行性剪枝——提前砍掉不可能的分支

📖 故事引入 ​

传说在印度贝拿勒斯神庙里，有三根金刚石柱子，其中一根上穿着 64 个金盘，从下到上按大小递减。僧侣们日夜不停地把金盘从一根柱子移到另一根，规则是：每次只能移动一个盘子，大盘子不能放在小盘子上面。传说当 64 个盘子全部移完时，世界就会毁灭。

别担心——即使每秒移动一次，64 个盘子也需要约 5800 亿年，比宇宙的年龄还长。

另一个场景：你们班 5 个同学要拍毕业照，站成一排。有多少种不同的排队方式？如果让你把每种排队方式都列出来，你打算怎么写程序？

这两个看似不相关的问题，背后是同一个思想：递归地枚举所有可能性。前者是经典的汉诺塔，后者是全排列——都是回溯算法的绝佳案例。

🧱 知识讲解 ​

44.1 递归三要素快速回顾 ​

还记得第 26 章的三要素吗？我们用它来重新审视：

要素含义判断标准
边界条件问题小到可以直接解决不需要再递归了
递推关系大问题 = 小问题 + 额外操作参数在向边界靠近
递归调用调用自己，规模缩小每次调用 n 都变小

44.2 汉诺塔：递归的封神之作 ​

问题：有 n 个盘子，从小到大编号 1~n，初始都在 A 柱。借助 B 柱，把所有盘子移到 C 柱。规则：每次移一个，大盘不能压小盘。

递归思路：

把 n 个盘子从 from 移到 to（借助 aux），可以拆成三步：

① 把上面 n-1 个盘子从 from 移到 aux（借助 to）
② 把最底下第 n 个盘子从 from 移到 to
③ 把 n-1 个盘子从 aux 移到 to（借助 from）

你看：步骤①和③是规模更小的汉诺塔问题！边界是 n == 1：直接移过去。

这套思路就像将军指挥部队过桥：先让前 n-1 个人到中间站，然后将军自己过去，再让那 n-1 个人从中间站到终点。

cpp
void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {                          // 边界：只有一个盘子
        cout << from << " -> " << to << endl;
        return;
    }
    hanoi(n - 1, from, aux, to);           // ① 上面n-1个移到辅助柱
    cout << from << " -> " << to << endl;   // ② 最底下盘子移到目标
    hanoi(n - 1, aux, to, from);           // ③ n-1个从辅助移到目标
}

// hanoi(3, 'A', 'C', 'B') 输出 7 步移动方案

n 个盘子的移动次数是 2^n - 1。你可以验证：f(1)=1, f(n)=2f(n-1)+1，解出来就是 2^n-1。

🔍 类比：汉诺塔就像搬家公司搬一摞箱子——先把上面的搬开，搬最底下的，再把上面的搬回来。区别是搬家公司可以放地上，而汉诺塔必须遵守大小顺序。

44.3 全排列：回溯框架入门 ​

问题：输出 1~n 的所有排列。比如 n=3，输出 123, 132, 213, 231, 312, 321。

回溯思路：想象你有 n 个位置要填。填第 1 个位置时，你有 n 种选择；填第 2 个位置时，剩下 n-1 种……这本质是一棵"选择树"，每条从根到叶的路径就是一个排列。

回溯就是深度优先地遍历这棵树：

填第1位：选1      选2      选3
填第2位：选2 选3  选1 选3  选1 选2
填第3位：选3 选2  选3 选1  选2 选1
结果：  123 132  213 231  312 321
cpp
int n;
int a[20];        // 存放当前排列
bool used[20];    // used[i] 表示数字 i 是否已被选过

void dfs(int pos) {  // pos：正在填第几个位置（从1开始）
    if (pos > n) {   // 边界：n个位置都填完了
        for (int i = 1; i <= n; i++) cout << a[i] << " ";
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; i++) {   // 枚举所有可能的数字
        if (!used[i]) {              // 试：这个数字没用过？
            a[pos] = i;              // 记：放在当前位置
            used[i] = true;          // 记：标记已使用
            dfs(pos + 1);            // 递归填下一个位置
            used[i] = false;         // 撤：回溯！恢复状态
        }
    }
}

44.4 回溯的"试—记—撤"三步曲 ​

回溯的核心就是这六个字：

步骤操作代码体现
试判断这个选择可不可以做if (!used[i])
记做出选择，改变状态a[pos] = i; used[i] = true;
撤递归返回后，撤销选择used[i] = false;

🧠 类比：就像玩迷宫——你走到一个岔路口，在路口插一面旗子（记），选一条路走下去（递归）。如果走到死胡同，你就退回来，拔掉旗子（撤），换另一条路（试下一个选择）。

为什么必须"撤"？ 如果不撤销，回到上一层时状态还是脏的——比如你标记了数字 3 已被使用，但在另一条分支里数字 3 明明还没被用过。不撤 = 状态污染。

44.5 组合枚举："选与不选" ​

问题：从 1~n 中选 k 个数，输出所有组合。比如 n=4, k=2，输出 (1,2), (1,3), (1,4), (2,3), (2,4), (3,4)。

组合有两种经典写法：

写法一：选与不选（对每个数做决策）

cpp
int n, k;
vector<int> chosen;

void dfs(int x) {  // 正在考虑数字 x
    if (chosen.size() == k) {         // 边界：选够了
        for (int v : chosen) cout << v << " ";
        cout << endl;
        return;
    }
    if (x > n) return;                // 边界：数字用完了（选不够）
    
    // 分支1：选 x
    chosen.push_back(x);
    dfs(x + 1);
    chosen.pop_back();                // 撤！
    
    // 分支2：不选 x
    dfs(x + 1);
}

写法二：按顺序选（确保不重复）

cpp
void dfs(int start, int cnt) {  // 从start开始选，已经选了cnt个
    if (cnt == k) {
        for (int v : chosen) cout << v << " ";
        cout << endl;
        return;
    }
    for (int i = start; i <= n; i++) {
        chosen.push_back(i);
        dfs(i + 1, cnt + 1);         // 下一层从 i+1 开始，保证升序
        chosen.pop_back();           // 撤！
    }
}

44.6 可行性剪枝入门 ​

回溯会探索所有分支，但有些分支明显没希望，应该提前砍掉——这就是剪枝。

例：组合枚举中，如果"还没选够 k 个数，但剩下的数字不够了"，后面不管怎么选都凑不够 k 个。

cpp
void dfs(int x) {
    if (chosen.size() == k) { /* 输出 */ return; }
    if (x > n) return;
    // 剪枝：即使把后面所有数都选上，也凑不够 k 个
    if (chosen.size() + (n - x + 1) < k) return;
    
    // 选 x ... 不选 x ...
}

剪枝不会改变答案的正确性，但能大幅减少搜索量。就像在迷宫里，如果你发现前面是一堵墙，就不会继续往前走了。

🧠 剪枝是搜索优化的核心思想。后面的章节（记忆化搜索、动态规划）本质上也是"剪枝"——用更聪明的方式避免重复搜索。

✋ 动手试试 ​

试试 1：修改汉诺塔程序，统计总共移动了多少步。验证 n=4 时是否为 15 步，n=5 时是否为 31 步。

试试 2：运行全排列程序，输入 n=4，观察输出的 24 个排列。然后尝试把 used[i] = false 这行注释掉，看看会发生什么——理解"撤"的重要性。

试试 3：用组合枚举的代码，输出从 5 个数中选 3 个的所有组合。验证输出是不是 10 个（C(5,3)=10）。

⚠️ 容易犯的错 ​

错 1：回溯忘了"撤" ​

❌ used[i] = true; dfs(pos+1); // 没有 used[i] = false

✅ used[i] = true; dfs(pos+1); used[i] = false; // 三步曲完整

错 2：递归参数传错了 ​

❌ 汉诺塔中写成 hanoi(n-1, from, to, aux)，步骤①应该是移到辅助柱

✅ hanoi(n-1, from, aux, to) // from→aux，借助 to

错 3：全排列中 used 数组没有初始化 ​

❌ bool used[20]; 直接使用，值不确定

✅ bool used[20] = {false}; 全局数组自动初始化为 0

错 4：组合枚举中忘写 start 参数 ​

❌ 从 1 开始每次都从 1 选，会产生 (1,1), (1,2,1) 这种重复

✅ 每层从 start 开始，且递归时传 i+1

📝 练习 ​

基础题 ​

1. 选择题

（1）3 个盘子的汉诺塔最少需要移动多少次？
A. 3   B. 5   C. 7   D. 9

（2）4 个元素的全排列有多少种？
A. 16   B. 24   C. 12   D. 8

（3）回溯算法中，"撤"的作用是？
A. 让代码更短   B. 恢复状态，不影响其他分支   C. 减少递归深度   D. 加速运行

2. 填空题

（1）汉诺塔递推公式：T(n) = 2×T(____) + 1，其中 T(1) = ____。

（2）回溯三步曲：____ → ____ → ____。

（3）从 5 个数中选 2 个，共有 ____ 种组合。

提高题 ​

3. 编程题 — 汉诺塔步数

输入 n（1 ≤ n ≤ 20），输出移动总步数（只输出步数，不输出每步过程）。用递归实现 int countHanoi(int n)。

4. 编程题 — 全排列变形

输入一个字符串（长度不超过 8，不含重复字符），输出它的所有排列。例如输入 "abc"，输出 abc, acb, bac, bca, cab, cba。

提示：用 string s 代替 int a[]，used 按字符下标标记。

挑战题 ​

5. 编程题 — 八皇后问题（简化版）

在 8×8 的棋盘上放置 8 个皇后，要求任意两个皇后不能在同一行、同一列或同一对角线上。输出所有放置方案的总数。

提示：这是经典的回溯剪枝题！每行必须放一个皇后，所以只需确定每行的皇后在哪一列。用数组 col[9] 记录第 i 行皇后放的列号，bool 数组标记哪些列、哪些对角线已被占用。

（对角线检查技巧：左上到右下的对角线满足 row - col 为常数，右上到左下的对角线满足 row + col 为常数。）

🧠 本章小结 ​

回溯 = 递归 + 枚举所有可能 + 可行则进、不行则退

汉诺塔：经典递归
  · f(n) = 2×f(n-1) + 1 → 2^n - 1
  · 三步拆解：移上面→移底下→移上面

全排列：回溯框架
  · 枚举每个位置填什么数字
  · 用 used[] 标记，选过就跳过

组合枚举：选与不选
  · 写法一：对每个数做选/不选决策
  · 写法二：按顺序选，保证不重复

回溯三步曲：试 → 记 → 撤
  · 试：判断能不能选
  · 记：做出选择，更新状态
  · 撤：返回后恢复状态（关键！）

剪枝：提前砍掉不可能的分支
  · 不改变答案，但大幅加速

📝 配套练习 ​

共8题。回溯从全排列→组合→八皇后→迷宫→单词接龙，搜索树复杂度从n!→2^n逐级膨胀。。★核心（课堂必做） ◆拓展（课后练习） ★★★挑战（选做）

级别题号链接覆盖知识点
★ 核心luogu-P1706https://hydro.ac/p/luogu-P1706回溯三步曲、全排列
◆ 拓展luogu-P1157https://hydro.ac/p/luogu-P1157回溯组合、只往后选
◆ 拓展luogu-P1036https://hydro.ac/p/luogu-P1036回溯+质数判定
◆ 拓展luogu-P1219https://hydro.ac/p/luogu-P1219八皇后、对角线剪枝
◆ 拓展luogu-P1605https://hydro.ac/p/luogu-P1605回溯迷宫、方向数组
◆ 拓展luogu-P1019https://hydro.ac/p/luogu-P1019回溯、单词接龙
◆ 拓展luogu-P1101https://hydro.ac/p/luogu-P1101回溯、单词方阵
★★★ 挑战luogu-P1092https://hydro.ac/p/luogu-P1092虫食算、回溯+剪枝

💡 练习建议：先完成 2 道★核心题，确保掌握本章基本方法；再完成 6 道◆拓展题，覆盖不同变式和细节；★★★挑战题建议在完成拓展题后再做，涉及多知识点综合。

配套练习 ​

共8题。回溯从全排列→组合→八皇后→迷宫→单词接龙，搜索树复杂度从n!→2^n逐级膨胀。★核心（课堂必做） · ◆拓展（课后练习） · ★★★挑战（选做）

级别题号链接覆盖知识点
★ 核心luogu-P1706https://hydro.ac/p/luogu-P1706回溯三步曲、全排列
◆ 拓展luogu-P1157https://hydro.ac/p/luogu-P1157回溯组合、只往后选
◆ 拓展luogu-P1036https://hydro.ac/p/luogu-P1036回溯+质数判定
◆ 拓展luogu-P1219https://hydro.ac/p/luogu-P1219八皇后、对角线剪枝
◆ 拓展luogu-P1605https://hydro.ac/p/luogu-P1605回溯迷宫、方向数组
◆ 拓展luogu-P1019https://hydro.ac/p/luogu-P1019回溯、单词接龙
◆ 拓展luogu-P1101https://hydro.ac/p/luogu-P1101回溯、单词方阵
★★★ 挑战luogu-P1092https://hydro.ac/p/luogu-P1092虫食算、回溯+剪枝

练习建议：先在课堂完成 1 道★核心题，掌握本章基本方法；课后完成 6 道◆拓展题，覆盖不同变式和细节；★★★挑战题建议在完成拓展题后再做，涉及多知识点综合。

自查清单：

  • [ ] 我能用递归三要素推导汉诺塔的递推关系
  • [ ] 我能写出完整的全排列回溯代码
  • [ ] 我理解回溯"试—记—撤"每一步的作用
  • [ ] 我能写出"选与不选"的组合枚举代码
  • [ ] 我知道剪枝的目的是什么，能给组合枚举加剪枝
  • [ ] 我理解为什么"撤"不能省略

🚀 下章预告：回溯会重复计算很多相同的问题——斐波那契的递归版就是个"反面教材"，同一个 F(5) 被算了好几次。有没有办法让递归记住已经算过的结果，避免重复劳动？这就是第 45 章——记忆化搜索。准备迎接一个让递归"飞起来"的魔法！🧠✨