第3章 模拟法
3.1 模拟法概述
模拟法设计思想
模拟法通过将现实问题抽象成计算机可识别的符号与操作，按逻辑顺序“模拟”其过程，从而得到结果；它不依赖复杂公式或高深技巧，只需理清问题背景与实现步骤即可。
示例：鸡兔同笼问题
题目
笼中有若干鸡和兔，鸡有 2 只脚，兔有 4 只脚。给定脚的总数 n，求笼中动物数的最大值与最小值。
思路
-
当所有动物都假设为鸡时，数量最大；
-
当尽量多假设为兔时，数量最小；
-
分别根据 n 的奇偶性以及能否被 4 整除进行处理。
伪代码
函数 Feets(n, maxNum, minNum):如果 n % 2 ≠ 0:maxNum = 0minNum = 0否则如果 n % 4 == 0:maxNum = n / 2minNum = n / 4否则:maxNum = n / 2minNum = (n - 2) / 4 + 1返回 maxNum, minNum
3.2 数学问题中的模拟法
3.2.1 约瑟夫环问题
题目
n 个人围成一圈，从 1 开始报数，报到 m 的人出列，下一次从下一个人继续，直至所有人出列；求出列顺序或最后剩余的编号。
思路
-
用数组
removed[0…n-1]记录某人是否已出列； -
利用
i = (i + 1) % n实现环形遍历； -
每次计数到 m 且该位置未出列时，标记出列并继续。
伪代码
函数 Josephus(n, m):removed = [0] * ncount = 0, i = -1, numOut = 0当 numOut < n - 1:count = 0当 count < m:i = (i + 1) % n如果 removed[i] == 0:count += 1removed[i] = 1numOut += 1返回 所有 removed[i] == 0 的 i + 1 列表
3.2.2 埃拉托色尼筛法
题目
求区间 [1, n] 内所有素数。
思路
-
假设所有数初始为素数；
-
从 2 开始，将其倍数标记为合数；
-
剩余未标记的即为素数。
伪代码
函数 EratoSieve(n):A[1…n] 全设为 0 （0 表示素数）对 i 从 2 到 ⌊n/2⌋:如果 A[i] == 0:对 j 从 2 到 ⌊n/i⌋:A[i * j] = 1 （标记合数）返回 所有 A[i] == 0 的 i
3.3 排序问题中的模拟法
3.3.1 计数排序
题目
待排序元素均为 [0, k] 范围内的整数，通过统计方式直接放置到正确位置。
思路
-
统计各值出现次数；
-
计算累加后的位置边界；
-
从后向前遍历原序列，将元素按边界放入结果数组。
伪代码
函数 CountSort(A, n, k):count[0…k] = 0对 每个 x in A: count[x] += 1对 i 从 1 到 k: count[i] += count[i - 1]B[n]对 i 从 n-1 到 0:B[count[A[i]] - 1] = A[i]count[A[i]] -= 1返回 B
3.3.2 颜色排序
题目
数组元素为红（1）、绿（2）、蓝（3），按红→绿→蓝顺序重排。
思路
维护三个指针：
-
i：红色区间右边界； -
j：当前扫描位置； -
k：蓝色区间左边界。
遍历时根据A[j]与对应区间交换位置。
伪代码
函数 ColorSort(A, n):i = 0, j = 0, k = n - 1当 j ≤ k:如果 A[j] == 1:交换 A[i] 和 A[j]; i++; j++否则 如果 A[j] == 2:j++否则: // A[j] == 3交换 A[j] 和 A[k]; k--返回 A
3.4 拓展与演练
3.4.1 装箱问题
题目
有 6 种型号的正方体产品，边长分别为 1…6，按给定数量装入边长 6 的箱子，求最少箱数。
思路
-
优先装 6×6、5×5、4×4、3×3 型号；
-
统计剩余 2×2 和 1×1 空间，装入相应型号；
-
根据剩余空间与产品数量计算额外箱数。
伪代码
函数 Packing(k1…k6):n = k6 + k5 + k4 + (k3 + 3) // 4x = 5*k4 + 剩余2×2空位数(由 k3 % 4 确定)如果 k2 > x: n += ceil((k2 - x) / 9)y = 36*n - (k6*216 + k5*125 + k4*64 + k3*27 + k2*4 + k1)如果 k1 > y: n += ceil((k1 - y) / 36)返回 n
3.4.2 数字回转方阵
题目
构造 n 阶方阵，按“偶数层先列后行，奇数层先行后列”规则填入 1～n²。
思路
利用双层循环和下标交替增减，分别处理奇偶层即可。
伪代码
函数 Full(n):初始化 z[n][n]number = 1对 layer 从 0 到 ⌊(n-1)/2⌋:如果 layer % 2 == 0: // 偶数层从 i=layer 到 n-layer-1: z[i][layer] = number; number++从 j=layer+1 到 n-layer-1: z[n-layer-1][j] = number; number++否则: // 奇数层从 j=layer 到 n-layer-1: z[layer][j] = number; number++从 i=layer+1 到 n-layer-1: z[i][n-layer-1] = number; number++返回 z