第模拟法
3
章
模拟法(simulationmethod)通常基于问题描述,或完成简单的建模,
或模拟过程的实现,是最简单的算法设计技术。有些问题很难通过数学推
导找到规律,一般采用模拟法直接模拟问题中事物的变化过程,从而完成
相应的任务。
3.概
1
述
3.1.1
模拟法的设计思想课件3-
1
用模拟法求解问题的基本思想是对问题进行抽象,将现实世界的问题
映射成计算机能够识别的符号表示,将事物之间的关系映射成运算或逻辑
控制。模拟法求解的问题通常是对某一类事件进行描述,然后经过简单计
算给出符合要求的结果。
模拟法是算法设计的基本功,没有复杂的公式和技巧,只需读懂问题、
明确要求,照着逻辑整理步骤,基本都可以完成。需要注意的是,有些问题
的背景错综复杂,如果没有理顺逻辑就可能步入歧途。
3.1.2
一个简单的例子
:
鸡兔同笼问题
【问题】笼子里有若干只鸡和兔子,鸡有两只脚,兔子有四只脚,没有
例外情况。已知笼子里脚的数量,问笼子里至多有多少只动物? 至少有多
少只动物?
【想法】对于同样数目的动物,鸡脚的总数肯定比兔子脚的总数要
少,因此在计算笼子里至多有多少只动物时,应该把脚都算作鸡脚,在计算
笼子里至少有多少只动物时,应该尽可能把脚都算作兔子脚。
【算法】设函数Fets实现鸡兔同笼问题,算法如下。
算法:鸡兔同笼问题Fets
输入:脚的数量
n
34 算法设计与分析(第3 版)
输出:至多的动物数maxNum,至少的动物数minNum
1.如果n 是奇数,则没有满足要求的解,maxNum=0,minNum=0;
2.如果n 是偶数且能被4整除,则maxNum=n/2,minNum=n/4;
3.如果n 是偶数但不能被4整除,则maxNum=n/2,minNum=(n-2)/4+1;
4.输出maxNum 和minNum;
【算法分析】 算法Feets只是进行了简单的判断和赋值,时间复杂度是O(1)。
【算法实现】 设形参maxNum 和minNum 以传引用方式接收求得的结果,程序
如下。
void Feets(int n, int &maxNum, int &minNum)
{
if (n % 2 != 0) {maxNum = 0; minNum = 0;}
else if (n % 4 == 0) {maxNum = n/2; minNum = n/4;}
else {maxNum = n/2; minNum = (n-2)/4 + 1;}
}
3.2 数学问题中的模拟法
3.2.1 约瑟夫环问题
【问题】 约瑟夫环问题(Josephuscircleproblem)由古罗马史学家约瑟夫提出,他参
加并记录了公元66—70年犹太人反抗罗马的起义。约瑟夫作为一个将军,守住了裘达伯
特城达47天之久。在城市沦陷后,他和40名视死如归的将士在一个洞穴中避难,这些反
抗者表决说“要投降毋宁死”。于是,约瑟夫建议每个人轮流杀死他旁边的人,而这个顺序
是由抽签决定的。约瑟夫有预谋地抓到了最后一签,并且,作为洞穴中的两个幸存者之
一,他说服了同伴一起投降了罗马。
【想法】 将参与抽签的人从1至n 进行编号并构成一个环,从而将约瑟夫环问题抽
象为如图3-1所示数据模型。假设密码是m ,从第1个人开始报数,报到m 时停止报数,
报m 的人出环;再从他的下一个人起重新报数,报到m 时停止报数,报m 的人出环。如
此下去,直至所有人全部出环。当任意给定n 和m 后,求n 个人出环的次序。
图3-1 约瑟夫环问题的数据模型(n=5,m =3时的出圈次序:3,1,5,2,4)
【算法】 设函数Joseph求解约瑟夫环问题,用数组r[n]存储n 个人是否出列,下标
源代码3-1
课件3-2
第3 章 模拟法 35
表示人的编号,从1开始数到密码m 则将其出列。如果编号i 的人出列则将数组r[i]置
为1,用求模运算%实现下标在数组内循环增1。算法如下。
算法:约瑟夫环问题Joseph
输入:参与游戏的人数n,密码m
输出:最后一个出列的编号
1.初始化数组r[n]={0};
2.计数器count=0;下标i=-1;出列人数num=0;
3.重复下述操作直到数组r[n]仅剩一个人:
3.1当count< m 时重复下述操作:
3.1.1i=(i+1)% n;
3.1.2如果r[i]未出列,则计数器count++;
3.2令r[i]=1;num++;
4.查找并返回仅剩的编号;
【算法分析】 步骤3在数组r[n]中反复查找待出列编号,外循环执行n-1次,内循
环执行m 次,时间复杂度为O(n×m )。
【算法实现】 设函数Joseph求解约瑟夫环问题,程序如下。
int Joseph(int r[ ], int n, int m)
{
int count, i = -1, num = 0;
while (num < n - 1)
{
count = 0;
while (count < m) //查找报到m 的人
{
i = (i+1) % n;
if (r[i] != 1) count++;
}
r[i] = 1; num++; //标记出列的人
}
for (i = 0; i < n; i++)
if (r[i] == 0) return i+1; //返回编号
}
3.2.2 埃拉托色尼筛法
【问题】 埃拉托色尼筛法(thesieveofEratosthenes)简称埃氏筛法,是古希腊数学
家埃拉托色尼提出的算法,用于求一定区间内的所有素数。算法的基本思想是,从区间
[1,n]内的所有数中去掉所有合数,剩下的就是所有素数。判断合数的方法是从2开始
依次过筛,如果是2的倍数则该数不是素数,进行标记处理,直至将n/2过筛,将所有合数
源代码3-2
36 算法设计与分析(第3 版)
打上标记。
【想法】 假设有一个筛子存放整数1~n,依次将2,3,5,…的倍数筛去(标记),最后
没有打上标记的数都是素数。埃拉托色尼筛法的计算过程如图3-2所示。
图3-2 埃拉托色尼筛法的计算过程
【算法】 设数组A[n]表示筛子,元素值全部初始化为0,依次将下标是2,3,5,…倍
数的元素值置1进行标记处理,最后所有元素值为0对应的下标都是素数,算法如下。
算法:埃拉托色尼筛EratoSieve
输入:待确定素数的范围n,数组A[n]
输出:区间[1,n]的所有素数
1.循环变量i 从2至n/2重复执行下述操作:
1.1如果A[i]不等于0,说明整数i 不是素数,转步骤1.3取下一个素数;
1.2将所有下标是i 的倍数的元素值置为1;
1.3i++;
2.输出数组A[n]中所有元素值为0对应的下标;
【算法分析】 埃拉托色尼筛法实际上是一种空间换时间的算法优化,对于判断单个
数的素数性质来说,相对于朴素的算法没有优化,但是对于求解某一区间的素数问题,埃
拉托色尼筛法可以很快打印一份素数表,时间复杂度只有O(nloglogn)。
【算法实现】 设函数EratoSieve实现埃拉托色尼筛法,程序如下。
void EratoSieve(int A[ ], int n)
{
int i, j;
for (i = 2; i <= n/2; i++)
{
if (A[i] != 0) continue;
else
{
for (j = 2; i * j <= n; j++)
源代码3-3
第3 章 模拟法 37
A[i*j] = 1;
}
}
}
3.3 排序问题中的模拟法
3.3.1 计数排序
【问题】 假设待排序记录均为整数且取自区间[0,k],计数排序①(countsort)的基
本思想是对每一个记录x,确定小于x 的记录个数,然后直接将x 放在应该的位置。例
如,小于x 的记录个数是10,则x 就位于第11个位置。
【想法】 对于待排序序列A[n]={2,1,5,2,4,3,0,5,3,2},k=5,首先统计值
为i(0≤i≤k)的记录个数存储在num[i]中,则num[k]={1,1,3,2,1,2},再统计小
于等于i(1≤i≤k)的记录个数存储在num[i]中,则num[k]={1,2,5,7,8,10},最后
反向读取数组A[n]填到数组B中,例如读取A[9]的值是2,则将num[2]减1,然后将2
填到B[4]中,如图3-3所示。注意,统计小于i(1≤i≤k)的记录个数不能就地进行(利用
数组num),需要再设一个数组存放小于i 的记录个数,就可以正向读取数组A[n]。
图3-3 计数排序过程
【算法】 设函数CountSort实现计数排序,数组num[k+1]存储每个记录出现的次
数以及小于等于值为i 的记录个数,算法如下。
算法:计数排序CountSort
输入:待排序记录序列A[n],记录的取值区间k
输出:排序数组B[n]
1.统计值为i 的记录个数存入num[i];
2.统计小于等于i 的记录个数存入num[i];
3.反向填充目标数组,将A[i]放在B[--num[A[i]]]中;
4.输出数组B[n];
① 计数排序算法在1954年由HaroldH.Seward提出,可以在线性时间对取值范围为某一区间的记录序列进行排序。
课件3-3
38 算法设计与分析(第3 版)
【算法分析】 计数排序是一种以空间换时间的排序算法,并且只适用于对一定范围
内的整数进行排序,时间复杂度为O(n+k),其中k 为序列中整数的范围。
【算法实现】 计数排序的关键在于确定待排序记录A[i]在目标数组B[n]中的位
置,由于数组元素num[i]存储的是A[n]中小于等于i 的记录个数,所以填充数组B[n]
时要反向读取A[n]。程序如下。
void CountSort(int A[ ], int n, int k, int B[ ])
{
int i, num[k+1] = {0};
for(i = 0; i < n; i++)
num[A[i]]++;
for (i = 1; i <= k; i++)
num[i] = num[i] + num[i-1];
for (i = n-1; i >= 0; i--)
B[--num[A[i]]] = A[i];
}
3.3.2 颜色排序
【问题】 现有Red、Green和Blue三种不同颜色(色彩中不能再分解的三种颜色,称
为三原色)的小球,乱序排列在一起,请按照Red、Green和Blue顺序重新排列这些小球,
使得相同颜色的小球排在一起。
【想法】 设数组a[n]存储Red、Green和Blue三种元素,设置三个参数i、j、k,其中
i 之前的元素(不包括a[i])全部为Red;k 之后的元素(不包括a[k])全部为Blue;i 和j
之间的元素(不包括a[j])全部为Green;j 指向当前正在处理的元素。首先将i 初始化为
0,k 初始化为n-1,j 初始化为0。然后j 从前向后扫描,在扫描过程中根据a[j]的颜色,
将其交换到序列的前面或后面,当j 等于k 时,算法结束。颜色排序的求解思想如图3-4
所示。
图3-4 颜色排序的求解思想
注意,当j 扫描到Red时,将a[i]和a[j]交换,只有当前面全部是Red时,交换到位
置j 的元素是Red,否则交换到位置j 的元素一定是Green,因此交换后j 应该加1;当j
扫描到Blue时,将a[k]和a[j]交换,Red、Green和Blue均有可能交换到位置j,则a[j]需
要再次判断,因此交换后不能改变j 的值。
【算法】 设数组a[n]有Red、Green和Blue三种元素,函数ColorSort实现颜色重排
问题,算法如下。
源代码3-4
第3 章 模拟法 39
算法:颜色排序ColorSort
输入:待排序记录序列a[n]
输出:排好序的数组a[n]
1.初始化i=0;k=n-1;j=0;
2.当j≤k时,依次考查元素a[j],有以下三种情况:
(1)如果a[j]是Red,则交换a[i]和a[j];i++;j++;
(2)如果a[j]是Green,则j++;
(3)如果a[j]是Blue,则交换a[k]和a[j];k--;
【算法分析】 由于下标j 和k 整体将数组扫描一遍,因此时间复杂度为O(n)。
【算法实现】 由于数组a[n]只有三种元素,假设Red、Green和Blue三种颜色分别
用1、2、3来代替,程序如下。
void ColorSort(int a[ ], int n)
{
int i = 0, k = n - 1, j = 0, temp;
while (j <= k)
switch (a[j]) //考查当前元素
{
case 1: temp = a[i]; a[i] = a[j]; a[j] = temp; i++; j++; break;
case 2: j++; break;
case 3: temp = a[j]; a[j] = a[k]; a[k] = temp; k--; break;
}
}
3.4 拓展与演练
3.4.1 装箱问题
【问题】 有一个工厂制造的产品形状都是长方体,一共有6种型号,每种型号长方体
的长和宽分别是1×1、2×2、3×3、4×4、5×5、6×6,高都是h。这些产品使用统一规格
的箱子进行包装,箱子的长、宽和高分别是6、6和h。对于每个订单工厂希望用最少的箱
子进行包装。每个订单包括用空格分开的6个整数,分别代表这6种型号的产品数量。
输出是包装需要箱子的个数。
【想法】 这个问题很难建立一个数学模型,只能模拟包装过程,分析装入6种产品后
箱子的剩余空间。装箱情况分析如表3-1所示。
源代码3-5
课件3-4
40 算法设计与分析(第3 版)
表3-1 6种产品占用箱子与剩余空间的装箱情况分析
1个箱子容纳产品剩余空间的装载情况
产品个数2×2 1×1 解 释
6×6 1 0 0 无剩余空间
5×5 1 0 11 11个长宽为1的产品
4×4 1 5 0 5个长宽为2的产品
3×3 1 5 7 5个长宽为2的产品和7个长宽为1的产品
3×3 2 3 6 3个长宽为2的产品和6个长宽为1的产品
3×3 3 1 5 1个长宽为2的产品和5个长宽为1的产品
3×3 4 0 0 无剩余空间
2×2 9 0 0 无剩余空间
1×1 36 0 0 无剩余空间
【算法】 设k1、k2、k3、k4、k5 和k6 分别表示6种型号的产品数量,x 和y 分别表示
长宽为2和1的空位数量,n 表示需要的箱子个数,算法如下。
算法:装箱问题Packing
输入:6种型号的产品数量k1、k2、k3、k4、k5、k6
输出:箱子个数n
1.n=装入长宽为3×3、4×4、5×5、6×6所需箱子数;
2.x=n 个箱子剩余2×2的空位数;
3.如果k2>x,则n=n+(k2-x 个产品需要的箱子数);
4.y=n 个箱子剩余1×1的空位数;
5.如果k1>y,则n=n+(k1-y 个产品需要的箱子数);
6.输出箱子个数n;
【算法分析】 算法Packing所有操作步骤都是简单的计算,时间复杂度为O(1)。
【算法实现】 设变量k1、k2、k3、k4、k5和k6分别表示6种型号的产品数量,变量x
和y分别表示长宽为2和1的空位数量,变量n表示需要的箱子个数。设数组p2[4]存
储装入3×3的产品个数分别是4、1、2、3时箱子剩余2×2的空位数。注意,程序中所有
的整除都应该保证向上取整。程序如下。
int Packing(int k1, int k2, int k3, int k4, int k5, int k6)
{
int n, x, y;
int p2[4] = {0, 5, 3, 1};
n = (k3 + 3)/4 + k4 + k5 + k6;
x = 5 * k4 + p2[k3 % 4];
if (k2 > x) n += (k2 - x + 8) / 9;
源代码3-6
第3 章 模拟法 41
y = 36 * n - 36 * k6 - 25 * k5 - 16 * k4 - 9 * k3 - 4 * k2;
if (k1 > y) n += (k1 - y + 35) / 36;
return n;
}
3.4.2 数字回转方阵
【问题】 n 阶数字回转方阵是将数字1置于方阵的左上角,然后从1开始递增,将
n2 个整数填写到n 阶方阵中,偶数层从第1行开始,先向下再折转向左,奇数层从第1列
开始先向右再折转向上,呈首尾相接,图3-5所示为一个5阶数字回转方阵。
图3-5 5阶数字回转方阵
【想法】 根据问题描述的填数规则,找到下标变化规律,
用模拟法直接求解。对于方阵的偶数行和列,填数的起始位置
是(1,i),然后列号不变行号加1,至位置(i,i)时折转,行号不
变列号减1,直至位置(i,1);对于方阵的奇数行和列,填数的
起始位置是(j,1),然后行号不变列号加1,至位置(j,j)时折
转,列号不变行号减1,直至位置(1,j)。
【算法】 设函数Full实现填写数字回转方阵,注意数组下
标从0开始,算法如下。
算法:数字回转方阵Full
输入:方阵的阶数n
输出:数字回转方阵z[n][n]
1.z[0][0]=1,number=2;
2.for(i=0,j=1;i< n&&j< n;);
2.1填写偶数层:
2.1.1填数直至i等于j:
z[i++][j]=number++;
2.1.2填数直至j等于0:
z[i][j--]=number++;
2.2填写奇数层:
2.2.1填数直至i等于j:
z[i][++j]=number++;
2.2.2填数直至i等于0:
z[i--][j]=number++;
【算法分析】 算法Full需要依次填写矩阵的每一个元素,时间复杂度是O(n2)。
【算法实现】 注意每一层填数后都要调整下标,程序如下。
void Full(int z[100][100], int n)
{
int number, i, j; 源代码3-7
42 算法设计与分析(第3 版)
z[0][0] = 1; number = 2;
for (i = 0, j = 1; i < n && j < n; ) //依次填写每一层
{
while (i < j)
z[i++][j] = number++;
while (j >= 0)
z[i][j--] = number++;
i++; j = 0;
while (i > j)
z[i][j++] = number++;
while (i >= 0)
z[i--][j] = number++;
j++; i = 0;
}
}
实验3 埃氏筛法的优化
【实验题目】 对于埃拉托色尼筛法,观察图3-2,很多合数被标记了不止1次,例如合
数6,在将2过筛时标记了1次,将3过筛时又标记一次,造成了不必要的重复标记。请
改进埃拉托色尼筛法,使得在线性时间内完成所有合数的标记。
【实验要求】 对于优化的埃拉托色尼筛法,要保证两点:①合数一定被标记;②每
个合数都没有被重复标记。
【实验提示】 注意到任何合数都能表示成一系列素数的乘积,如果保证每个合数只
被其最小质因数筛去,就能够达到不重复标记。对于整数i,对所有不超过i 的素数p,将
i *p 标记为合数,如果p 是i 的因子则将整数i 进行标记并停止过筛,直至p 等于i,说
明整数i 是素数。
习 题 3
1.如果一个十进制的正整数能够被7整除,或者某个位置的数字是7,则称该正整数
为与7相关的数。求小于n(n<100)的所有与7无关的正整数的平方和。
2.对于一元二次方程ax2+bx+c=0,给定系数a、b 和c,求方程的根。要求所有实
数精确到小数点后5位。
3.恺撒加密由古罗马恺撒大帝在其政府的秘密通信中使用而得名,其基本思想是:
将待加密信息(称为明文)的每个字母在字母表中向后移动常量key(称为密钥),得到加
密信息(称为密文)。假设字母表为英文字母表,对于给定的明文和密钥,请给出恺撒加密
后的密文。
4.校门外的树。校门外长度为L 的马路上有一排树,每两棵相邻的树之间的距离都
43
第3章模拟法
是1m 。可以把马路看成一个数轴,校门口在数轴0的位置,另一端在
L
的位置,数轴上
每个整数点都有一棵树。马路上有一些区域要用来修建地铁,这些区域用数轴上的半开
区间[s,t)来表示,已知
s
和
t
都是整数,且区域之间可能有部分重叠。由于修建地铁要
把区域中的树全部移走,问马路上还剩下多少棵树?
5.对于约瑟夫环问题, 请修改3.1节给出的算法。
假设每个人持有的密码不同,2.
6.桥牌共52张,没有大小王,按E、S、W、N的顺序把52
张牌随机发给四个玩家,请列出每个玩家的发牌情况。
7.定义
n
阶间断折叠方阵是把n2 个整数折叠填写到
n
阶
方阵中,起始数1置于方阵的左上角,然后从起始数开始递增,
每一层从第1行开始,先向下再折转向左,层层折叠地排列为
间断折叠方阵。图3-6所示为5阶间断折叠方阵。请构造并
输出任意
n
阶间断折叠方阵。图3-
6
5阶间断折叠方阵
8.泊松分酒。法国数学家泊松(Poison)提出的分酒趣
题:有一瓶12品脱(容量单位)的酒,同时有容积为5品脱和8品脱的空杯各一个,借助
这两个空杯,如何将这瓶12品脱的酒平分?