1、3.1.1 模拟法的设计思想模拟法通常对某一类事件进行描述，然后经过简单计算给出符合要求的结果。有些问题背景错综复杂，逻辑没有理顺清楚就可能步入歧途用模拟法求解问题的基本思想是对问题进行抽象（1）将现实世界的问题映射成计算机能够识别的符号表示（2）将事物之间的关系映射成运算或逻辑控制模拟法是算法设计的基本功，没有复杂的公式和技巧，只需读懂问题明确要求、照着逻辑整理步骤，基本都可以完成。3.1.2 一个简单的例子鸡兔同笼问题【问题】笼子里有若干只鸡和兔子，鸡有两只脚、兔子有四只脚，没有例外情况。已知笼子里脚的个数，问笼子里至多有多少只动物？至少有多少只动物？【想法】对于同样数目的动物，鸡脚的总数
2、肯定比兔子脚的总数要少，因此在计算笼子里至多有多少只动物时，应该把脚都算作鸡脚，在计算笼子里至少有多少只动物时，应该尽可能把脚都算作兔子脚。【算法】设函数Feets实现鸡兔同笼问题，算法如下：算法：鸡兔同笼问题Feets输入：脚的个数 n输出：至多的动物个数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；3.
3、1.2 一个简单的例子鸡兔同笼问题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;【算法实现】设形参maxNum和minNum以传引用方式接收求得的结果，程序如下：时间复杂度？O(1)v第 3 章 模拟法3-2 数学问题中的模拟法3.2.1 约瑟夫环问题【问题】约瑟夫环问题由古罗马史学家约瑟夫（Josephus）提出，他参加并记录了公元6670年犹太人反抗罗马的起义。在城市
4、沦陷之后，他和40名死硬的将士在附近的一个洞穴中避难。这些起义者表决说“要投降毋宁死”。于是，约瑟夫建议每个人轮流杀死他旁边的人，而这个顺序是由抽签决定的。约瑟夫有预谋地抓到了最后一签，并且，作为洞穴中的两个幸存者之一，他说服了他原先的牺牲品一起投降了罗马。3.2.1 约瑟夫环问题【想法】设 n(n0)个人围成一个环，n 个人的编号分别为1，2，n，从第 1 个人开始报数，报到 m 时停止报数，报 m 的人出环，再从他的下一个人起重新报数，报到 m 时停止报数，报m的人出环，如此下去，直到所有人全部出环为止。对于任意给定 n 和 m，求 n 个人出环的次序。如何存储这种环状线性结构，并求解约瑟
5、夫环的出环次序呢？12354出环的顺序是：3 1 5 2 4例如，n=5,m=3，则3.2.1 约瑟夫环问题【算法】设函数Joseph求解约瑟夫环问题，用数组 rn 存储 n 个人是否出列，下标表示人的编号，从 1 开始数到密码 m 则将其出列，如果编号 i 的人出列则将数组 ri 置为 1，用求模运算%实现下标在数组内循环增 1。算法如下：算法：约瑟夫环问题Joseph输入：参与游戏的人数 n，密码 m输出：最后一个出列的编号 1.初始化数组 rn=0；2.计数器 count=0；下标 i=-1；出列人数 num=0；3.重复下述操作直到数组 rn 中仅剩一个人：3.1 当 count m
6、时重复下述操作：3.1.1 i=(i+1)%n；3.1.2 如果 ri 未出列，则计数器 count+；3.2 令 ri=1；num+；4.查找并返回仅剩的编号；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(ri!=1)count+;ri=1;num+;/标记出列的人 for(i=0;i n;i+)if(ri=0)return i+1;/返回编号【算法实现】设函数Joseph求解约瑟夫环问题，程序如下：时间复杂度？O(nm)n
7、-1次m次3.2.1 约瑟夫环问题3.2.2 埃拉托色尼筛法【问题】埃拉托色尼筛法简称埃氏筛法，基本思想是，假定区间1,n内的所有数都是素数，再去掉所有合数，剩下的就是所有素数。判断合数的方法是从 2 开始依次过筛，如果是 2 的倍数则该数不是素数，进行标记处理，直至将 n/2 过筛，将所有合数打上标记。【想法】假设有一个筛子存放整数 1n，依次将 2、3、5、的倍数筛去（标记），最后没有打上标记的数都是素数。0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 n设置筛子 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0筛掉 2 的倍数 0 0 0 0
8、 1 0 1 0 1 0 1 0 1 0 1 0 0筛掉 3 的倍数 0 0 0 0 1 0 1 0 1 1 1 0 1 0 1 1 0筛掉 5 的倍数 0 0 0 0 1 0 1 0 1 1 1 0 1 0 1 1 03.2.2 埃拉托色尼筛法【算法】设数组 An 表示筛子，元素值全部初始化为 0，依次将下标是 2、3、5、倍数的元素值置 1 进行标记处理，最后所有元素值为 0 对应的下标都是素数。算法如下：算法：埃拉托色尼筛EratoSieve输入：待确定素数的范围 n，数组 An输出：区间1,n的所有素数 1.循环变量 i 从 2 n/2 重复执行下述操作：1.1 如果 Ai 不等于 0
9、，说明整数 i 不是素数，转步骤1.3取下一个素数；1.2 将所有下标是 i 的倍数的元素值置为 1；1.3 i+；2.输出数组 An 中所有元素值为 0 对应的下标；void EratoSieve(int A,int n)int i,j;for(i=2;i=n/2;i+)if(Ai!=0)continue;else for(j=2;i*j=n;j+)Ai*j=1;【算法实现】设函数EratoSieve实现埃拉托色尼筛法，程序如下：时间复杂度？O(nlog logn)3.2.2 埃拉托色尼筛法v第 3 章 模拟法3-3 排序问题中的模拟法3.3.1 计数排序【问题】假设待排序记录均为整数且取自
10、区间0,k，计数排序基本思想是对每一个记录 x，确定小于 x 的记录个数，然后直接将 x 放在应该的位置。例如，小于 x 的记录个数是 10，则 x 就位于第 11 个位置。【想法】对于待排序序列An=2,1,5,2,4,3,0,5,3,2，k=5，第一步：统计值为 i（1 i k）的记录个数存储在 numi中 第二步：统计小于等于i（1 i k）的记录个数存储在 numi中 第三步：反向读取数组 An 填到数组 B中3.3.1 计数排序为什么反向读取数组An呢？统计小于 i（1ik）的记录个数不能就地进行，需要再设一个数组存放小于 i 的记录个数，就可以正向读取数组 An。【算法】设函数Co
11、untSort实现计数排序，数组 numk+1 存储每个记录出现的次数以及小于等于值为 i 的记录个数，算法如下：算法：计数排序CountSort输入：待排序记录序列 An，记录的取值区间 k输出：排序数组 Bn 1.统计值为 i 的记录个数存入数组 numi；2.统计小于等于 i 的记录个数存入数组 numi；3.反向填充目标数组，将 Ai 放在数组 B-numAi 中；4.输出数组 Bn；3.3.1 计数排序void CountSort(int A,int n,int k,int B)int i,numk+1=0;for(i=0;i n;i+)numAi+;for(i=1;i=0;i-)B
12、-numAi=Ai;时间复杂度？O(n+k)3.3.1 计数排序【算法实现】计数排序的关键在于确定待排序记录 Ai 在目标数组 Bn 中的位置，由于数组元素 numi 存储 An 中小于等于 i 的记录个数，所以填充数组 Bn时要反向读取 An。程序如下：3.3.2 颜色排序【问题】要求重新排列一个由 Red、Green 和 Blue 构成的数组，使得所有的 Red 都排在最前面，Green 排在其次，Blue 排在最后。Red Red Red Green Green Blue Blue?i j k【想法】设数组 an 存储 Red、Green 和 Blue 三种元素，设置三个参数 i、j、k
13、，其中 i 之前的元素（不包括 ai）全部为 Red；k 之后的元素（不包括 ak）全部为Blue；aj 表示当前元素。则 i 初始化为 0，k 初始化为 n-1，j 初始化为0。j 从前向后扫描，在扫描过程中根据 aj 的颜色，将其交换到序列的前面或后面，当 j 等于 k时，结束扫描。【算法】设数组 an 有 Red、Green 和 Blue 三种元素，函数ColorSort实现颜色重排问题，算法如下：算法：颜色排序ColorSort输入：待排序记录序列 an输出：排好序的数组 an 1.初始化 i=0;k=n 1;j=0;2.当j=k 时，依次考查元素 aj，有以下三种情况：（1）如果 a
14、j 是 Red，则交换 ai 和 aj；i+;j+;（2）如果 aj 是 Green，则 j+;（3）如果 aj 是 Blue，则交换 ak 和 aj；k-;3.3.2 颜色排序u到当 j 扫描到Red，将ai和aj交换，当前面出现连续个Red时，交换到位置 j的元素是Red，否则交换到位置 j 的元素一定是Green，交换后 j 应该加 1；u当 j 扫描到Blue，将ak和aj交换，Red、Green和Blue均有可能交换到位置 j，则aj需要再次判断，交换后不能改变 j。Red Red Red Green Green Blue Blue?i j kvoid ColorSort(int a
15、,int n)int i=0,k=n-1,j=0,temp;while(j=k)switch(aj)/考查当前元素 case 1:temp=ai;ai=aj;aj=temp;i+;j+;break;case 2:j+;break;case 3:temp=aj;aj=ak;ak=temp;k-;break;【算法实现】由于数组 an 只有三种元素，假设 Red、Green 和 Blue 三种颜色分别用 1、2、3来代替，程序如下：时间复杂度？O(n)3.3.2 颜色排序void ColorSort(int a,int n)int n1=0,n2=0,n3=0;for(int i=0;i n;i+
16、)if(ai=1)n1+;if(ai=2)n2+;if(ai=3)n3+;for(i=0;i n1;i+)ai=1;for(;i x，则 n=n+(k2-x个产品需要的箱子数)；4.y=n 个箱子剩余 11 的空位数；5.如果 k1 y，则 n=n+(k1-y个产品需要的箱子数)；6.输出箱子个数 n；【算法分析】算法Packing所有操作步骤都是简单的计算，时间复杂度为O(1)。3.4.1 装箱问题【算法实现】设数组 p24 存储装入33 的产品个数分别是 4、1、2、3 时箱子剩余 22 的空位数，注意到程序中所有的整除都应该是向上取整，程序如下：int Packing(int k1,in
17、t k2,int k3,int k4,int k5,int k6)int n,x,y;int p24=0,5,3,1;n=(k3+3)/4+k4+k5+k6;x=5*k4+p2k3%4;if(k2 x)n+=(k2-x+8)/9;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 列开始先向右再折转向上，呈首尾相接
18、。【想法】根据问题描述的填数规则，找到下标变化规律，用模拟法直接求解。对于方阵的偶数行和列，填数的起始位置是（1,i），然后列号不变行号加 1，至位置（i,i）时折转，行号不变列号减 1，直至位置（i,1）；对于方阵的奇数行和列，填数的起始位置是（j,1），然后行号不变列号加 1，至位置（j,j）时折转，列号不变行号减 1，直至位置（1,j）。3.4.2 数字回转方阵【算法】设函数Full实现填写数字回转方阵，注意数组下标从 0 开始，算法如下：算法：数字回转方阵Full输入：方阵的阶数 n输出：数字回转方阵 znn 1.z00=1，number=2；2.for(i=0,j=1;i n&j n
19、;)2.1 填写偶数层：2.1.1 填数直至 i 等于 j：zi+j=number+;2.1.2 填数直至 j 等于 0：zij-=number+;2.2 填写奇数层：2.2.1 填数直至 i 等于 j：zi+j=number+;2.2.2 填数直至 i 等于 0：zi-j=number+;3.4.2 数字回转方阵【算法实现】注意每一层填数后都要调整下标，程序如下：void Full(int z100100,int n)int number,i,j;z00=1;number=2;for(i=0,j=1;i n&j n;)/依次填写每一层 while(i=0)zij-=number+;i+;j=0;while(i j)zij+=number+;while(i=0)zi-j=number+;j+;i=0;时间复杂度？O(n2)
