template <classType> inlinevoidSwap(Type &a, Type &b) { Type temp = a; a = b; b = temp; } template <classType> voidPerm(Type list [], int k, int m){ // 产生 list[k:m] 的所有排列 if (k == m) { // 边界条件：只剩下一个元素，此时已完成一种全排列，进行打印 for (int i = 0; i <= m; i++) cout << list[i]; cout << endl; } else { // 递归步骤：还有多个元素待排列 for (int i = k; i <= m; i++) { // 将第 i 个元素交换到当前待排列位置 k Swap( list[k], list[i] ); // 递归产生剩余元素 (k+1 到 m) 的排列 Perm( list, k + 1, m ); // 恢复原状（回溯）：再次交换还原数组，以便进行下一次尝试 Swap( list[k], list[i] ); } } }
/** * n 待划分的正整数 * m 划分中允许的最大加数 * return 划分方案的总数 */ intq(int n, int m){ // 1. 边界条件：n或m为1时，只有一种划分方式（即 1+1+...+1 或 n=1） if (n < 1 || m < 1) return0; if (n == 1 || m == 1) return1;
// 2. 当最大加数限制 m 超过 n 时，有效限制其实就是 n if (n < m) { returnq(n, n); }
// 3. 当 n == m 时，划分包含两种情况： // - 只有 {n} 这一种划分：即 1 // - 最大加数小于 n 的划分：即 q(n, n-1) if (n == m) { return1 + q(n, n - 1); }
// 4. 当 n > m 时（一般情况），根据是否包含 m 分为两部分： // - q(n, m-1): 划分中不包含 m，即最大加数限制减小为 m-1 // - q(n-m, m): 划分中至少包含一个 m，则剩下的值 n-m 继续按最大加数 m 划分 returnq(n, m - 1) + q(n - m, m); }
汉诺塔 Hanoi
1 2 3 4 5 6 7 8 9
voidhanoi(int n, int a, int b, int c) { if (n > 0) { hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); } }
分治
1.说明算法策略
分解：将原问题划分为若干个规模较小、相互独立、与原问题形式相同的子问题。
解决：递归地解这些子问题。若子问题规模足够小，则直接解决。
合并：将子问题的解合并为原问题的解。
2.描述算法过程
用文字或图示描述算法逻辑
3.编写伪代码
4.复杂度分析
列递归方程：T(n)=aT(n/b)+f(n)。
证明方法：
主定理
递归树法
递归树法 1.以合并排序 T(n)=2T(n/2)+n 为例（平衡递归树）
1 2 3 4 5 6 7
>第 0 层: n ---- 工作量: n / \ >第 1 层: n/2 n/2 ---- 工作量: (n/2 + n/2) = n / \ / \ >第 2 层: n/4 n/4 n/4 n/4 ---- 工作量: (n/4 * 4) = n ... ... ... ... >第 log n 层: 1 1 1 1 ... 1 ---- 工作量: n 个 1 = n
template<class Type> intBinarySearch(Type a[], const Type& x, int l, int r) { while (r >= l){ int m = (l+r)/2; if (x == a[m]) return m; if (x < a[m]) r = m-1; else l = m+1; } return-1; }
// a: 原数组, b: 辅助数组, l: 左边界, m: 中间点, r: 右边界 voidMerge(Type a[], Type b[], int l, int m, int r) { int i = l, j = m + 1, k = l; // i指向左半部分起始，j指向右半部分起始，k为目标数组下标 // 比较两个子序列，将较小的元素依次放入数组 b while ((i <= m) && (j <= r)) { if (a[i] <= a[j]) b[k++] = a[i++]; else b[k++] = a[j++]; }
// 检查是否有剩余元素并复制到数组 b if (i > m) { // 如果左边元素已放完，将右边剩余部分直接复制 for (int q = j; q <= r; q++) b[k++] = a[q]; } else { // 如果右边元素已放完，将左边剩余部分直接复制 for (int q = i; q <= m; q++) b[k++] = a[q]; } }
// a: 待排序数组, left: 起始索引, right: 结束索引 voidMergeSort(Type a[], int left, int right) { if (left < right) { // 递归条件：当前区间至少有两个元素 int i = (left + right) / 2; // 取中点，将序列一分为二 MergeSort(a, left, i); // 递归排序左半部分 MergeSort(a, i + 1, right); // 递归排序右半部分 Merge(a, b, left, i, right); // 将排好序的两部分合并到辅助数组 b copy(a, b, left, right); // 将合并后的结果从 b 复制回原数组 a } }
// 划分函数 (Partition) // 该函数选择一个基准元素(pivot)，并将数组重新排列： // 小于基准的移到左边，大于基准的移到右边。 template<class Type> intPartition(Type a[], int p, int r){ int i = p; // 左指针，从基准位置开始 int j = r + 1; // 右指针，从数组末尾之后开始（配合 --j 使用） Type x = a[p]; // 选择当前子数组的第一个元素作为基准(pivot)
// 将 < x 的元素交换到左边区域 // 将 > x 的元素交换到右边区域 while (true) { // 从左向右寻找第一个大于或等于 x 的元素 while (a[++i] < x && i < r); // 从右向左寻找第一个小于或等于 x 的元素 while (a[--j] > x);
// 用于在最坏 $O(n)$ 时间内找到第 k 小的元素 template<class Type> Type Select(Type a[], int p, int r, int k){ // 1. 如果元素个数小于 75，直接排序并返回第 k 个元素 if (r - p < 75) { Sort(a, p, r); return a[p + k - 1]; }
// 2. 将数组划分为 5 个一组，找出每组的中位数并移到数组前部 for (int i = 0; i <= (r - p - 4) / 5; i++) { int s = p + 5 * i; int t = s + 4; Sort(a, s, t); // 将各组中位数交换到 a[p] 开始的连续位置 Swap(a[p + i], a[s + 2]); }
// 3. 递归寻找“中位数之中的中位数”作为基准元素 x Type x = Select(a, p, p + (r - p - 4) / 5, (r - p - 4) / 10 + 1);
// 4. 找到 x 的实际索引并将其换到 a[p]，以便调用您提供的 Partition for (int m = p; m <= r; m++) { if (a[m] == x) { Swap(a[p], a[m]); break; } }
// 5. 执行划分操作 int i = Partition(a, p, r); int j = i - p + 1; // 左半部分(含基准)的元素个数
// 6. 递归处理子问题 if (k <= j) { returnSelect(a, p, i, k); } else { returnSelect(a, i + 1, r, k - j); } }
/** * 函数功能：生成 2^k 个选手的循环赛日程表 * 参数说明：k - 选手数量为 2^k, a - 存储日程表的二维数组 */ voidTable(int k, int **a) { int n = 1; // 1. 计算总人数 n = 2^k for (int i = 1; i <= k; i++) n *= 2; // 2. 初始化第一行：第一天每个选手的对手就是自己（编号 1 到 n） for (int i = 1; i <= n; i++) a[1][i] = i;
int m = 1; // m 为当前处理的子问题规模（初始块大小） // 3. 按照分治思想，通过已有的块构造更大的块 for (int s = 1; s <= k; s++) { n /= 2; // 当前阶段需要构造的块的数量 for (int t = 1; t <= n; t++) { // 遍历并填充下方对应的方格 for (int i = m + 1; i <= 2 * m; i++) { for (int j = m + 1; j <= 2 * m; j++) { // 对角线对称填充：左上角的块复制到右下角 a[i][j + (t - 1) * m * 2] = a[i - m][j + (t - 1) * m * 2 - m]; // 对角线对称填充：右上角的块复制到左下角 a[i][j + (t - 1) * m * 2 - m] = a[i - m][j + (t - 1) * m * 2]; } } } m *= 2; } }
voidMatrixChain(int *p, int n, int **m, int **s) { // 初始化链长为 1 的情况，m[i][i] = 0 for (int i = 1; i <= n; i++) m[i][i] = 0; // r 是矩阵链的长度，从 2 开始 for (int r = 2; r <= n; r++) { // i 是链的起始位置 for (int i = 1; i <= n - r + 1; i++) { // j 是链的结束位置 int j = i + r - 1; // 初始假设在第一个位置切开 m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j]; s[i][j] = i; // 暂时记录 k=i 为最优分割点 // 循环 k 从 i+1 到 j-1 (因为 k=i 的情况已经算过了) for (int k = i+1; k < j; k++) { // 计算 k 为分割点时的成本 int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]; // 如果找到了更优的(成本更低的)分割点 k if (t < m[i][j]) { m[i][j] = t; // 更新最小成本 s[i][j] = k; // 更新最优分割点 } } } } }
/* * s[i][j] 的值为计算 A[i:j] 的最小乘次数的断开位置。 */ voidTraceback( int i, int j, int **s ) { if ( i == j ) return;
// 递归处理左子链 (A[i]...A[s[i,j]]) Traceback( i, s[i][j], s );
// 递归处理右子链 (A[s[i,j]+1]...A[j]) Traceback( s[i][j] + 1, j, s );
/* * m, n: 字符串 x 和 y 的长度 * x, y: 待比较的两个字符串（下标通常从 1 开始） * c: 存储 LCS 长度的二维数组 * b: 存储路径标记的二维数组（用于后续构造序列） */ voidLCSLength(int m, int n, char *x, char *y, int **c, int **b) { int i, j;
// 初始化边界：第一列和第一行长度设为 0 for (i = 1; i <= m; i++) c[i][0] = 0; for (i = 1; i <= n; i++) c[0][i] = 0;
// 自底向上计算每一个子问题的最优解 for (i = 1; i <= m; i++) { for (j = 1; j <= n; j++) { if (x[i] == y[j]) { // 如果当前字符相等，LCS 长度加 1 c[i][j] = c[i-1][j-1] + 1; b[i][j] = 1; // 标记 1：表示来自左上方（匹配成功） } elseif (c[i-1][j] >= c[i][j-1]) { // 如果上方格子的值更大，继承上方的值 c[i][j] = c[i-1][j]; b[i][j] = 2; // 标记 2：表示来自上方 } else { // 否则继承左方格子的值 c[i][j] = c[i][j-1]; b[i][j] = 3; // 标记 3：表示来自左方 } } } } /* * i, j: 当前扫描到的字符串位置 * x: 字符串 x * b: 存储路径标记的二维数组 */ voidLCS(int i, int j, char *x, int **b) { // 递归终止条件：到达数组边界 if (i == 0 || j == 0) return;
/** * 使用分治法递归计算最大子段和 * @param a 数组 * @param left 子数组的左边界 * @param right 子数组的右边界 * @return int left 到 right 之间的最大子段和 */ intMaxSubSum(int *a, int left, int right) { int sum = 0;
// 基本情况(Base Case)：如果只有一个元素 if (left == right) { sum = a[left] > 0 ? a[left] : 0; } else { // --- 1. 分解 (Divide) --- // 找到中点 int center = (left + right) / 2; // --- 2. 治理 (Conquer) --- // (a) 递归求“左半段”的最大和 int leftsum = MaxSubSum(a, left, center); // (b) 递归求“右半段”的最大和 int rightsum = MaxSubSum(a, center + 1, right);
// --- 3. 合并 (Combine) --- // (c) 求“跨越中点”的最大和 // (c.1) 计算包含中点的、向左延伸的最大和 (s1) int s1 = 0; int lefts = 0; for (int i = center; i >= left; i--) { lefts += a[i]; if (lefts > s1) s1 = lefts; }
// (c.2) 计算包含中点+1的、向右延伸的最大和 (s2) int s2 = 0; int rights = 0; for (int i = center + 1; i <= right; i++) { rights += a[i]; if (rights > s2) s2 = rights; }
// (c.3) 跨越中点的最大和即 s1 + s2 sum = s1 + s2;
// 比较三种情况，取最大值 if (sum < leftsum) sum = leftsum; if (sum < rightsum) sum = rightsum; } // 返回最终的最大值 return sum; }
/** * @brief 最大子段和的分治算法 - 入口函数 * @param n 数组元素个数 * @param a 数组 * @return int 整个数组的最大子段和 */ intMaxSum(int n, int *a){ // 调用递归函数，从 1 到 n (假设数组是 1-based 索引) returnMaxSubSum(a, 1, n); }
动态规划（Kadane 算法）
设 dp[i] 是以第 i 个元素结尾的最大子段和。
转移方程
对于每一个元素 a[i]，我们面临两个选择：
如果之前的子段和 dp[i−1] 是正数，那么 a[i] 加上它会变得更大。
如果 dp[i−1] 是负数，加上它反而会变小，不如直接从 a[i] 开始。
dp[i]=max(a[i],dp[i−1]+a[i])
1 2 3 4 5 6 7 8 9
intMaxSum(int n, int a[]){ int sum = 0, b = 0; for (int i = 1; i <= n; i++) { if (b > 0) b += a[i]; // 之前的贡献是正的，接上 else b = a[i]; // 之前的贡献是负的，丢弃并从当前位开始 if (b > sum) sum = b; // 记录全局出现过的最大值 } return sum; }
/* * 问题：从长度为 n 的数组 a 中，选取 m 个互不相交的连续子段，使得这 m 个子段的总和最大。 * b[i][j] 的定义：前 j 个元素中形成 i 个子段，且第 i 个子段【必须包含】第 j 个元素 a[j] 时的最大和。 */ intMaxSum(int m, int n, int *a) { // --- 1. 边界情况处理 --- // 如果数组总长度不够分 m 段，或者要求的段数不合法，直接返回 0 if (n < m || m < 1) return0;
// --- 2. 初始化 DP 表 --- // b[i][j] 记录状态。i 范围 [0, m], j 范围 [0, n] int **b = newint *[m + 1]; for (int i = 0; i <= m; i++) { b[i] = newint[n + 1]; b[i][0] = 0; // 当没有元素时，和为 0 }
// --- 3. 动态规划主体逻辑 --- for (int i = 1; i <= m; i++) { // 外层循环：当前正在处理第 i 个子段 for (int j = i; j <= n - m + i; j++) { // 中层循环：当前考虑数组的前 j 个元素 // 提示：j 的上限设为 n-m+i 是因为要给后面还没分的段留出足够的元素位置 if (j > i) { //方案 A：让 a[j] 紧跟在 a[j-1] 后面，合并到当前的第 i 段。 //逻辑：此时的和就是“包含 a[j-1] 的第 i 段最大和” + a[j]。 b[i][j] = b[i][j - 1] + a[j]; //方案 B：让 a[j] 独立作为第 i 段的开头。 //逻辑：这意味着我们要从前面（1 到 j-1 范围内）找出一个已经分好 i-1 段的最优结果。 //这个 k 循环就是在寻找：前 k 个元素分出 i-1 段的最大和。 for (int k = i - 1; k < j; k++) { // 如果“之前的 i-1 段最优和 + a[j]”比当前的方案 A 更好，就更新它 // 注意：这里 k < j，如果 k < j-1，中间的元素就被“跳过”了 if (b[i][j] < b[i - 1][k] + a[j]) { b[i][j] = b[i - 1][k] + a[j]; } } } else { //特殊情况：j == i //当元素个数正好等于段数时，每个元素必须独自成为一段，没得选。 b[i][j] = b[i - 1][j - 1] + a[j]; } } }
// --- 4. 统计最终结果 --- /* * 因为 b[m][j] 要求第 j 个元素必须包含在第 m 段内， * 但最优解的第 m 段可能在数组的任何位置结束（比如数组末尾几个是负数，我们会跳过它们）。 * 所以我们需要遍历 b[m][m] 到 b[m][n]，找出其中的最大值。 */ int sum = 0; for (int j = m; j <= n; j++) { if (sum < b[m][j]) { sum = b[m][j]; } }
/** * @brief 计算凸多边形的最优三角剖分（最小权值和） * @param n 多边形的边数 (顶点为 v0, v1, ..., vn) * @param t (传出参数) 存储 t[i][j] (子问题 {vi-1...vj} 的最优解) 的表 * @param s (传出参数) 存储 s[i][j] (最优分割点 k) 的表 * @note w(i, j, k) 是一个假定的函数，用于计算三角形 {vi, vj, vk} 的权值 */ voidMinWeightTriangulation(int n, Type **t, int **s) { // 1. 初始化：t[i][i] = 0 (基本情况，只有一条边 {vi-1, vi}) for (int i = 1; i <= n; i++) t[i][i] = 0;
// 2. 按“链长” r 循环 (r+1 是子多边形的顶点数) for (int r = 2; r <= n; r++) { // 3. 循环子问题的起始点 i for (int i = 1; i <= n - r + 1; i++) { // 4. 计算子问题的结束点 j int j = i + r - 1;
// 使用数组 w 中的权值初始化堆 // n 个叶子节点 Q.Initialize(w, n, n);
// 用于临时存储取出的两个最小节点 Huffman<Type> x, y; // z 用于存储合并后的新节点 Huffman<Type> z;
// 反复合并最小频率树 // n 个节点需要合并 n-1 次才能变成一棵树 for (int i = 1; i < n; i++) { // 1. 从堆中取出当前权值最小的节点，存入 x Q.DeleteMin(x); // 2. 从堆中取出当前权值次小的节点，存入 y Q.DeleteMin(y);
// 3. 合并：创建一个新节点 z // z 的左孩子是 x，右孩子是 y z.MakeTree(0, x.tree, y.tree);
// 4. 新节点的权值 = 两个子节点权值之和 x.weight += y.weight; // 这里复用了 x 的 weight 字段来存新权值 x.tree = z; // 更新 x 的树指针指向新生成的树 z
// 步骤 3: 更新剩余未访问节点到生成树的距离 for (int k = 2; k <= n; k++) { // 如果新加入的节点 j 到 k 的距离比 k 原有的 lowcost 更小 if((c[j][k] < lowcost[k]) && (!s[k])) { lowcost[k] = c[j][k]; // 更新最小权重 closest[k] = j; // 更新 k 的连接点为 j } } }
时间复杂度：O(n2)
Krustal 算法
使用了最小堆来选取边，并结合并查集来检测环路。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
// 循环条件：堆中还有边(e) 且 已选入生成树的边数小于 n-1 while( e && k < n-1){ EdgeNode<int>x; // 1. 贪心策略：从最小堆 H 中取出当前权值最小的边 H.DeleteMin(x); e--; // 剩余边数减一 // 2. 查找根节点：利用并查集查找两个端点 u, v 所属的连通分量 int a = U.Find(x.u); int b = U.Find(x.v); // 3. 判环：如果 a != b，说明两点不在同一个集合，连接它们不会形成环 if(a != b) { t[k++] = x; // 将该边加入结果数组 t U.Union(a,b); // 4. 合并：将U中两个联通分支a和b连接起来，视为已连通 } }
当图的边数为e时，Kruskal算法所需的计算时间是O(eloge)。当 e=Ω(n2) 时（稠密图），Kruskal 算法比 Prim 算法差，但当 e=o(n2) （稀疏图）时，Kruskal 算法却比 Prim 算法好得多。
多机调度问题
最长处理时间作业优先
当n≤m时，只要将机器 i 的 [0,ti] 时间区间分配给作业即可
当n>m时，首先将n个作业依其所需的处理时间从大到小 排序，依此顺序将作业分配给空闲的处理机
算法所需时间为 O(nlogn)
