简介：这份Word文档面向ACM竞赛选手与算法学习者，系统整理了51个经典算法实例，覆盖递归、图论、动态规划、搜索与组合优化等核心领域，适合用来打牢算法基础、训练解题思维。包内仅含1个doc文件，压缩包约1.77MB，共126页，每道题均配有题目说明、解题思路、分析过程与可运行的源码，形成从理解到实现的完整闭环。内容从河内之塔、费式数列、巴斯卡三角形等入门递归题，延伸到老鼠走迷宫、骑士走棋盘、八皇后等搜索与回溯问题，再到背包问题、蒙地卡罗法求PI、Eratosthenes筛选求质数、超长整数运算等进阶主题，目录按算法逐条编排，便于按知识点检索与对照练习。目前已有413人学习，适合希望系统刷题、查漏补缺的竞赛选手与自学者参考。
1. 递归不是玄学：从河内之塔看“把问题缩小一号”为什么总能奏效
很多人第一次写递归，是在河内之塔上翻车的：明明只有三行核心代码，却怎么也说不清为什么它能把 64 个盘子搬完。更反直觉的是，这份流传很广的《ACM51个经典算法大全》里，河内之塔的解法只有一句关键判断——盘数超过两个时，把第三个以下的盘子“遮起来”，每次只处理两个盘子。遮住的部分交给递归，递归再遮住更下面一层，直到只剩一个盘子直接搬走。这个“遮起来”的动作，就是递归最底层的设计动机：把 n 规模的问题，压缩成 n-1 规模加一次确定的移动。搞懂这一点，后面八皇后、老鼠走迷宫、骑士走棋盘、背包问题，全都是同一套骨架的不同变体。这份资料把 51 个经典例子按“题目、思路、分析、源码”四段式整理，源码可运行，正好适合拿来对照着看机制，而不是背模板。
2. 递归与回溯：为什么“退回来”比“往前走”更难写对
2.1 河内之塔的移动次数为什么是 2^n - 1
先看资料里给出的递推关系。设 n 个盘子从 A 搬到 C 需要 T(n) 次，那么必须先把上面 n-1 个搬到 B（T(n-1) 次），再把最大的一个搬到 C（1 次），最后把 n-1 个从 B 搬到 C（T(n-1) 次）。于是 T(n) = 2T(n-1) + 1，展开后就是 2^n - 1。资料里顺手算了一笔账：64 个盘子、每秒搬一个，约 5850 亿年。这个数字不是噱头，它说明递归的代价是指数级的，任何“看起来优雅”的递归写法，都要先问一句规模上限在哪。
void hanoi(int n, char A, char B, char C) { if (n == 1) { printf("Move sheet %d from %c to %c\n", n, A, C); } else { hanoi(n - 1, A, C, B); // 把上面 n-1 个借 C 搬到 B printf("Move sheet %d from %c to %c\n", n, A, C); // 最大盘直接到 C hanoi(n - 1, B, A, C); // 把 B 上的 n-1 个借 A 搬到 C } }三个参数的顺序是这段代码最容易看晕的地方。A、B、C 不是固定的柱子身份，而是“源、辅助、目标”三个角色。第一次递归调用把 C 当辅助、B 当目标；第二次递归调用把 A 当辅助、C 当目标。角色在每一层递归里轮换，这正是递归能把“中间柱”这个概念自动处理掉的原因。我一般会这么理解：递归函数签名里的参数，描述的是“这一层要完成的任务”，而不是“全局的柱子”。
2.2 老鼠走迷宫：回溯的本质是“撤销选择”
资料里老鼠走迷宫（一）用 2 表示墙、1 表示路径、0 表示可走。核心函数 visit 先标记当前格为 1，然后按右、下、左、上四个方向试探，一旦 success 被置位就不再继续。关键在最后三行：如果四个方向都没走通，把当前格重新置 0，退回上一格。这就是回溯的“后悔药”——走错了要把脚印擦掉，否则后续路径会被假路径堵死。
int visit(int i, int j) { maze[i][j] = 1; // 先假设这一步在路径上 if (i == endI && j == endJ) success = 1; if (success != 1 && maze[i][j+1] == 0) visit(i, j+1); if (success != 1 && maze[i+1][j] == 0) visit(i+1, j); if (success != 1 && maze[i][j-1] == 0) visit(i, j-1); if (success != 1 && maze[i-1][j] == 0) visit(i-1, j); if (success != 1) maze[i][j] = 0; // 四个方向都不通，撤销标记 return success; }注意 success 这个全局标志的作用：它让“找到一条路径”之后的所有递归调用快速短路返回，不再继续搜索。这是求单一路径和求所有路径的分水岭。资料里老鼠走迷宫（二）把 success 判断全部去掉，改成走到出口就打印整张地图，然后继续试探，最后无条件把当前格置 0。两段代码只差几行，语义却从“找一条路”变成“枚举所有路”。很多人在这一题上踩坑，就是把两种语义混在一起写，结果要么只打印一条路径，要么路径重复。
2.3 八皇后：分支修剪为什么能把 8^8 压到可算
八皇后如果暴力枚举每一列放哪一行，是 8^8 种组合。资料里的做法是逐行放置，每放一个皇后就检查同列、右上到左下、左上到右下三条线是否被占用，用 column、rup、lup 三个数组做 O(1) 判断。一旦某行无位置可放，立刻回溯到上一行换列，这就是“分支修剪”。
void backtrack(int i) { if (i > N) { showAnswer(); } else { for (int j = 1; j <= N; j++) { if (column[j] == 1 && rup[i+j] == 1 && lup[i-j+N] == 1) { queen[i] = j; column[j] = rup[i+j] = lup[i-j+N] = 0; // 占用 backtrack(i + 1); column[j] = rup[i+j] = lup[i-j+N] = 1; // 恢复 } } } }rup 的下标是 i+j，范围 2 到 2N；lup 的下标是 i-j+N，把负数偏移到正数区间。这两个下标变换是八皇后最值得记住的细节：它把“斜线冲突”这种几何判断，变成了数组下标判断。恢复现场的三行赋值和占用时的三行完全对称，少写一行就会出现“上一行的皇后影响了下一行的判断”这种血泪 bug。
3. 分治与贪心：为什么“局部最优”有时真的能走到全局最优
3.1 骑士走棋盘：Warnsdorff 规则背后的直觉
骑士旅游如果纯递归，8x8 棋盘上分支因子是 8，深度 64，搜索空间大到不可接受。资料里明确提到 1823 年 Warnsdorff 提出的启发式：下一步优先走“再下一步可选步数最少”的那个格子。代码里先收集当前格所有可走方向，再对每个候选方向统计它的出路数 exists[l]，最后选 exists 最小的那个走。
// 对每个候选下一步，统计它还能走几步 for (l = 0; l < count; l++) { for (k = 0; k < 8; k++) { tmpi = nexti[l] + ktmove1[k]; tmpj = nextj[l] + ktmove2[k]; if (tmpi < 0 || tmpj < 0 || tmpi > 7 || tmpj > 7) continue; if (board[tmpi][tmpj] == 0) exists[l]++; } } // 选出路最少的候选 tmp = exists[0]; min = 0; for (l = 1; l < count; l++) { if (exists[l] < tmp) { tmp = exists[l]; min = l; } }这个规则的直觉是：先把“死角”走掉，把出路多的格子留到后面。它不保证一定成功，资料里也老实写了“找不到走法的机会也是有的”，但在 8x8 上成功率很高。这里的设计取舍很典型：用贪心换掉指数级搜索，牺牲完备性换效率。理解这一点，比背下八个方向的偏移数组更有价值。
3.2 背包问题：动态规划为什么能避开重复子问题
资料里背包问题用动态规划求解。核心状态是“前 i 件物品、容量 j 下的最大价值”，转移方程是取“不放第 i 件”和“放第 i 件”的较大值。和递归版相比，DP 把每个 (i, j) 状态只算一次，用二维表存下来。常见的实现思路是倒序遍历容量，把二维压成一维，避免同一件物品被重复放入。
for (int i = 0; i < n; i++) { for (int j = capacity; j >= weight[i]; j--) { // 倒序保证 dp[j-weight[i]] 还是上一轮的值 if (dp[j] < dp[j - weight[i]] + value[i]) dp[j] = dp[j - weight[i]] + value[i]; } }倒序这一行是 0-1 背包和完全背包的分界线。正序遍历会让同一件物品被多次选取，那是完全背包的语义。很多人写背包翻车，不是转移方程错，而是循环方向错。资料里把这类“同一骨架、不同方向”的题目放在一起，正好用来对照。
3.3 三色棋：一次遍历完成分类的指针技巧
三色棋要求只用原数组，把蓝、白、红排成顺序。资料里的解法维护三个指针：bFlag 指向蓝色区末尾之后，wFlag 是当前处理位置，rFlag 指向红色区起始之前。遇到白色 wFlag 前进；遇到蓝色与 bFlag 交换，两个指针都前进；遇到红色与 rFlag 交换，rFlag 后退但 wFlag 不动，因为换过来的元素还没检查。
while (wFlag <= rFlag) { if (color[wFlag] == WHITE) wFlag++; else if (color[wFlag] == BLUE) { SWAP(bFlag, wFlag); bFlag++; wFlag++; } else { while (wFlag < rFlag && color[rFlag] == RED) rFlag--; SWAP(rFlag, wFlag); rFlag--; } }红色分支里那个 while 是在跳过已经在正确位置的红色元素，避免无意义的交换。这个算法本质上是三路划分，后来被用在快速排序处理重复元素上。资料把它放在排序章节之前，其实埋了一条线：三色棋的指针划分，就是快排 partition 的雏形。
4. 排序与查找：为什么“改良”往往只是换了一个比较维度
4.1 Shell 排序：插入排序为什么怕“远距离逆序”
插入排序对基本有序的序列很快，但对逆序严重的大数组很慢，因为每次只能把元素往前挪一格。Shell 排序的做法是先按较大间隔分组做插入排序，让元素能一次跨越大距离，再逐步缩小间隔，最后间隔为 1 时序列已经接近有序。资料里把它称为“改良的插入排序”，这个定位很准确：它没有换算法骨架，只是换了一个“比较和移动的步长维度”。
常见的实现思路是间隔取 n/2、n/4 直到 1。这个序列不是最优的，但足够简单。理解 Shell 排序的关键是：间隔大于 1 时，排序结果不是最终有序，只是“间隔有序”。最后一轮间隔为 1 的插入排序才是收尾。很多人误以为前面几轮已经把数组排好，结果在间隔序列设计上出错。
4.2 快速排序的三种写法：枢轴选择为什么决定性能
资料里快速排序给了三个版本，差别主要在枢轴怎么选、划分怎么做。版本一取第一个元素做枢轴，版本二取中间元素，版本三做了更细的划分处理。枢轴选择直接决定最坏情况：如果每次取到最大或最小元素，递归深度退化成 n，复杂度从 O(n log n) 掉到 O(n^2)。取中间元素是一种低成本的缓解手段，但面对精心构造的输入仍然可能退化。
// 以中间元素为枢轴的划分示意 int pivot = arr[(left + right) / 2]; while (left <= right) { while (arr[left] < pivot) left++; while (arr[right] > pivot) right--; if (left <= right) { swap(&arr[left], &arr[right]); left++; right--; } }这段划分的好处是左右指针相向而行，交换后不会死循环。注意内层两个 while 没有等号判断，等号情况交给外层 if 处理，这样重复元素也能被均匀分到两边。快排的“玄学”性能问题，多半出在枢轴和重复元素处理上，而不是递归本身。
4.3 二分查找与插补查找：有序性怎么被“利用”得更彻底
二分查找每次取中点，把搜索区间砍半，复杂度 O(log n)。插补查找则根据目标值在区间中的比例来估算位置：mid = low + (key - arr[low]) / (arr[high] - arr[low]) * (high - low)。当数据分布均匀时，插补查找接近 O(log log n)，比二分更快；但数据分布倾斜时，它可能退化得比二分还慢。
资料里还提到费氏查找，用斐波那契数来分割区间，避免除法运算。这三种查找的共同前提都是“有序”，差别在于用哪种方式估计下一个检查点。理解它们的取舍，比记住公式更重要：二分最稳，插补在均匀分布上最快，费氏在特定硬件上省除法。
5. 避坑与排查：这 51 个例子里最容易翻车的几处
5.1 递归没有终止条件或终止条件写错
现象：程序栈溢出，或者输出明显多于预期。原因：河内之塔里把 n==1 写成 n==0，或者迷宫 visit 里没有在出口处正确置位 success。解决：先在纸上画出 n=1、n=2 的调用树，确认每一层都能收敛到终止条件；迷宫题在进入函数第一行就判断出口，而不是放在四个方向试探之后。
5.2 回溯后忘记恢复现场
现象：八皇后解的数量偏少，或者迷宫只找到一条路径后其他路径全被堵死。原因：占用数组或路径标记在递归返回后没有还原。解决：把“占用”和“恢复”写成对称的两段代码，紧挨着放，中间只夹递归调用；迷宫题在四个方向都失败后必须把当前格置 0。
5.3 数组下标越界或偏移量算错
现象：八皇后在某些行突然无解，或者骑士走棋盘走到边界外。原因：rup 的 i+j 最大到 2N，数组只开了 2N+1 却从 1 开始用；lup 的 i-j+N 在 i=1、j=N 时等于 1，边界没对齐。解决：把所有下标的最小值和最大值手算一遍，数组大小按最大值加一开；骑士题在每次计算 tmpi、tmpj 后立刻做边界检查，不要等到访问 board 时才检查。
5.4 排序算法的循环边界写反
现象：Shell 排序结果局部有序但整体不对，或者快排出现死循环。原因：Shell 排序的内层插入排序步长用了 1 而不是当前间隔；快排划分时 left 和 right 的移动条件写成了 <= 或 >=。解决：Shell 排序内层所有下标运算都用当前 gap；快排划分的内层 while 用严格小于/大于，等号交给外层交换处理。
5.5 大数运算按普通整型处理
现象：超长整数运算结果溢出或变成负数。原因：资料里的大数运算需要用数组或字符串逐位处理，直接套 int 或 long 会在超过范围后静默出错。解决：把每一位存进数组，从低位向高位处理进位和借位；输出时跳过前导零，但结果为 0 时要单独处理。
6. 从 51 个例子看算法资料该怎么读：一份可验证的取舍清单
这份资料的价值不在于“51”这个数字，而在于它把每个例子的题目、思路、分析、源码四段放在一起，形成了一条可验证的链路。读这类资料，我一般会做三件事。第一，先看思路段能不能用一句话说清算法的核心动作，比如河内之塔是“遮住下面、处理两个”，三色棋是“三个指针分区”，说不清就说明还没读懂。第二，把源码里的关键判断改成错误版本，跑一遍看现象是否符合预期，比如把八皇后的恢复现场删掉，看解的数量怎么变，这种对照比通读十遍更有效。第三，记录每个例子的规模上限和复杂度，形成一张自己的取舍表。
| 例子 | 核心机制 | 典型复杂度 | 容易翻车的点 |
|---|---|---|---|
| 河内之塔 | 递归缩小规模 | O(2^n) | 终止条件、参数角色轮换 |
| 老鼠走迷宫 | 回溯撤销 | O(4^(m*n)) 最坏 | 忘记恢复标记 |
| 八皇后 | 回溯加分支修剪 | 远小于 8^8 | 斜线下标偏移 |
| 骑士走棋盘 | 贪心启发式 | 近似线性 | 边界检查 |
| 背包问题 | 动态规划 | O(n*capacity) | 一维数组遍历方向 |
| 三色棋 | 三路划分 | O(n) | 红色分支 wFlag 不动 |
| 快速排序 | 分治加划分 | 平均 O(n log n) | 枢轴退化、重复元素 |
这张表不是让你背，而是让你在遇到新题时能快速定位“它属于哪一类骨架”。51 个例子里，递归、回溯、贪心、动态规划、排序、查找、矩阵操作这几类反复出现，真正新的东西并不多，多的是同一机制在不同场景下的变形。比如巴斯卡三角形和组合数计算是同一套递推，魔方阵和矩阵转置共享下标变换的思路，约瑟夫问题和循环链表、数组模拟都能互相印证。
还有一个容易被忽略的点：资料里的源码是 C 语言写的，很多边界处理依赖数组和全局变量。移植到其他语言时，全局状态要改成参数传递，数组越界检查要显式补上，否则原本能跑的代码换个环境就翻车。我一般会先把全局变量收进一个结构体，再把递归函数的返回值语义统一，这样调试时能少走很多弯路。
从那以后我每次读这类算法合集，都会先挑一个例子把源码改错再改对，强制走一遍“现象、原因、修复”的闭环，而不是顺着目录从头看到尾。希望这份整理也能帮到你，把 51 个例子读成几类骨架，而不是 51 个孤立的故事。
本文还有配套的精品资源，点击获取
