简介这份面向ACM竞赛与算法进阶学习者的Word文档围绕51个经典算法案例组织内容适合需要从题目、思路到代码实现完整梳理算法体系的读者。压缩包内共1个doc文件约1.77MB、126页按案例分节呈现便于集中查阅与打印研读。文档覆盖递归、回溯、图遍历、动态规划、组合优化、大数运算与数论筛法等方向包含河内之塔、八皇后、骑士走棋盘、老鼠走迷宫、背包问题、费式数列、巴斯卡三角形、生命游戏、字串核对、中序式转后序式等典型题目并配有解题分析、算法说明和可运行源码强调题目—思路—分析—源码的完整链路读者可据此理解状态设计、递归边界与复杂度优化思路。已有412人学习适合作为ACM备赛、课程实验和算法面试复习的案例库也便于按目录结构查漏补缺。1. 51 个算法的老文档为什么还值得从硬盘里翻出来题库里刷到一道题思路明明有了代码写出来却卡在边界上递归少一层、下标差一、回溯忘了恢复现场。这时候缺的不是教程是一份能对着抄、能跑通、能验证的样板。《ACM 51 个经典算法大全》就是这么一份东西——126 页 Word 文档51 个经典算法挨个拆开题目描述、解题思路、分析过程、可编译的 C 源码四样齐全从河内塔、八皇后一路排到魔方阵和费氏查找。它适合两类人刚进 ACM 训练、需要建立递归与回溯肌肉记忆的新手以及写过不少题但排序、查找、大数这些基础件一直是黑匣子的老手。下面按我自己拆这份文档的顺序讲怎么分类、怎么跑通、怎么改成能测试的骨架、哪里最容易翻车。2. 把 51 个题目拆成四条主线先练哪条、后练哪条拿到一份 126 页的合集最没效率的读法是从第一页线性读到最后一页。第 1 题是递归第 13 题突然跳到背包第 33 题又回到排序中间还夹着概率模拟和魔方阵构造。按目录顺序硬读等于每三页换一次脑子里的模型。我的做法是先看目录把 51 个题目按「解题范式」而不是「页码」重新分组分成四条主线然后一条一条推进。分组的依据很简单同一个范式下的题目递归函数的结构、状态的定义、边界条件的写法高度相似练完一题等于练完一类。跨范式跳着练每次都要重建思维模型投入产出比很低。主线文档内序号题目数核心范式建议投入递归与回溯1、5、6、7、8、12、22、23、27、29、3011函数自调用、状态恢复、剪枝3 到 4 天排序与查找33 至 4513分治、增量、比较与散列思想2 到 3 天组合枚举与数论2、3、13、15、18、19、20、26、28、31、3211递推、筛法、DP、位运算3 天数值、大数与矩阵14、16、17、21、24、25、46 至 5112数组模拟、坐标变换、随机采样2 天这张表不是让你按顺序打卡而是让你知道每一段投入换回来的是什么。递归那条线换回来的是「能写对回溯」排序查找那条线换回来的是「能手写不虚」后面两条更多是「见过、知道边界在哪」。2.1 递归回溯主线四个题目构成一条完整的难度台阶这条线里最值得按顺序啃的是第 1、5、8、7 题。河内塔是单函数双递归的最小模型递归体只有三行但已经包含了「把大问题拆成同类子问题」的全部要素。老鼠走迷宫一把递归搬到二维网格上新增的是方向数组和「走不通要退回来」的现场恢复。八皇后在第 5 题的基础上加了约束剪枝用三个标记数组把「同列、同对角线」的判断降到 O(1)。骑士走棋盘再往上加一层启发式——纯回溯在 8×8 上会跑到天荒地老文档用的是「优先走下一步出路最少的位置」这种贪心排序把搜索空间压下来。这四题的递进关系很清晰但文档是平铺的不点破。我一般会要求自己每跑通一题在纸上写一句话回答「这个递归函数在做什么」写不出来说明只是抄了一遍。题目递归形态剪枝 / 优化手段主要卡点河内塔单层双递归无复杂度本身就是 2^n-1柱子的角色在递归中要交换迷宫一单层四分支找到即停success 标志回溯时要把走过的格子清回 0迷宫二单层四分支不剪枝走到出口就打印打印循环的边界容易写死八皇后单层 N 分支列 两条对角线三个标记数组递归返回前必须恢复三个标记骑士走棋盘迭代 贪心下一步出路数最少优先8 个方向的坐标增量要成对写对推进时有一个可执行的小技巧先把每个题目的解法手算一遍不用电脑。河内塔 n3 手写出 7 步八皇后手推出前两个解的位置骑士走棋盘先接受「可能找不到解」这个前提。手算过一遍再去读源码能立刻看出哪一行对应你手算的哪一步比直接读代码快得多。2.2 排序与查找主线13 个排序里只有 4 个值得手写文档从第 33 题到第 41 题排了 9 个排序第 42 到 45 题排了 4 个查找。第一次看会以为要全部背下来实际上按使用频率分三档就够。第一档必须能手写不出错快速排序文档给了三个版本重点看分区那段的指针移动、合并排序、堆排序文档第 36 题标题写的是「改良的选择排序」本体是堆的调整、基数排序。第二档知道原理和适用条件即可Shell 排序的增量序列、Shaker 排序的双向扫描、选择/插入/气泡三个基础款的稳定性差异。第三档基本只用来看代码风格三个快排版本之间的差异主要在主元选取和小区间处理读懂一版就够。查找那四题的价值在于「适用条件」而不是代码。循序查找加卫兵是为了省掉每次循环的边界判断代价是要多开一个位置。二分查找的前提是有序插补查找在数据分布均匀时能把比较次数压到接近 log log n费氏查找则是用斐波那契数代替中点划分避免除法。文档里这几种写法的循环条件各不相同抄的时候特别容易把low high和low high混掉。一个可执行的验证办法写一个 10 万随机整数的数组把 9 个排序各跑一遍输出结果做逐元素比对全部一致才算过。这一步能抓出绝大多数下标错误比肉眼检查有效。2.3 组合枚举、大数与矩阵坑集中在边界和下标第 27 到 32 题是一串组合枚举排列组合、格雷码、产生可能的集合、m 元素集合的 n 元素子集、数字拆解、得分排行。这一组代码短但边界条件密集。格雷码用i ^ (i 1)生成一行就完事可一旦 n 超过 30 就要换 64 位。子集枚举用位掩码1 n在 n31 时是负数这个坑不跑一次根本发现不了。第 16、17 题的大数运算和第 46 到 51 题的矩阵系列是另一类。大数用数组模拟竖式核心是进位处理加法只可能进 1乘法进位可能很大两个的写法不能照抄。矩阵那几题稀疏矩阵、多维转一维、上三角下三角对称矩阵、三种魔方阵考的是坐标映射i * cols j这个公式谁都会写但对称矩阵压缩存储时的下标公式有四五种写法选错一个就整体偏移。这几组的正确打开方式是先把参数范围写死在代码里逐个放大看从哪个值开始出错。比如子集枚举从 n10 试到 n32大数加法从 5 位试到 500 位。出错的那个点就是你理解不到位的地方。2.4 读文档的顺序先跑通再回头看分析文档每一题的结构是「说明 → 解法 → 源码」。很多人习惯按这个顺序读读完说明读解法读完解法再读源码结果读到源码时已经忘了前面在讲什么。我自己的顺序是反的先扫一眼说明知道题目要干什么直接跳到源码编译跑一遍看输出长什么样然后再回头读解法那一段。这时候解法里的每一句话都能对上刚才看到的输出理解成本低很多。特别是回溯类的题目先看到「92 个解」这个具体数字再去读剪枝逻辑会顺畅得多。3. 跑通第一个例子编译、目录约定与递归验证文档里的代码是纯 C没有依赖理论上复制粘贴就能编译。实际操作时会遇到三类问题编译器默认标准不同导致的隐式声明、代码里写死的数组维度、以及输出格式对不上没法做自动比对。这一章先把环境和跑通流程固定下来。3.1 目录约定与编译参数我习惯给这类合集单独开一个工程目录源码、可执行文件、输出分开避免几十个a.out混在一起。# 建三个目录src 存源码bin 存可执行文件out 存运行输出 mkdir -p acm51/{src,bin,out} cd acm51 # 把文档第 1 题的源码存成 src/01_hanoi.c 之后 gcc -stdc99 -Wall -Wextra -O2 src/01_hanoi.c -o bin/hanoi # 用输入重定向跑避免每次手动敲 ./bin/hanoi 3 | tee out/01_hanoi.txt三个编译参数各有用途。-stdc99是因为文档里不少代码在for循环内部声明变量比如for(int i 0; ...)这是 C99 特性用默认的 gnu17 也能过但换到一些老环境就会报错固定下来省事。-Wall -Wextra是关键文档里有几题的函数定义写在main之后又没有前置声明这两个开关会把隐式声明警告打出来比运行时的段错误好查一百倍。-O2不是必须但骑士走棋盘、八皇后这类搜索题开了优化能快出数倍。后面所有题目都套这个模板只改文件名。跑之前先看一眼这题有没有从标准输入读数河内塔、骑士走棋盘有有的就用喂参数没有的直接跑。3.2 河内塔给递归加一个计数器文档原版的河内塔只打印每一步跑完看不出总共搬了几次也就没法验证2^n - 1这个结论。加一个全局计数器改十行就够。#include stdio.h static long long g_move 0; /* 全局计数器统计实际搬盘次数 */ void hanoi(int n, char from, char aux, char to) { if (n 1) { /* 只剩一个盘子直接搬 */ g_move; printf(Move sheet %d from %c to %c\n, n, from, to); return; } hanoi(n - 1, from, to, aux); /* 上面 n-1 个先挪到辅助柱 */ g_move; printf(Move sheet %d from %c to %c\n, n, from, to); hanoi(n - 1, aux, from, to); /* 再从辅助柱挪到目标柱 */ } int main(void) { int n; if (scanf(%d, n) ! 1 || n 1 || n 25) { /* 输入校验防止递归过深 */ fprintf(stderr, n must be in [1, 25]\n); return 1; } hanoi(n, A, B, C); printf(total %lld, expect %lld\n, g_move, (1LL n) - 1); return 0; }逻辑上就三件事。第一递归的终止条件是n 1此时直接把盘子从from搬到to不需要辅助柱。第二n 1时先把上面n-1个整体挪到aux这一步里to变成了辅助角色所以调用参数是hanoi(n-1, from, to, aux)——三个柱子名字没变但语义在每次递归里轮换这是这题唯一容易绕晕的地方。第三把最大的那个盘子搬到to再把n-1个从aux搬到to。参数上要注意(1LL n)里的LL。如果不加1 30就已经是负数了n 稍大一点期望值就是错的你会以为是递归写错了实际是类型溢出。上限卡在 25 是一个折中2^25是三千三百万次打印再大就不是验证而是折磨硬盘了。跑n 10输出末行应该是total 1023, expect 1023。对不上就说明计数器加的位置错了——要么在递归里重复加要么漏了中间那一步。3.3 八皇后三个标记数组到底在标记什么八皇后是这条线上最值得反复写的一题因为它的剪枝结构在后面的迷宫、数独、棋盘覆盖里会反复出现。文档原版用三个全局数组column、rup、lup初值全设成 1 表示「可用」放置时设 0 表示「被占」。#include stdio.h #define N 8 static int column[N 1]; /* 列占用标记下标 1..N */ static int rup[2 * N 1]; /* 右上到左下对角线下标 ij范围 2..2N */ static int lup[2 * N 1]; /* 左上到右下对角线下标 i-jN范围 1..2N-1 */ static int queen[N 1]; /* queen[row] col记录每行皇后所在列 */ static int g_count 0; static void backtrack(int row) { if (row N) { /* 八行都放完了得到一个解 */ g_count; return; } for (int c 1; c N; c) { if (column[c] rup[row c] lup[row - c N]) { column[c] rup[row c] lup[row - c N] 0; /* 占位 */ queen[row] c; backtrack(row 1); column[c] rup[row c] lup[row - c N] 1; /* 恢复现场 */ } } } int main(void) { for (int i 1; i N; i) column[i] 1; for (int i 1; i 2 * N; i) rup[i] lup[i] 1; backtrack(1); printf(solutions %d\n, g_count); return 0; }三个数组的下标设计是这题的核心。列好理解column[c]直接对应第 c 列。两条对角线需要做坐标变换同一右上到左下方向上的格子row col是常数最小值 211最大值 2N所以数组开到2N1。同一左上到右下方向上的格子row - col是常数但会出现负数加个 N 平移成1..2N-1数组同样开到2N1就够。backtrack的入口参数是行号而不是格子坐标这是一个隐含的剪枝——每行只放一个皇后所以行冲突根本不用判断循环直接从第 1 行推到第 8 行。这一点文档里没明说但它是这个写法比「逐格枚举」快一个数量级的原因。跑出来应该是 92。如果跑出 0八成是三个数组的初值设成了 0如果跑出 4 或 8 之类的数多半是恢复现场那三行漏了其中一行导致后面的分支被前面残留的标记挡住。提示把N改成 4、5、6 分别跑一遍已知解数是 2、10、4。这三个小规模数据是验证剪枝写对没写对的最快方式比一上来就跑 8 皇后好定位。4. 把示例代码改成可测试的工程结构文档里的代码都是「一个文件、一个main、直接打印」的形态适合看不适合验证。改了参数对不对、剪枝有没有漏、边界有没有越界全靠肉眼盯输出。把 51 个题目逐个改造成能跑断言的形态工作量太大但挑十来个核心题目改一遍后面的题照着套就行。4.1 剥掉 main让求解函数返回结果而不是打印第一个改造动作是把「打印」换成「返回」。以八皇后为例原版在row N时调用showAnswer()打印棋盘改成返回计数函数签名就从void变成long long递归里的累加也顺理成章。#include stdio.h #define N 8 static int col[N 1], d1[2 * N 1], d2[2 * N 1]; /* 返回从第 row 行开始能摆出的完整解数 */ static long long dfs(int row) { if (row N) return 1; /* 走到第 N1 行说明前 N 行都摆好了 */ long long total 0; for (int c 1; c N; c) { if (!col[c] !d1[row c] !d2[row - c N]) { col[c] d1[row c] d2[row - c N] 1; total dfs(row 1); /* 子问题的解数累加回来 */ col[c] d1[row c] d2[row - c N] 0; } } return total; } int main(void) { long long got dfs(1); printf(N%d solutions%lld\n, N, got); if (got ! 92) { /* 已知解数做回归断言 */ fprintf(stderr, regression failed: expect 92\n); return 1; } return 0; }改造的关键在第 8 行if (row N) return 1;。原来这里是「打印并计数」现在变成「返回 1 表示找到一条完整路径」父层把这个 1 累加进total一路传回根节点。这个「返回可行解数量」的模式可以直接套到迷宫返回路径条数、子集枚举返回子集个数、数字拆解返回拆分数上是这类回溯题最通用的骨架。改造后的直接收益是可以在main里写断言。断言比打印靠谱因为打印你需要人眼比对断言是程序自己比对跑完退出码非 0 就说明回归了。我一般会把已知结果整理成一张小表放在测试脚本里。题目断言用的已知值说明八皇后 N892经典解数改剪枝逻辑后必须仍然成立八皇后 N64小规模方便打断点河内塔 n101023等于 2^10 - 1筛法 n100000078498一百万以内素数个数约瑟夫环 n41, k331经典设定下的幸存位置注意这些已知值只能在「题目定义完全一致」的前提下用。比如约瑟夫环有从 0 编号和从 1 编号两种约定差一个偏移断言就会误报。4.2 大数加法进位只可能进 1别照抄乘法的写法第 16 题的超长整数运算文档给了加减乘除一整套。加法是最短的但也是最容易被写错的因为很多人会把乘法的进位逻辑直接搬过来。#include stdio.h #include string.h #define MAXLEN 1000 /* 支持最多 1000 位十进制数 */ /* 低位在前存进 buf模拟竖式加法out 必须以 \0 结尾 */ static void bigadd(const char *a, const char *b, char *out) { int la (int)strlen(a), lb (int)strlen(b); int buf[MAXLEN 2] {0}; /* 多开两位给最高位进位留空间 */ int len la lb ? la : lb; for (int i 0; i len; i) { int da (i la) ? a[la - 1 - i] - 0 : 0; /* 从个位开始取 */ int db (i lb) ? b[lb - 1 - i] - 0 : 0; buf[i] da db; if (buf[i] 10) { /* 加法进位只可能是 1 */ buf[i] - 10; buf[i 1] 1; } } int top len; while (top 0 buf[top] 0) top--; /* 跳过前导零但至少保留一位 */ int k 0; for (int i top; i 0; i--) out[k] (char)(0 buf[i]); out[k] \0; } int main(void) { char out[MAXLEN 2]; bigadd(99999999999999999999, 1, out); /* 20 个 9 加 1专门测连续进位 */ printf(%s\n, out); return 0; }buf开到MAXLEN 2而不是MAXLEN是因为两个 1000 位数相加结果最多 1001 位最高位的进位要有个地方落。很多人图省事开成MAXLEN然后在buf[i 1] 1那一行踩到越界编译器不报错跑起来把相邻内存改了输出看着还挺正常这种属于典型的血泪经验。top的循环条件写成top 0 buf[top] 0top 0这个限制是为了保住最低位——结果是 0 的时候不能把所有位都跳掉否则输出空字符串。这个细节在减法里同样存在文档的减法代码里就有类似处理。乘法不能套这段。乘法的中间累加值可能远大于 10进位可能是几十必须用「先累加再统一进位」的写法不能在循环里就地取模。这两段代码形态差别很大混用是这份文档里最容易犯的错。4.3 筛法与插补查找参数范围决定了代码能不能跑第 15 题的埃氏筛法文档写法是从 2 开始把每个素数的倍数标记掉。改造成能接受命令行参数的版本后有几个参数必须想清楚。#include stdio.h #include stdlib.h int main(int argc, char **argv) { long n (argc 1) ? atol(argv[1]) : 1000000L; /* 上限默认一百万 */ char *comp calloc((size_t)n 1, 1); /* comp[i]1 表示 i 是合数 */ if (!comp) { perror(calloc); return 1; } long cnt 0; for (long i 2; i n; i) { if (comp[i]) continue; /* 已被标记跳过 */ cnt; if (i * i n) /* 先判越界再筛防止 i*i 溢出 */ for (long j i * i; j n; j i) comp[j] 1; } printf(primes %ld : %ld\n, n, cnt); free(comp); return 0; }三个参数点。calloc而不是malloc因为需要初始化为 0malloc拿到的是脏内存标记会乱。char而不是int存标记一百万规模下省三倍内存缓存命中率也高。内层循环从i * i开始而不是2 * i因为小于i * i的合数一定已经被更小的素数筛过了这一步能省掉将近一半的标记操作。if (i * i n)这个判断是防溢出的。i是long在 64 位平台上i * i到 30 亿才溢出看起来安全但如果哪天把long改成int比如在嵌入式环境i到 46341 时i * i就翻负了内层循环直接不执行结果会漏掉一大批合数。这种错误在小数据上测不出来必须跑到 n 大于 10 亿才暴露属于典型的「上线才炸」。第 44 题的插补查找有个类似的前置条件数据必须近似均匀分布而且不能有重复值否则mid的计算会退化。文档里的mid low (high - low) * (key - a[low]) / (a[high] - a[low])这行分母是a[high] - a[low]如果首尾元素相等就直接除零。实际用的时候我会在前面加一句if (a[high] a[low]) return -1;。5. 踩坑排查51 个例子里最容易翻车的五处这份文档的代码整体质量不错但毕竟是逐题整理的版本之间风格不统一有几处明显的坑。下面五条都是我自己或者身边的人实际踩过的按「现象 → 原因 → 解决」记下来。5.1 迷宫二只打印左上角一小块现象把第 6 题的源码编译跑通屏幕上确实出现了路径但棋盘只画了左上角 7×7 的一小块右边和下边是空的看着像被裁掉了。原因这一题的maze数组定义成了maze[9][9]入口在(1,1)出口在(7,7)但main里打印迷宫的循环条件写的是i 7和j 7。这个 7 是从第 5 题的 7×7 迷宫抄过来的改成 9×9 的时候只改了数组没改循环。解决把所有硬编码的 7 换成宏或者sizeof推导。#define ROW 9然后循环写i ROW改维度时只改一处。更稳的写法是sizeof(maze) / sizeof(maze[0])但要注意传参退化成指针的情况这里maze是全局数组不会退化可以直接用。5.2 骑士走棋盘编译报隐式声明现象用-stdc99 -Wall编译第 7 题main里调用travel那一行报implicit declaration of function travel链接时直接失败提示 undefined reference。原因travel函数的定义写在main之后前面没有原型声明。C89 允许隐式声明默认返回 intC99 起这个行为被移除编译器直接报错。文档里的代码大概是按 C89 的习惯写的。解决在main前面加一行int travel(int x, int y);。另一种办法是编译时加-stdgnu89把标准退回去但这会关掉一堆现代检查不推荐。加原型是最小改动也是后面所有题目通用的做法——凡是被调函数写在后面一律先声明。5.3 费氏数列跑到第 47 项变成负数现象第 2 题的代码里#define N 20输出正常。改大到 50 想多看几项第 47 项开始出现负数后面越来越离谱。原因int在 32 位下最大 2147483647斐波那契第 46 项是 1836311903第 47 项就溢出成负数了。这是整数溢出不是算法错。解决把数组类型改成long longN可以安全开到 92第 93 项开始超出 64 位有符号范围。如果要更大就得上第 16 题那套大数数组。这里有个容易忽略的点printf的格式符也要跟着从%d改成%lld只改类型不改格式符输出依然是错的而且是那种「看着像个正常数字」的错。5.4 回溯漏了恢复现场解数少一大截现象把八皇后的三个标记数组从「1 表示可用」改成「1 表示占用」改完之后跑出来只有 4 个解而不是 92 个。原因语义反了之后backtrack里的三行赋值也要跟着反过来——原来放皇后是设 0恢复是设 1现在放皇后是设 1恢复是设 0。只改了初始化没改这两处导致递归返回后标记一直停在「占用」状态后面的分支全被挡住。解决把「占位」和「恢复」两行写成紧挨着的一对中间只隔一个递归调用视觉上形成配对改的时候不容易只改一半。更彻底的办法是把这个模式抽成两个宏MARK(row, c)和UNMARK(row, c)两边永远同时改。5.5 快速排序遇到有序输入退化成平方级现象第 37 题的快速排序测试数据随机生成时 10 万个元素零点几秒跑完换成已经排好序的数组跑了十几秒还没出结果。原因文档里的快排固定取第一个元素做主元。对已经有序的输入每次划分都退化成「一边 1 个、一边 n-1 个」递归深度变成 n复杂度从 O(n log n) 掉到 O(n²)。10 万个元素就是 100 亿次比较的量级。解决主元改成三数取中取首、中、尾三个位置的中间值作为主元同时在划分时把等于主元的元素均匀分到两边。改完之后有序输入和随机输入的性能基本持平。这个改动只有七八行但它是快排能不能用于真实数据的分水岭文档里三个快排版本都没有处理这一点。6. 进阶用法把 51 个例子做成自己的模板库走到这一步51 个题目大概跑通了七成剩下的多半是矩阵和概率类的不影响主线。接下来要做的不是继续刷而是把它们沉淀下来。我的做法是建一个templates/目录只放五类骨架回溯带状态恢复、二分三种边界写法、大数加减乘各一个、筛法、并查集。每类一个文件函数签名固定参数用宏或者结构体传不写main靠单独的test_*.c去调。这套东西的价值在于「下次不用重新想」。真到了比赛或者面试现场回溯的框架是肌肉记忆写的时候只需要填状态定义和剪枝条件剩下的骨架直接从模板里抄。文档给的是 51 个完整例子模板库给的是 5 个可以拼装的最小单元后者复用率高得多。再补一个验收清单每次改完模板跑一遍检查项判定方式常见失败原因回溯解数正确对照第 4 章那张已知值表恢复现场漏一行边界输入不崩n 0、n 1、n 上限 各跑一次循环条件写成或溢出可控用-fsanitizeundefined编译跑一遍中间结果用 int 存内存不越界用-fsanitizeaddress编译跑一遍数组开小一位结果可复现固定随机种子跑两次比对输出用了time(NULL)做种子-fsanitizeundefined和-fsanitizeaddress这两个编译选项我应该早点用。当年照着文档抄筛法int数组开成n而不是n 1comp[n]那一格越界写了一个字节程序跑了半小时才崩中间输出全是正常的。后来加了 ASan编译完第一次运行就把越界位置精确打出来了。从那以后我每次把文档里的代码改成自己的版本都强制走一遍两个 sanitizer 再合并进模板库哪怕它看起来「只是改了个变量名」。希望帮到你。本文还有配套的精品资源点击获取
简介这份面向ACM竞赛与算法进阶学习者的Word文档围绕51个经典算法案例组织内容适合需要从题目、思路到代码实现完整梳理算法体系的读者。压缩包内共1个doc文件约1.77MB、126页按案例分节呈现便于集中查阅与打印研读。文档覆盖递归、回溯、图遍历、动态规划、组合优化、大数运算与数论筛法等方向包含河内之塔、八皇后、骑士走棋盘、老鼠走迷宫、背包问题、费式数列、巴斯卡三角形、生命游戏、字串核对、中序式转后序式等典型题目并配有解题分析、算法说明和可运行源码强调题目—思路—分析—源码的完整链路读者可据此理解状态设计、递归边界与复杂度优化思路。已有412人学习适合作为ACM备赛、课程实验和算法面试复习的案例库也便于按目录结构查漏补缺。1. 51 个算法的老文档为什么还值得从硬盘里翻出来题库里刷到一道题思路明明有了代码写出来却卡在边界上递归少一层、下标差一、回溯忘了恢复现场。这时候缺的不是教程是一份能对着抄、能跑通、能验证的样板。《ACM 51 个经典算法大全》就是这么一份东西——126 页 Word 文档51 个经典算法挨个拆开题目描述、解题思路、分析过程、可编译的 C 源码四样齐全从河内塔、八皇后一路排到魔方阵和费氏查找。它适合两类人刚进 ACM 训练、需要建立递归与回溯肌肉记忆的新手以及写过不少题但排序、查找、大数这些基础件一直是黑匣子的老手。下面按我自己拆这份文档的顺序讲怎么分类、怎么跑通、怎么改成能测试的骨架、哪里最容易翻车。2. 把 51 个题目拆成四条主线先练哪条、后练哪条拿到一份 126 页的合集最没效率的读法是从第一页线性读到最后一页。第 1 题是递归第 13 题突然跳到背包第 33 题又回到排序中间还夹着概率模拟和魔方阵构造。按目录顺序硬读等于每三页换一次脑子里的模型。我的做法是先看目录把 51 个题目按「解题范式」而不是「页码」重新分组分成四条主线然后一条一条推进。分组的依据很简单同一个范式下的题目递归函数的结构、状态的定义、边界条件的写法高度相似练完一题等于练完一类。跨范式跳着练每次都要重建思维模型投入产出比很低。主线文档内序号题目数核心范式建议投入递归与回溯1、5、6、7、8、12、22、23、27、29、3011函数自调用、状态恢复、剪枝3 到 4 天排序与查找33 至 4513分治、增量、比较与散列思想2 到 3 天组合枚举与数论2、3、13、15、18、19、20、26、28、31、3211递推、筛法、DP、位运算3 天数值、大数与矩阵14、16、17、21、24、25、46 至 5112数组模拟、坐标变换、随机采样2 天这张表不是让你按顺序打卡而是让你知道每一段投入换回来的是什么。递归那条线换回来的是「能写对回溯」排序查找那条线换回来的是「能手写不虚」后面两条更多是「见过、知道边界在哪」。2.1 递归回溯主线四个题目构成一条完整的难度台阶这条线里最值得按顺序啃的是第 1、5、8、7 题。河内塔是单函数双递归的最小模型递归体只有三行但已经包含了「把大问题拆成同类子问题」的全部要素。老鼠走迷宫一把递归搬到二维网格上新增的是方向数组和「走不通要退回来」的现场恢复。八皇后在第 5 题的基础上加了约束剪枝用三个标记数组把「同列、同对角线」的判断降到 O(1)。骑士走棋盘再往上加一层启发式——纯回溯在 8×8 上会跑到天荒地老文档用的是「优先走下一步出路最少的位置」这种贪心排序把搜索空间压下来。这四题的递进关系很清晰但文档是平铺的不点破。我一般会要求自己每跑通一题在纸上写一句话回答「这个递归函数在做什么」写不出来说明只是抄了一遍。题目递归形态剪枝 / 优化手段主要卡点河内塔单层双递归无复杂度本身就是 2^n-1柱子的角色在递归中要交换迷宫一单层四分支找到即停success 标志回溯时要把走过的格子清回 0迷宫二单层四分支不剪枝走到出口就打印打印循环的边界容易写死八皇后单层 N 分支列 两条对角线三个标记数组递归返回前必须恢复三个标记骑士走棋盘迭代 贪心下一步出路数最少优先8 个方向的坐标增量要成对写对推进时有一个可执行的小技巧先把每个题目的解法手算一遍不用电脑。河内塔 n3 手写出 7 步八皇后手推出前两个解的位置骑士走棋盘先接受「可能找不到解」这个前提。手算过一遍再去读源码能立刻看出哪一行对应你手算的哪一步比直接读代码快得多。2.2 排序与查找主线13 个排序里只有 4 个值得手写文档从第 33 题到第 41 题排了 9 个排序第 42 到 45 题排了 4 个查找。第一次看会以为要全部背下来实际上按使用频率分三档就够。第一档必须能手写不出错快速排序文档给了三个版本重点看分区那段的指针移动、合并排序、堆排序文档第 36 题标题写的是「改良的选择排序」本体是堆的调整、基数排序。第二档知道原理和适用条件即可Shell 排序的增量序列、Shaker 排序的双向扫描、选择/插入/气泡三个基础款的稳定性差异。第三档基本只用来看代码风格三个快排版本之间的差异主要在主元选取和小区间处理读懂一版就够。查找那四题的价值在于「适用条件」而不是代码。循序查找加卫兵是为了省掉每次循环的边界判断代价是要多开一个位置。二分查找的前提是有序插补查找在数据分布均匀时能把比较次数压到接近 log log n费氏查找则是用斐波那契数代替中点划分避免除法。文档里这几种写法的循环条件各不相同抄的时候特别容易把low high和low high混掉。一个可执行的验证办法写一个 10 万随机整数的数组把 9 个排序各跑一遍输出结果做逐元素比对全部一致才算过。这一步能抓出绝大多数下标错误比肉眼检查有效。2.3 组合枚举、大数与矩阵坑集中在边界和下标第 27 到 32 题是一串组合枚举排列组合、格雷码、产生可能的集合、m 元素集合的 n 元素子集、数字拆解、得分排行。这一组代码短但边界条件密集。格雷码用i ^ (i 1)生成一行就完事可一旦 n 超过 30 就要换 64 位。子集枚举用位掩码1 n在 n31 时是负数这个坑不跑一次根本发现不了。第 16、17 题的大数运算和第 46 到 51 题的矩阵系列是另一类。大数用数组模拟竖式核心是进位处理加法只可能进 1乘法进位可能很大两个的写法不能照抄。矩阵那几题稀疏矩阵、多维转一维、上三角下三角对称矩阵、三种魔方阵考的是坐标映射i * cols j这个公式谁都会写但对称矩阵压缩存储时的下标公式有四五种写法选错一个就整体偏移。这几组的正确打开方式是先把参数范围写死在代码里逐个放大看从哪个值开始出错。比如子集枚举从 n10 试到 n32大数加法从 5 位试到 500 位。出错的那个点就是你理解不到位的地方。2.4 读文档的顺序先跑通再回头看分析文档每一题的结构是「说明 → 解法 → 源码」。很多人习惯按这个顺序读读完说明读解法读完解法再读源码结果读到源码时已经忘了前面在讲什么。我自己的顺序是反的先扫一眼说明知道题目要干什么直接跳到源码编译跑一遍看输出长什么样然后再回头读解法那一段。这时候解法里的每一句话都能对上刚才看到的输出理解成本低很多。特别是回溯类的题目先看到「92 个解」这个具体数字再去读剪枝逻辑会顺畅得多。3. 跑通第一个例子编译、目录约定与递归验证文档里的代码是纯 C没有依赖理论上复制粘贴就能编译。实际操作时会遇到三类问题编译器默认标准不同导致的隐式声明、代码里写死的数组维度、以及输出格式对不上没法做自动比对。这一章先把环境和跑通流程固定下来。3.1 目录约定与编译参数我习惯给这类合集单独开一个工程目录源码、可执行文件、输出分开避免几十个a.out混在一起。# 建三个目录src 存源码bin 存可执行文件out 存运行输出 mkdir -p acm51/{src,bin,out} cd acm51 # 把文档第 1 题的源码存成 src/01_hanoi.c 之后 gcc -stdc99 -Wall -Wextra -O2 src/01_hanoi.c -o bin/hanoi # 用输入重定向跑避免每次手动敲 ./bin/hanoi 3 | tee out/01_hanoi.txt三个编译参数各有用途。-stdc99是因为文档里不少代码在for循环内部声明变量比如for(int i 0; ...)这是 C99 特性用默认的 gnu17 也能过但换到一些老环境就会报错固定下来省事。-Wall -Wextra是关键文档里有几题的函数定义写在main之后又没有前置声明这两个开关会把隐式声明警告打出来比运行时的段错误好查一百倍。-O2不是必须但骑士走棋盘、八皇后这类搜索题开了优化能快出数倍。后面所有题目都套这个模板只改文件名。跑之前先看一眼这题有没有从标准输入读数河内塔、骑士走棋盘有有的就用喂参数没有的直接跑。3.2 河内塔给递归加一个计数器文档原版的河内塔只打印每一步跑完看不出总共搬了几次也就没法验证2^n - 1这个结论。加一个全局计数器改十行就够。#include stdio.h static long long g_move 0; /* 全局计数器统计实际搬盘次数 */ void hanoi(int n, char from, char aux, char to) { if (n 1) { /* 只剩一个盘子直接搬 */ g_move; printf(Move sheet %d from %c to %c\n, n, from, to); return; } hanoi(n - 1, from, to, aux); /* 上面 n-1 个先挪到辅助柱 */ g_move; printf(Move sheet %d from %c to %c\n, n, from, to); hanoi(n - 1, aux, from, to); /* 再从辅助柱挪到目标柱 */ } int main(void) { int n; if (scanf(%d, n) ! 1 || n 1 || n 25) { /* 输入校验防止递归过深 */ fprintf(stderr, n must be in [1, 25]\n); return 1; } hanoi(n, A, B, C); printf(total %lld, expect %lld\n, g_move, (1LL n) - 1); return 0; }逻辑上就三件事。第一递归的终止条件是n 1此时直接把盘子从from搬到to不需要辅助柱。第二n 1时先把上面n-1个整体挪到aux这一步里to变成了辅助角色所以调用参数是hanoi(n-1, from, to, aux)——三个柱子名字没变但语义在每次递归里轮换这是这题唯一容易绕晕的地方。第三把最大的那个盘子搬到to再把n-1个从aux搬到to。参数上要注意(1LL n)里的LL。如果不加1 30就已经是负数了n 稍大一点期望值就是错的你会以为是递归写错了实际是类型溢出。上限卡在 25 是一个折中2^25是三千三百万次打印再大就不是验证而是折磨硬盘了。跑n 10输出末行应该是total 1023, expect 1023。对不上就说明计数器加的位置错了——要么在递归里重复加要么漏了中间那一步。3.3 八皇后三个标记数组到底在标记什么八皇后是这条线上最值得反复写的一题因为它的剪枝结构在后面的迷宫、数独、棋盘覆盖里会反复出现。文档原版用三个全局数组column、rup、lup初值全设成 1 表示「可用」放置时设 0 表示「被占」。#include stdio.h #define N 8 static int column[N 1]; /* 列占用标记下标 1..N */ static int rup[2 * N 1]; /* 右上到左下对角线下标 ij范围 2..2N */ static int lup[2 * N 1]; /* 左上到右下对角线下标 i-jN范围 1..2N-1 */ static int queen[N 1]; /* queen[row] col记录每行皇后所在列 */ static int g_count 0; static void backtrack(int row) { if (row N) { /* 八行都放完了得到一个解 */ g_count; return; } for (int c 1; c N; c) { if (column[c] rup[row c] lup[row - c N]) { column[c] rup[row c] lup[row - c N] 0; /* 占位 */ queen[row] c; backtrack(row 1); column[c] rup[row c] lup[row - c N] 1; /* 恢复现场 */ } } } int main(void) { for (int i 1; i N; i) column[i] 1; for (int i 1; i 2 * N; i) rup[i] lup[i] 1; backtrack(1); printf(solutions %d\n, g_count); return 0; }三个数组的下标设计是这题的核心。列好理解column[c]直接对应第 c 列。两条对角线需要做坐标变换同一右上到左下方向上的格子row col是常数最小值 211最大值 2N所以数组开到2N1。同一左上到右下方向上的格子row - col是常数但会出现负数加个 N 平移成1..2N-1数组同样开到2N1就够。backtrack的入口参数是行号而不是格子坐标这是一个隐含的剪枝——每行只放一个皇后所以行冲突根本不用判断循环直接从第 1 行推到第 8 行。这一点文档里没明说但它是这个写法比「逐格枚举」快一个数量级的原因。跑出来应该是 92。如果跑出 0八成是三个数组的初值设成了 0如果跑出 4 或 8 之类的数多半是恢复现场那三行漏了其中一行导致后面的分支被前面残留的标记挡住。提示把N改成 4、5、6 分别跑一遍已知解数是 2、10、4。这三个小规模数据是验证剪枝写对没写对的最快方式比一上来就跑 8 皇后好定位。4. 把示例代码改成可测试的工程结构文档里的代码都是「一个文件、一个main、直接打印」的形态适合看不适合验证。改了参数对不对、剪枝有没有漏、边界有没有越界全靠肉眼盯输出。把 51 个题目逐个改造成能跑断言的形态工作量太大但挑十来个核心题目改一遍后面的题照着套就行。4.1 剥掉 main让求解函数返回结果而不是打印第一个改造动作是把「打印」换成「返回」。以八皇后为例原版在row N时调用showAnswer()打印棋盘改成返回计数函数签名就从void变成long long递归里的累加也顺理成章。#include stdio.h #define N 8 static int col[N 1], d1[2 * N 1], d2[2 * N 1]; /* 返回从第 row 行开始能摆出的完整解数 */ static long long dfs(int row) { if (row N) return 1; /* 走到第 N1 行说明前 N 行都摆好了 */ long long total 0; for (int c 1; c N; c) { if (!col[c] !d1[row c] !d2[row - c N]) { col[c] d1[row c] d2[row - c N] 1; total dfs(row 1); /* 子问题的解数累加回来 */ col[c] d1[row c] d2[row - c N] 0; } } return total; } int main(void) { long long got dfs(1); printf(N%d solutions%lld\n, N, got); if (got ! 92) { /* 已知解数做回归断言 */ fprintf(stderr, regression failed: expect 92\n); return 1; } return 0; }改造的关键在第 8 行if (row N) return 1;。原来这里是「打印并计数」现在变成「返回 1 表示找到一条完整路径」父层把这个 1 累加进total一路传回根节点。这个「返回可行解数量」的模式可以直接套到迷宫返回路径条数、子集枚举返回子集个数、数字拆解返回拆分数上是这类回溯题最通用的骨架。改造后的直接收益是可以在main里写断言。断言比打印靠谱因为打印你需要人眼比对断言是程序自己比对跑完退出码非 0 就说明回归了。我一般会把已知结果整理成一张小表放在测试脚本里。题目断言用的已知值说明八皇后 N892经典解数改剪枝逻辑后必须仍然成立八皇后 N64小规模方便打断点河内塔 n101023等于 2^10 - 1筛法 n100000078498一百万以内素数个数约瑟夫环 n41, k331经典设定下的幸存位置注意这些已知值只能在「题目定义完全一致」的前提下用。比如约瑟夫环有从 0 编号和从 1 编号两种约定差一个偏移断言就会误报。4.2 大数加法进位只可能进 1别照抄乘法的写法第 16 题的超长整数运算文档给了加减乘除一整套。加法是最短的但也是最容易被写错的因为很多人会把乘法的进位逻辑直接搬过来。#include stdio.h #include string.h #define MAXLEN 1000 /* 支持最多 1000 位十进制数 */ /* 低位在前存进 buf模拟竖式加法out 必须以 \0 结尾 */ static void bigadd(const char *a, const char *b, char *out) { int la (int)strlen(a), lb (int)strlen(b); int buf[MAXLEN 2] {0}; /* 多开两位给最高位进位留空间 */ int len la lb ? la : lb; for (int i 0; i len; i) { int da (i la) ? a[la - 1 - i] - 0 : 0; /* 从个位开始取 */ int db (i lb) ? b[lb - 1 - i] - 0 : 0; buf[i] da db; if (buf[i] 10) { /* 加法进位只可能是 1 */ buf[i] - 10; buf[i 1] 1; } } int top len; while (top 0 buf[top] 0) top--; /* 跳过前导零但至少保留一位 */ int k 0; for (int i top; i 0; i--) out[k] (char)(0 buf[i]); out[k] \0; } int main(void) { char out[MAXLEN 2]; bigadd(99999999999999999999, 1, out); /* 20 个 9 加 1专门测连续进位 */ printf(%s\n, out); return 0; }buf开到MAXLEN 2而不是MAXLEN是因为两个 1000 位数相加结果最多 1001 位最高位的进位要有个地方落。很多人图省事开成MAXLEN然后在buf[i 1] 1那一行踩到越界编译器不报错跑起来把相邻内存改了输出看着还挺正常这种属于典型的血泪经验。top的循环条件写成top 0 buf[top] 0top 0这个限制是为了保住最低位——结果是 0 的时候不能把所有位都跳掉否则输出空字符串。这个细节在减法里同样存在文档的减法代码里就有类似处理。乘法不能套这段。乘法的中间累加值可能远大于 10进位可能是几十必须用「先累加再统一进位」的写法不能在循环里就地取模。这两段代码形态差别很大混用是这份文档里最容易犯的错。4.3 筛法与插补查找参数范围决定了代码能不能跑第 15 题的埃氏筛法文档写法是从 2 开始把每个素数的倍数标记掉。改造成能接受命令行参数的版本后有几个参数必须想清楚。#include stdio.h #include stdlib.h int main(int argc, char **argv) { long n (argc 1) ? atol(argv[1]) : 1000000L; /* 上限默认一百万 */ char *comp calloc((size_t)n 1, 1); /* comp[i]1 表示 i 是合数 */ if (!comp) { perror(calloc); return 1; } long cnt 0; for (long i 2; i n; i) { if (comp[i]) continue; /* 已被标记跳过 */ cnt; if (i * i n) /* 先判越界再筛防止 i*i 溢出 */ for (long j i * i; j n; j i) comp[j] 1; } printf(primes %ld : %ld\n, n, cnt); free(comp); return 0; }三个参数点。calloc而不是malloc因为需要初始化为 0malloc拿到的是脏内存标记会乱。char而不是int存标记一百万规模下省三倍内存缓存命中率也高。内层循环从i * i开始而不是2 * i因为小于i * i的合数一定已经被更小的素数筛过了这一步能省掉将近一半的标记操作。if (i * i n)这个判断是防溢出的。i是long在 64 位平台上i * i到 30 亿才溢出看起来安全但如果哪天把long改成int比如在嵌入式环境i到 46341 时i * i就翻负了内层循环直接不执行结果会漏掉一大批合数。这种错误在小数据上测不出来必须跑到 n 大于 10 亿才暴露属于典型的「上线才炸」。第 44 题的插补查找有个类似的前置条件数据必须近似均匀分布而且不能有重复值否则mid的计算会退化。文档里的mid low (high - low) * (key - a[low]) / (a[high] - a[low])这行分母是a[high] - a[low]如果首尾元素相等就直接除零。实际用的时候我会在前面加一句if (a[high] a[low]) return -1;。5. 踩坑排查51 个例子里最容易翻车的五处这份文档的代码整体质量不错但毕竟是逐题整理的版本之间风格不统一有几处明显的坑。下面五条都是我自己或者身边的人实际踩过的按「现象 → 原因 → 解决」记下来。5.1 迷宫二只打印左上角一小块现象把第 6 题的源码编译跑通屏幕上确实出现了路径但棋盘只画了左上角 7×7 的一小块右边和下边是空的看着像被裁掉了。原因这一题的maze数组定义成了maze[9][9]入口在(1,1)出口在(7,7)但main里打印迷宫的循环条件写的是i 7和j 7。这个 7 是从第 5 题的 7×7 迷宫抄过来的改成 9×9 的时候只改了数组没改循环。解决把所有硬编码的 7 换成宏或者sizeof推导。#define ROW 9然后循环写i ROW改维度时只改一处。更稳的写法是sizeof(maze) / sizeof(maze[0])但要注意传参退化成指针的情况这里maze是全局数组不会退化可以直接用。5.2 骑士走棋盘编译报隐式声明现象用-stdc99 -Wall编译第 7 题main里调用travel那一行报implicit declaration of function travel链接时直接失败提示 undefined reference。原因travel函数的定义写在main之后前面没有原型声明。C89 允许隐式声明默认返回 intC99 起这个行为被移除编译器直接报错。文档里的代码大概是按 C89 的习惯写的。解决在main前面加一行int travel(int x, int y);。另一种办法是编译时加-stdgnu89把标准退回去但这会关掉一堆现代检查不推荐。加原型是最小改动也是后面所有题目通用的做法——凡是被调函数写在后面一律先声明。5.3 费氏数列跑到第 47 项变成负数现象第 2 题的代码里#define N 20输出正常。改大到 50 想多看几项第 47 项开始出现负数后面越来越离谱。原因int在 32 位下最大 2147483647斐波那契第 46 项是 1836311903第 47 项就溢出成负数了。这是整数溢出不是算法错。解决把数组类型改成long longN可以安全开到 92第 93 项开始超出 64 位有符号范围。如果要更大就得上第 16 题那套大数数组。这里有个容易忽略的点printf的格式符也要跟着从%d改成%lld只改类型不改格式符输出依然是错的而且是那种「看着像个正常数字」的错。5.4 回溯漏了恢复现场解数少一大截现象把八皇后的三个标记数组从「1 表示可用」改成「1 表示占用」改完之后跑出来只有 4 个解而不是 92 个。原因语义反了之后backtrack里的三行赋值也要跟着反过来——原来放皇后是设 0恢复是设 1现在放皇后是设 1恢复是设 0。只改了初始化没改这两处导致递归返回后标记一直停在「占用」状态后面的分支全被挡住。解决把「占位」和「恢复」两行写成紧挨着的一对中间只隔一个递归调用视觉上形成配对改的时候不容易只改一半。更彻底的办法是把这个模式抽成两个宏MARK(row, c)和UNMARK(row, c)两边永远同时改。5.5 快速排序遇到有序输入退化成平方级现象第 37 题的快速排序测试数据随机生成时 10 万个元素零点几秒跑完换成已经排好序的数组跑了十几秒还没出结果。原因文档里的快排固定取第一个元素做主元。对已经有序的输入每次划分都退化成「一边 1 个、一边 n-1 个」递归深度变成 n复杂度从 O(n log n) 掉到 O(n²)。10 万个元素就是 100 亿次比较的量级。解决主元改成三数取中取首、中、尾三个位置的中间值作为主元同时在划分时把等于主元的元素均匀分到两边。改完之后有序输入和随机输入的性能基本持平。这个改动只有七八行但它是快排能不能用于真实数据的分水岭文档里三个快排版本都没有处理这一点。6. 进阶用法把 51 个例子做成自己的模板库走到这一步51 个题目大概跑通了七成剩下的多半是矩阵和概率类的不影响主线。接下来要做的不是继续刷而是把它们沉淀下来。我的做法是建一个templates/目录只放五类骨架回溯带状态恢复、二分三种边界写法、大数加减乘各一个、筛法、并查集。每类一个文件函数签名固定参数用宏或者结构体传不写main靠单独的test_*.c去调。这套东西的价值在于「下次不用重新想」。真到了比赛或者面试现场回溯的框架是肌肉记忆写的时候只需要填状态定义和剪枝条件剩下的骨架直接从模板里抄。文档给的是 51 个完整例子模板库给的是 5 个可以拼装的最小单元后者复用率高得多。再补一个验收清单每次改完模板跑一遍检查项判定方式常见失败原因回溯解数正确对照第 4 章那张已知值表恢复现场漏一行边界输入不崩n 0、n 1、n 上限 各跑一次循环条件写成或溢出可控用-fsanitizeundefined编译跑一遍中间结果用 int 存内存不越界用-fsanitizeaddress编译跑一遍数组开小一位结果可复现固定随机种子跑两次比对输出用了time(NULL)做种子-fsanitizeundefined和-fsanitizeaddress这两个编译选项我应该早点用。当年照着文档抄筛法int数组开成n而不是n 1comp[n]那一格越界写了一个字节程序跑了半小时才崩中间输出全是正常的。后来加了 ASan编译完第一次运行就把越界位置精确打出来了。从那以后我每次把文档里的代码改成自己的版本都强制走一遍两个 sanitizer 再合并进模板库哪怕它看起来「只是改了个变量名」。希望帮到你。本文还有配套的精品资源点击获取
