简介这份《ACM51个经典算法大全》面向ACM竞赛选手与算法学习者是一份系统梳理经典算法题型的Word文档资料适合希望夯实算法基础、提升编程思维的中高级学习者。压缩包内共1个doc文件约1.77MB文档共126页按目录依次收录51个经典算法实例涵盖递归、图论、动态规划、搜索与组合优化等多个方向。内容从河内之塔、费式数列、巴斯卡三角形等基础递归与数列问题切入延伸至老鼠走迷宫、骑士走棋盘、八皇后等搜索与回溯题型并包含背包问题、蒙地卡罗法求PI、Eratosthenes筛选求质数、超长整数运算等进阶主题。每个实例均配有题目说明、解题思路、分析过程与可运行源码便于读者对照理解算法设计逻辑并动手验证。目前已有406人学习下载适合作为ACM备赛与算法专项训练的参考材料。1. 从河内塔到魔方阵一份 51 题算法合集的正确打开方式很多人刷算法题的习惯是打开在线判题平台挑一道高频题写完提交过了就翻篇。但真到面试或者比赛现场遇到一个没见过的问题脑子里没有可迁移的模型就容易卡住。这份《ACM51个经典算法大全》的价值恰恰在这里它不是题库而是一份按问题类型组织的算法模型清单从河内之塔的递归拆解到八皇后的分支修剪再到背包问题的动态规划51 个例子覆盖了递归、回溯、贪心、动态规划、图遍历、大数运算、矩阵压缩等核心套路。文档共 126 页每个例子都配了题目说明、解题思路和可运行的 C 源码适合刚接触 ACM 赛制的新手建立分类意识也适合有经验的选手拿来当速查手册在遇到陌生题型时快速定位到相近的模型。2. 递归与回溯河内塔、八皇后、骑士走棋盘的状态管理2.1 递归三要素在河内塔中的体现河内塔是理解递归最干净的入口。它的递归结构可以拆成三步把上面 n-1 个盘子从 A 移到 B把第 n 个盘子从 A 移到 C再把 n-1 个盘子从 B 移到 C。终止条件是 n1 时直接移动。文档里的 C 代码把这三步直接翻译成了函数调用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 个盘子从 A 经 C 移到 B printf(Move sheet %d from %c to %c\n, n, A, C); // 移动第 n 个盘子 hanoi(n-1, B, A, C); // 将 n-1 个盘子从 B 经 A 移到 C } }这里的关键参数是三个柱子角色在递归调用中的轮换第一次递归时 C 变成辅助柱第二次递归时 A 变成辅助柱。移动次数为 2^n - 1n64 时约 1.8×10^19 次按每秒一次算要 5850 亿年。这个数字不是用来吓人的它说明递归解法虽然优雅但指数级增长的问题规模必须靠数学公式提前判断可行性。2.2 八皇后用三个布尔数组做分支修剪八皇后的朴素做法是枚举 8^8 种摆放但文档里的实现用 column、rup、lup 三个数组把冲突检测降到 O(1)#define N 8 int column[N1]; // 同列是否有皇后 int rup[2*N1]; // 右上到左下对角线 int lup[2*N1]; // 左上到右下对角线 int queen[N1]; // queen[i] j 表示第 i 行皇后在第 j 列 void backtrack(int i) { if(i N) { showAnswer(); } else { for(int j 1; j N; j) { if(column[j] rup[ij] lup[i-jN]) { queen[i] j; column[j] rup[ij] lup[i-jN] 0; // 占用 backtrack(i1); column[j] rup[ij] lup[i-jN] 1; // 回溯 } } } }对角线索引的设计是重点ij 的范围是 2 到 2Ni-jN 的范围是 1 到 2N-1正好把两个方向的对角线映射到一维数组。这种「用索引编码约束」的手法在数独、N 皇后变体中反复出现。剪枝的效果很明显不检查同列已占的格子搜索树规模从 8^8 降到 4 万多个节点。2.3 骑士走棋盘Warnsdorff 启发式与贪心选择骑士旅游如果纯回溯8×8 棋盘上搜索空间极大。文档采用的 Warnsdorff 规则是每次优先走「下一步可选方向最少」的那个格子。代码里先试探八个方向统计每个候选位置的出路数再选出路最少的// 统计每个候选方向的出路数 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; } }这个贪心策略不保证一定找到解但在 8×8 上成功率很高。它和后面背包问题的贪心思路形成对照贪心在有些问题上能快速给出可行解在另一些问题上只能给近似解判断标准是问题是否具有贪心选择性质。算法核心策略时间复杂度适用场景河内塔递归分解O(2^n)教学演示、递归思维训练八皇后回溯剪枝O(n!) 剪枝后大幅降低约束满足问题骑士旅游Warnsdorff 贪心O(n^2) 每步哈密顿路径近似求解3. 动态规划与数学方法背包、大数运算与质数筛选3.1 背包问题的二维 DP 表与空间优化背包问题是动态规划的入门经典。文档给出的思路是定义 dp[i][j] 为前 i 个物品在容量 j 下的最大价值状态转移方程为 dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])。用 Python 复现如下def knapsack(weights, values, capacity): n len(weights) # dp[j] 表示容量为 j 时的最大价值 dp [0] * (capacity 1) for i in range(n): # 逆序遍历保证每个物品只被选一次 for j in range(capacity, weights[i] - 1, -1): dp[j] max(dp[j], dp[j - weights[i]] values[i]) return dp[capacity] weights [2, 3, 4, 5] values [3, 4, 5, 6] print(knapsack(weights, values, 8)) # 输出 10一维数组逆序遍历是 0-1 背包的标准写法正序遍历则变成完全背包。这个细节在面试中经常被追问。参数 capacity 决定数组长度weights[i] 是第 i 个物品的重量逆序保证 dp[j-w[i]] 取的是上一轮的值不会被本轮更新覆盖。3.2 大数运算用数组模拟手工计算C 语言的 long long 最多到 2^63-1约 9.2×10^18。文档里的超长整数运算用数组逐位存储模拟竖式加减乘除。以加法为例#define MAX 1000 void bigAdd(int a[], int b[], int result[]) { int carry 0; for(int i 0; i MAX; i) { int sum a[i] b[i] carry; result[i] sum % 10; // 当前位 carry sum / 10; // 进位 } }数组下标 0 存个位依次向高位延伸。乘法的思路是双重循环result[ij] a[i] * b[j]最后统一处理进位。这种表示法在 Python 里不需要因为 Python 的 int 是任意精度但理解底层实现有助于在 C/C 环境中处理大数问题。3.3 Eratosthenes 筛法与蒙地卡罗求 PIEratosthenes 筛法的核心是从 2 开始把每个质数的倍数标记为合数def sieve(n): is_prime [True] * (n 1) is_prime[0] is_prime[1] False for i in range(2, int(n**0.5) 1): if is_prime[i]: for j in range(i*i, n 1, i): is_prime[j] False return [i for i in range(n 1) if is_prime[i]] print(sieve(30)) # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]内层循环从 ii 开始因为小于 ii 的合数已经被更小的质数筛过了。时间复杂度 O(n log log n)。蒙地卡罗求 PI 则是另一种思路在单位正方形内随机撒点统计落在四分之一圆内的比例乘以 4 得到 PI 的近似值。撒点越多越接近真实值但收敛速度是 O(1/√n)精度提升很慢。注意筛法在 n 超过 10^7 时内存占用明显可以用位数组或分段筛优化。4. 排序与搜索从 Shell 排序到插补搜寻的工程取舍4.1 四种基础排序的适用边界文档覆盖了选择、插入、气泡、Shell、Shaker、快速、合并、基数共八种排序。前三种 O(n^2) 排序在数据量小于 100 时差异不大但插入排序在近乎有序的数据上接近 O(n)。Shell 排序是插入排序的改良版通过增量序列把远距离元素先粗略排好def shell_sort(arr): n len(arr) gap n // 2 while gap 0: for i in range(gap, n): temp arr[i] j i # 对间隔为 gap 的子序列做插入排序 while j gap and arr[j - gap] temp: arr[j] arr[j - gap] j - gap arr[j] temp gap // 2 return arrgap 的选取影响性能常见的有 n/2 折半和 Knuth 序列 (3^k-1)/2。折半实现简单但在某些数据上不如 Knuth 序列稳定。4.2 快速排序的三种划分策略文档里快速排序给了三个版本区别在 pivot 的选择取第一个元素、取中间元素、取随机元素。取第一个元素在已排序数据上退化为 O(n^2)取随机元素可以概率上避免最坏情况。工程中常见的做法是「三数取中」取左端、中间、右端三个数的中位数作为 pivot。import random def quick_sort(arr, low, high): if low high: # 随机选 pivot 并交换到低位 rand_idx random.randint(low, high) arr[low], arr[rand_idx] arr[rand_idx], arr[low] pivot arr[low] i, j low, high while i j: while i j and arr[j] pivot: j - 1 arr[i] arr[j] while i j and arr[i] pivot: i 1 arr[j] arr[i] arr[i] pivot quick_sort(arr, low, i - 1) quick_sort(arr, i 1, high) return arr4.3 二分搜寻、插补搜寻与费氏搜寻的对比二分搜寻每次取中点插补搜寻则根据目标值在范围内的比例估算位置mid low (high - low) * (target - arr[low]) / (arr[high] - arr[low])。在均匀分布的数据上插补搜寻接近 O(log log n)但数据分布倾斜时反而比二分慢。费氏搜寻用斐波那契数列确定分割点避免除法运算在早期硬件上有优势现在更多是算法教学价值。搜索算法分割点计算适用数据分布平均时间复杂度二分搜寻中点任意有序O(log n)插补搜寻按比例估算均匀分布O(log log n)费氏搜寻斐波那契分割任意有序O(log n)5. 矩阵压缩与魔方阵构造从稀疏矩阵到奇数阶幻方5.1 稀疏矩阵的三元组表示当矩阵中非零元素远少于总元素时用二维数组存储浪费空间。文档里的做法是用三元组 (row, col, value) 只存非零项#define MAX_TERMS 100 typedef struct { int row; int col; int value; } Term; Term sparse[MAX_TERMS]; int termCount 0; void addTerm(int r, int c, int v) { if(v ! 0) { sparse[termCount].row r; sparse[termCount].col c; sparse[termCount].value v; termCount; } }转置操作从遍历整个矩阵变成遍历三元组数组时间复杂度从 O(rows×cols) 降到 O(termCount)。如果三元组按行优先有序转置时可以用「列计数排序」进一步优化到线性时间。5.2 上三角、下三角与对称矩阵的一维映射对称矩阵只需要存一半元素。文档给出的映射公式是对于 n×n 对称矩阵a[i][j] 映射到一维数组的索引 k i*(i1)/2 ji j 时。上三角矩阵类似只是索引公式不同。这种压缩在有限元计算和协方差矩阵存储中很常见。def symmetric_index(i, j): if i j: i, j j, i return i * (i 1) // 2 j # 验证3x3 对称矩阵的存储顺序 for i in range(3): for j in range(3): print(f({i},{j}) - {symmetric_index(i,j)}, end ) print()5.3 奇数魔方阵的 Siamese 方法奇数阶魔方阵n 为奇数的构造有固定算法1 放在第一行中间之后每个数放在前一个数的右上方如果右上方超出边界就绕回如果该位置已有数就放在正下方。文档里的实现直接翻译了这个规则def magic_square(n): if n % 2 0: raise ValueError(只支持奇数阶) magic [[0] * n for _ in range(n)] i, j 0, n // 2 for num in range(1, n * n 1): magic[i][j] num ni, nj (i - 1) % n, (j 1) % n if magic[ni][nj]: i (i 1) % n else: i, j ni, nj return magic for row in magic_square(5): print(row)4N 魔方阵和 2(2N1) 魔方阵的构造规则不同前者用对角线交换法后者用分块填充法。这些构造题在 ACM 中属于找规律类核心是先把小规模的手工结果列出来再归纳出位置变换规则。提示魔方阵的验证标准是每行、每列、两条对角线的和都等于 n(n^21)/2写完代码后先用这个公式做断言检查。6. 用断言和边界用例验证你的算法实现写完 51 个算法不等于掌握它们。真正拉开差距的是验证环节你能不能构造出覆盖边界条件的测试用例能不能用断言把算法的数学性质固化下来。以八皇后为例除了打印棋盘还可以加一个校验函数def validate_queens(queen, n): queen[i] j 表示第 i 行皇后在第 j 列 for i in range(n): for j in range(i 1, n): if queen[i] queen[j]: return False if abs(queen[i] - queen[j]) abs(i - j): return False return True这个函数不依赖回溯过程直接检查最终解是否满足约束。在调试时如果回溯逻辑有 bugvalidate 会立刻暴露冲突位置。类似地背包问题可以用小规模暴力枚举做交叉验证当物品数不超过 15 时枚举所有子集求最大价值和 DP 结果对比。另一个实用技巧是记录递归调用的深度和次数。河内塔的调用次数应该是 2^n - 1八皇后的回溯节点数可以用计数器统计和理论值对比。如果偏差过大说明剪枝条件写错了。对于排序算法用 Python 的random.shuffle生成 1000 个随机数排序后用arr sorted(arr)做断言再测已排序、逆序、全等、大量重复等边界情况。最后把每个算法的输入规模和时间消耗记录下来画一张简单的增长曲线。O(n^2) 和 O(n log n) 在 n1000 时可能只差几毫秒但 n100000 时差距会拉到秒级。这份 51 题合集里的每个例子都值得这样跑一遍跑完你对算法复杂度的直觉会比只看代码强得多。本文还有配套的精品资源点击获取
