简介这是一份面向ACM竞赛选手与算法学习者的经典算法题解合集覆盖从递归入门到动态规划、图论搜索、组合优化等核心专题适合希望系统刷题、夯实算法思维的中高级编程学习者。压缩包内仅含1个doc文档约1.77MB共126页按目录顺序编排了51个经典案例每道题均配有题目说明、解题思路、分析过程与可运行源码便于对照理解与动手验证。内容涵盖河内之塔、费式数列、巴斯卡三角形、三色棋、老鼠走迷宫、骑士走棋盘、八皇后、八枚银币、生命游戏、字串核对、双色与三色河内塔、背包问题、蒙地卡罗法求PI、Eratosthenes筛选求质数、超长整数运算等从递归、回溯、图遍历到动态规划层层递进。目前已有406人学习适合作为竞赛备赛与算法课程复习的参考材料。1. 从一份 126 页的 Word 说起ACM 51 个经典算法大全到底能解决什么如果你正在准备 ACM 校赛、蓝桥杯或者只是想把算法基础重新捋一遍大概率会遇到一个尴尬网上题解满天飞但真正把「题目描述 → 解题思路 → 分析过程 → 可运行源码」四样东西凑齐的资料并不多。这份《ACM 51 个经典算法大全》就是少数凑齐了的——Word 文档共 126 页收录 51 个经典算法案例每个案例都带题目说明、解法推导和一份能直接编译运行的 C 语言源码。它不是那种只给你一个结论的速查表而是把递归、回溯、动态规划、图遍历、排序查找、矩阵操作这些 ACM 高频考点的「思考路径」摊开给你看。适合谁适合刚接触算法竞赛、需要一份能照着敲、能跑通、能改参数的实战底稿的人也适合已经工作、想用最短时间把经典算法手感找回来的开发者。下面我按「这份资料怎么用 → 核心算法怎么落地 → 坑在哪 → 怎么进阶」的顺序把它拆开讲清楚。2. 递归与回溯河内之塔、八皇后、骑士走棋盘怎么跑通2.1 河内之塔递归三行代码背后的移动次数边界河内之塔是这份资料的第 1 个案例也是理解递归最直观的入口。它的规则很简单三根柱子 A、B、Cn 个大小不一的盘子从 A 移到 C每次只能移动一个且大盘不能压在小盘上。资料里给出的解法核心就三行递归逻辑但真正值得关注的是它附带的移动次数推导n 个盘子需要 2^n - 1 次移动。当 n64 时这个数字是 18446744073709551615按每秒搬一个盘子算大约 5850 亿年。这个数字不是噱头它提醒你递归的时间复杂度在指数级场景下有多恐怖。#include stdio.h void hanoi(int n, char A, char B, char C) { if (n 1) { // 只剩一个盘子时直接从 A 移到 C printf(Move sheet %d from %c to %c\n, n, A, C); } else { // 先把上面 n-1 个盘子从 A 移到 B借助 C hanoi(n - 1, A, C, B); // 把最底下第 n 个盘子从 A 移到 C printf(Move sheet %d from %c to %c\n, n, A, C); // 再把 B 上的 n-1 个盘子移到 C借助 A hanoi(n - 1, B, A, C); } } int main() { int n; printf(请输入盘数); scanf(%d, n); hanoi(n, A, B, C); return 0; }这段代码的逻辑说明hanoi(n, A, B, C)的含义是「把 n 个盘子从 A 借助 B 移到 C」。递归的终止条件是 n1此时直接移动。参数怎么改如果你想观察移动过程把printf换成计数变量累加即可如果你想验证 2^n - 1在 main 里加一个计数器输入 n10、n20 分别跑一遍输出次数会严格吻合。常见误用是忘记递归中柱子的角色互换——第一次递归调用是hanoi(n-1, A, C, B)第二次是hanoi(n-1, B, A, C)顺序写反了盘子就会压错。2.2 八皇后回溯 分支修剪把 92 种解全部打出来八皇后是回溯法的经典代表。资料里的实现用了一个 8×8 的棋盘但并没有真的开二维数组去逐格检查而是用三个一维数组column[]、rup[]、lup[]分别标记「同列」「右上至左下对角线」「左上至右下对角线」是否已被占用。这就是分支修剪——一旦某列或某条对角线被占直接跳过不再往下递归。#include stdio.h #include stdlib.h #define N 8 int column[N 1]; // 同栏是否有皇后1 表示有 int rup[2 * N 1]; // 右上至左下是否有皇后 int lup[2 * N 1]; // 左上至右下是否有皇后 int queen[N 1] {0}; // queen[i] j 表示第 i 行皇后在第 j 列 int num; // 解答编号 void backtrack(int i) { int j; if (i N) { // 找到一个完整解打印棋盘 printf(\n解答 %d\n, num); for (int y 1; y N; y) { for (int x 1; x N; x) { if (queen[y] x) printf( Q); else printf( .); } printf(\n); } } else { for (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; // 回溯恢复 } } } } int main() { num 0; 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); return 0; }参数说明column[j]标记第 j 列是否可用rup[ij]标记右上至左下对角线lup[i-jN]标记左上至右下对角线加 N 是为了避免负索引。运行后你会得到 92 个解这是 8 皇后问题的标准答案数。如果你想改成 n 皇后把#define N 8改成其他值即可但注意 n 超过 13 以后回溯耗时会明显上升这时候需要加更细的剪枝策略。资料里还提到了骑士走棋盘用的是 Warnsdorff 启发式——优先走「下一步出路最少」的位置这个思路在路径规划类题目里很常见值得单独拎出来理解。3. 动态规划与数学方法背包、大数运算、质数筛选的落地细节3.1 背包问题从二维 DP 表到一维滚动数组的压缩背包问题是这份资料里动态规划部分的重点。资料给出的思路是标准的二维 DPdp[i][j]表示前 i 件物品在容量 j 下的最大价值状态转移方程是dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])。但实际写代码时很多人会忽略一个优化如果每件物品只能选一次0/1 背包可以把二维表压缩成一维数组内层循环从大到小遍历容量。#include stdio.h #define MAX_W 1000 #define MAX_N 100 int max(int a, int b) { return a b ? a : b; } int main() { int n, W; int w[MAX_N], v[MAX_N]; int dp[MAX_W 1] {0}; printf(输入物品数量和背包容量); scanf(%d %d, n, W); for (int i 0; i n; i) { printf(输入第 %d 件物品的重量和价值, i 1); scanf(%d %d, w[i], v[i]); } // 一维滚动数组容量从大到小遍历保证每件物品只选一次 for (int i 0; i n; i) { for (int j W; j w[i]; j--) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } } printf(最大价值%d\n, dp[W]); return 0; }逻辑说明外层循环遍历物品内层循环从W递减到w[i]。为什么必须递减因为如果从小到大遍历dp[j-w[i]]可能已经被当前物品更新过相当于一件物品被选了多次那就变成了完全背包。这个细节是背包问题里最容易翻车的地方资料里的二维写法不会出这个问题但一旦你手动优化成一维就必须记住这个方向。参数怎么改如果题目变成「每件物品可以选无限次」内层循环改成从小到大即可如果变成「多重背包」需要额外加一层数量循环或二进制拆分。3.2 大数运算与质数筛选数组模拟和埃氏筛的边界处理超长整数运算大数运算是 ACM 里绕不开的基础设施。C 语言的long long最多到 19 位左右再大就得用数组模拟。资料里的做法是用一个整型数组存每一位低位在前手动实现加、减、乘、除和取模。这里的关键参数是数组长度——一般开到 1000 以上具体看题目数据范围。另一个高频案例是 Eratosthenes 筛选求质数核心是一个布尔数组从 2 开始把每个质数的倍数全部标记为非质数。#include stdio.h #include string.h #define MAX 1000000 int main() { int is_prime[MAX 1]; memset(is_prime, 1, sizeof(is_prime)); is_prime[0] is_prime[1] 0; for (int i 2; i * i MAX; i) { if (is_prime[i]) { // 从 i*i 开始标记因为小于 i*i 的倍数已被更小的质数筛过 for (int j i * i; j MAX; j i) { is_prime[j] 0; } } } int count 0; for (int i 2; i MAX; i) { if (is_prime[i]) count; } printf(1 到 %d 之间的质数个数%d\n, MAX, count); return 0; }参数说明MAX决定筛选范围i * i MAX是循环上界内层从i * i开始而不是2 * i这是一个常数级优化。注意memset(is_prime, 1, sizeof(is_prime))把每个字节设为 1对于 int 数组来说每个元素会变成0x01010101不是 1。正确做法是用char数组或者手动循环初始化。这个坑我在第一次写筛法时就踩过输出结果全错排查了半天才发现是memset的字节语义问题。4. 排序与查找从冒泡到基数排序什么时候该换算法4.1 排序算法选型数据规模决定一切这份资料覆盖了选择排序、插入排序、气泡排序、Shell 排序、Shaker 排序、快速排序三种写法、合并排序、基数排序。很多人学排序时容易陷入「背代码」的误区但实际做题时真正重要的是选型。数据量在 1000 以内插入排序和冒泡排序的常数小写起来快数据量到 10^5必须上快速排序或合并排序如果数据范围集中且是整数基数排序的 O(n) 优势就体现出来了。排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性适用场景插入排序O(n²)O(n²)O(1)稳定小规模或基本有序快速排序O(n log n)O(n²)O(log n)不稳定通用大规模排序合并排序O(n log n)O(n log n)O(n)稳定需要稳定排序或链表基数排序O(d(nk))O(d(nk))O(nk)稳定整数且范围集中资料里快速排序给了三种写法区别主要在基准值的选择和分区方式。第一种取首元素为基准第二种取中间元素第三种做了更细致的三数取中。实际刷题时我一般直接用第三种因为它在面对近似有序数据时退化概率更低。但要注意快速排序的最坏情况是 O(n²)如果题目数据经过特殊构造合并排序是更稳妥的选择。4.2 查找算法卫兵、二分、插补、费氏搜寻的取舍查找部分资料给了四种循序搜寻带卫兵、二分搜寻、插补搜寻、费氏搜寻。循序搜寻的「卫兵」技巧值得单独说——在数组末尾放一个待查找值作为哨兵这样内层循环就不用每次判断是否越界减少一次比较。二分搜寻是标准写法但边界条件low high还是low high经常让人写错。插补搜寻适合数据分布均匀的场景它用mid low (key - a[low]) / (a[high] - a[low]) * (high - low)来估算位置均匀分布时比二分更快但分布不均时反而更慢。费氏搜寻用斐波那契数列分割理论上有优势但实际常数较大除非题目明确要求否则二分足够。#include stdio.h // 带卫兵的循序搜寻 int sequential_search(int a[], int n, int key) { int last a[n - 1]; a[n - 1] key; // 设置卫兵 int i 0; while (a[i] ! key) i; a[n - 1] last; // 恢复原值 if (i n - 1 || a[n - 1] key) return i; return -1; } // 标准二分搜寻 int binary_search(int a[], int n, int key) { int low 0, high n - 1; while (low high) { int mid low (high - low) / 2; // 防止溢出 if (a[mid] key) return mid; else if (a[mid] key) low mid 1; else high mid - 1; } return -1; } int main() { int a[] {1, 3, 5, 7, 9, 11, 13, 15}; int n sizeof(a) / sizeof(a[0]); printf(循序查找 7索引 %d\n, sequential_search(a, n, 7)); printf(二分查找 11索引 %d\n, binary_search(a, n, 11)); return 0; }参数说明卫兵搜寻里a[n-1]被临时覆盖循环结束后必须恢复否则数组被破坏。二分搜寻里mid low (high - low) / 2是为了防止low high溢出虽然 int 范围内一般不会但养成习惯没坏处。资料里还提到插补搜寻和费氏搜寻前者适合均匀分布后者适合斐波那契分割但实际竞赛中二分的出场率远高于这两者。5. 避坑与排查这份资料跑起来最容易翻车的五个地方5.1 编译环境不匹配导致源码跑不通现象资料里的 C 代码在本地编译时报错提示scanf不安全或void main不合法。原因这份资料年代较早部分代码用了void main()或gets()等旧标准写法现代编译器默认不通过。解决把void main改成int main并在末尾return 0gets()换成fgets()如果用的是 Visual Studio在文件开头加#define _CRT_SECURE_NO_WARNINGS关闭安全警告。5.2 数组越界与索引偏移现象八皇后或迷宫程序运行时输出乱码或直接崩溃。原因资料里部分数组从索引 1 开始使用但声明时开了N1或2*N1如果手动改成从 0 开始边界条件没同步调整就会越界。解决保持资料原有的索引习惯不要随意改起始下标如果非要改先把所有i N和i N的循环条件核对一遍。5.3 递归深度过大导致栈溢出现象河内之塔输入 n30 以上时程序崩溃。原因递归调用层数等于 n每层都有局部变量和返回地址默认栈空间不够。解决把递归改成迭代或者手动增大栈空间编译器选项更实际的做法是河内之塔本身只适合演示递归思想n 超过 20 的输出量已经不适合人眼观察用计数器验证公式即可。5.4 浮点误差在蒙地卡罗法求 PI 中的体现现象蒙地卡罗法求 PI 每次运行结果波动较大有时偏差超过 0.01。原因随机采样点数不够或者rand()的范围和精度有限。解决把采样次数提高到 10^7 以上用(double)rand() / RAND_MAX生成 0 到 1 之间的浮点数如果平台支持换用drand48()或 C 的mt19937获得更好的随机性。5.5 排序算法在特定数据下的退化现象快速排序在近似有序数组上跑得比插入排序还慢。原因基准值选择不当导致每次分区极不平衡递归深度退化成 O(n)。解决用三数取中或随机基准如果题目数据规模不大且基本有序直接上插入排序反而更快。资料里给了三种快排写法建议都跑一遍对比感受一下基准值选择对性能的影响。6. 进阶用法把 51 个案例变成自己的算法模板库这份资料最大的价值不在于「读一遍」而在于「拆一遍、改一遍、存一遍」。我自己的做法是把 51 个案例按题型分成六类——递归回溯、动态规划、数学方法、排序、查找、矩阵操作每类挑 2 到 3 个最典型的把源码改成自己顺手的风格加上详细注释和测试用例存成一个本地模板库。比如河内之塔的递归框架可以直接套到「生成所有子集」上八皇后的回溯模板改一下冲突判断就能解数独背包的一维滚动数组写法稍作变形就是「零钱兑换」的解法。具体操作上我一般会建一个目录每个算法一个.c文件文件头写清楚「适用题型」「时间复杂度」「关键参数」「易错点」。然后写一个Makefile或者简单的build.sh一键编译所有文件确保每次改动后都能跑通。下面是一个模板文件头的示例/* * 算法0/1 背包一维滚动数组 * 适用给定容量和物品重量价值求最大价值 * 时间O(n * W) * 关键参数dp 数组大小 容量上限 1 * 易错点内层循环必须从大到小否则变成完全背包 * 测试n3, W5, w{2,3,4}, v{3,4,5} - 答案 7 */另外资料里的 51 个案例并不是孤立的。巴斯卡三角形和排列组合可以互相验证三色棋和快速排序的分区思想同源老鼠走迷宫一和二的区别只在「找到一个解就停」还是「找所有解」这个差异在回溯模板里就是一个return语句的位置。把这些关联点标出来你的模板库就不是 51 个孤立文件而是一张互相引用的知识网。从那以后我每次拿到一份算法资料都会先跑通、再拆解、最后归档成自己的模板而不是读完就放在一边。这份 126 页的 Word 我前后翻了不下五遍每次都能从之前忽略的注释里找到新东西。希望帮到你。本文还有配套的精品资源点击获取