网上找的一些10月浙江3模拟策略

1、模拟法模拟的形式随机模拟：题目给定或者隐含某一概率。设计者利用随机函数和取整函数设定某一范围的随机值，将符合概率的随机值作为参数。然后根据这一模拟的数学模型展开算法设计。由于解题过程借助了计算机的伪随机数发生数，其随机的意义要比实际问题中真实的随机变量稍差一些，因此模拟效果有不确定的因素；过程模拟：题目不给出概率，要求编程者按照题意设计数学模型的各种参数，观察变更这些参数所引起过程状态的变化，由此展开算法设计。模拟效果完全取决于过程模拟的真实性和算法的正确性，不含任何不确定因素。由于过程模拟的结果无二义性，因此竞赛大都采用过程模拟。 模拟法的类型直叙式模拟筛选法模拟构造法模拟直叙式模拟 直叙式

2、模拟即按照试题要求展开模拟过程。编程者要忠实于原题，认真审题，千万不要疏漏任何条件，精心设计方便模拟的数据结构。“直叙式模拟”的难度取决于模拟对象所包含的动态变化的属性有多少，动态属性愈多，则难度愈大。 花生采摘【问题描述】鲁宾逊先生有一只宠物猴，名叫多多。这天，他们两个正沿着乡间小路散步，突然发现路边的告示牌上贴着一张小小的纸条：“欢迎免费品尝我种的花生！熊字”。鲁宾逊先生和多多都很开心，因为花生正是他们的最爱。在告示牌背后，路边真的有一块花生田，花生植株整齐地排列成矩形网格（如图1）。有经验的多多一眼就能看出，每棵花生植株下的花生有多少。为了训练多多的算术，鲁宾逊先生说：“你先找出花生最多

3、的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过你一定要在我限定的时间内回到路边。”我们假定多多在每个单位时间内，可以做下列四件事情中的一件：1)从路边跳到最靠近路边（即第一行）的某棵花生植株；2)从一棵植株跳到前后左右与之相邻的另一棵植株；3)采摘一棵植株下的花生；4)从最靠近路边（即第一行）的某棵花生植株跳回路边。现在给定一块花生田的大小和花生的分布，请问在限定时间内，多多最多可以采到多少个花生？注意可能只有部分植株下面长有花生，假设这些植株下的花生个数各不相同。例如在图2所示的花生田里，只有位于(2, 5), (3, 7), (4, 2), (5,

4、 4)的植株下长有花生，个数分别为13, 7, 15, 9。沿着图示的路线，多多在21个单位时间内，最多可以采到37个花生。【输入文件】输入文件peanuts.in的第一行包括三个整数，M, N和K，用空格隔开；表示花生田的大小为M * N（1M, N20），多多采花生的限定时间为K（0K1000）个单位时间。接下来的M行，每行包括N个非负整数，也用空格隔开；第i + 1行的第j个整数Pij（0Pij 500）表示花生田里植株(i, j)下花生的数目，0表示该植株下没有花生。【输出文件】输出文件peanuts.out包括一行，这一行只包含一个整数，即在限定时间内，多多最多可以采到花生的个数。每

5、次在二维数组中找到当前最大值的位置 若最大值为零，则由当前位置直接返回路边； 否则判断走至最大值位置后再返回路边的时间是否来得及：如果来得及，则移动到最大值位置，把该位置的花生数置为零，累加已用时间；如果来不及，就由当前位置直接返回路边。 设var t,m,n,k,max,i,j,max1i,max1j,maxi,maxj,total:integer; 多多目前的行程为t；花生田的规模为m*n；多多采花生的限定时间为k ；最近采集花生的位置为（max1i,max1j），准备采集花生的位置为（maxi，maxj），显然两个采集点的距离为 ；多多在限定时间内可采集到的最多花生数为total p:a

6、rray1.20,1.20of integer; 花生田。其中pi，j为花生田里植株(i, j)下花生的数目由于多多在相邻元素间移动一步的时间为一个单位，因此除去多多从路边往返数组第一行的2个单位时间，则多多在数组内采集花生的时间不允许超过k-2（k=k-2）个时间单位。我们首先计算花生数最多的位置（max1i，max1j）和该位置的花生数max，将多多的行程t初始化为max1i。显然，如果花生田里有花生(max0)且采集了花生最多的植株后可返回路边（t+max1i-1k），则采集（max1i，max1j）位置的花生（pmax1i,max1j0；totaltotal+max）。然后计算下一个花

7、生数最多的位置（maxi，maxj），将两个采集点的距离计入t(tt+ )，并将（maxi，maxj）设为下一个采集目标（max1imaxi;max1jmaxj）。重复上述计算过程，直至花生田里无花生(max=0)或者采集（max1i，max1j）位置的花生后无法返回路边（t+max1i-1k）为止。由此得出算法：readln(m,n,k);读花生田的规模和多多采花生的限定时间k:=k-2; 计算多多在数组内采集花生的最多时间max:=0;读花生田的信息。计算花生数最多的位置（max1i，max1j）和该位置的花生数maxfor i:=1 to m do for j:=1 to n do be

8、gin read(pi,j); if pi,jmax then begin max:=pi,j;max1i:=i;max1j:=j；end;then end;fort:=max1i;total:=0; 多多的行程和采集的花生数初始化while (t+max1i-10) do若在限定时间内回到路边且找到花生最多的植株，则采摘它的花生，并累计采摘的花生总数 begin pmax1i,max1j:=0;total:=total+max; max:=0;计算当前花生数最多的位置（maxi，maxj）和该位置的花生数max for i:=1 to m dofor j:=1 to n doif pi,jm

9、ax then begin max:=pi,j;maxi:=i;maxj:=j；end;then t:=t+1+abs(max1i-maxi)+abs(max1j-maxj);累计行程 max1i:=maxi;max1j:=maxj；从该位置出发，继续采摘花生end;while writeln(total);输出限定时间内多多采到花生数的最大值 时间复杂度为O (k*n2) 贪心算法 先将花生植株按花生数递减的顺序排列成一维数组，数组元素记录下植株的花生数和位置。按照数组顺序，找出距离之和不超过k-2、且最接近k-2的前若干个元素，将这些元素记录的花生数累加起来，便构成了问题的解。算法的时间复

10、杂度为O (n*log n +k)。昂贵的聘礼 年轻的探险家来到了一个印第安部落里。在那里他和酋长的女儿相爱了，于是便向酋长去求亲。酋长要他用10000个金币作为聘礼才答应把女儿嫁给他。探险家拿不出这么多金币，便请求酋长降低要求。酋长说：“嗯，如果你能够替我弄到大祭司的皮袄，我可以只要8000金币。如果你能够弄来他的水晶球，那么只要5000金币就行了。”探险家就跑到大祭司那里，向他要求皮袄或水晶球，大祭司要他用金币来换，或者替他弄来其他的东西，他可以降低价格。探险家于是又跑到其他地方，其他人也提出了类似的要求，或者直接用金币换，或者找到其他东西就可以降低价格。不过探险家没必要用多样东西去换一样

11、东西，因为不会得到更低的价格。探险家现在很需要你的帮忙，让他用最少的金币娶到自己的心上人。另外他要告诉你的是，在这个部落里，等级观念十分森严。地位差距超过一定限制的两个人之间不会进行任何形式的直接接触，包括交易。他是一个外来人，所以可以不受这些限制。但是如果他和某个地位较低的人进行了交易，地位较高的的人不会再和他交易，他们认为这样等于是间接接触，反过来也一样。因此你需要在考虑所有的情况以后给他提供一个最好的方案。 为了方便起见，我们把所有的物品从1开始进行编号，酋长的允诺也看作一个物品，并且编号总是1。每个物品都有对应的价格P，主人的地位等级L，以及一系列的替代品Ti和该替代品所对应的“优惠”

12、Vi。如果两人地位等级差距超过了M，就不能“间接交易”。你必须根据这些数据来计算出探险家最少需要多少金币才能娶到酋长的女儿。输入文件 M，N（1=N=100），依次表示地位等级差距限制和物品的总数。 按照编号从小到大依次给出了N个物品的描述。每个物品的描述开头是三个非负整数P、L、X（XN），依次表示该物品的价格、主人的地位等级和替代品总数。接下来X行每行包括两个整数T和V，分别表示替代品的编号和“优惠价格”。输出文件 最少需要的金币数。数据结构const maxn=100;物品数上限type ny=nz;物品的指针变量 nz=array1.maxn,1.2 of longint;替代品序列，

13、包括每一个替代品的编号和“优惠价格” nx=record p,x,l:longint; 物品的价格、替代品总数和主人的地位等级 list:ny; 替代品序列 end;var map:array1.maxn of nx;物品序列 can:array1.maxn of boolean;记录与当前客户的等级差距在限制范围内的客户 p,l,x,i,j,m,n，l1:longint;输入信息readln(m,n);输入地位等级差距限制和物品总数readln(map1.p,map1.l,map1.x);读入物品1的价格、主人的地位等级和替代品总数new(map1.list);读入物品1的每个替代品的编号和

14、“优惠价格”for i:=1 to map1.x do readln(map1.listi,1,map1.listi,2);for i:=2 to n do读入物品2物品n的信息 with mapi do begin readln(p,l,x);new(list); for j:=1 to x do readln(listj,1,listj,2); end;计算最少需要的金币数递推每一个客户h(1hn)11寻找每一个与客户h的等级差距在限制范围内的客户i搜索客户i的每一个可与客户h交易的替代品j,若替代后花钱更少，则记下 pricei=minpricej+物品j的优惠价，物品i的单价12若当前

15、方案最佳（price1=0) and (mapi.l-maph.l=m) then cani:=true; for i:=1 to n do pricei:=mapi.p;初始时直接购买repeat ok:=true; for i:=1 to n do枚举每一个与客户h的等级差距在限制范围内的客户 if cani then for j:=1 to mapi.x do begin枚举物品i的每一个替代品，记下其编号和“优惠价格” now:=mapi.listj,1; more:=mapi.listj,2; if （cannow）and(pricenow+morepricei) 若第j个替代品可与

16、客户h交易且间接交易后花钱更少，则采取该交易方案 then begin ok:=false;pricei:=pricenow+more;end; end;foruntil ok;if price1min then min:=price1;若目前方案的花钱最少，则记下end;for writeln(min);输出最少需要的金币数end;DAM语言 有个机器执行一种DASM语言。该机器有一个栈，初始时栈里只有一个元素x，随着DAM语言程序的执行，栈里的元素会发生变化。DAM语言有四种指令：D指令：把栈顶元素复制一次加到栈顶A指令：把栈顶元素取出，加到新的栈顶元素中。M指令：把栈顶元素取出，乘到新的

17、栈顶元素中。如果执行A或M指令的时候栈内只有一个元素，则机器会发出错误信息。如果程序无误，那么执行完毕以后，栈顶元素应该是x的多项式，例如，程序DADDMA的执行情况为（栈内元素按照从底到顶的顺序从左至右排列，用逗号隔开）：x x， x 2x 2x， 2x 2x， 2x， 2x 2x， 4x2 4x2+2x给出一段DAM程序，求出执行完毕后栈顶元素。输入输入仅一行，包含一个不空的字符串s，长度不超过12，代表一段DAM程序。输入程序保证合法且不会导致错误。输出仅输出一行，即栈顶多项式。须按照习惯写法降幂输出，即：等于1的系数不要打印，系数为0的项不打印，第一项不打印正号。一次方不打印1。 模拟

18、需要注意的问题：多项式的表示方式。有的选手或许会觉得：本题没有说明次数的上限，因此最好用链表做。其实完全没有必要。由于指令不超过12条，而D指令和A，M指令总数应该相等，因此最多有6条M指令，因此次数上限为26=64。我们可以用数组来表示多项式，又方便又不会导致时间和空间上的问题。 本题也没有说明系数的最大值。稍微细心的选手发现：它最大可能为232，超过长整数的范围，因此需要采用extended类型，当然，也不存在非得用高精度的必要。 $n+var degree ： array1 . 20 of integer； 存储系数个数的栈 co ： array1 . 20， 0 . 64 of ext

19、ended；存储多项式的栈 tmp ： array0 . 64 of extended；系数序列 I， j， d， a， b， top ： integer； 栈顶指针为top s ： string； Dam程序 first ： boolean；begin top 1； 栈顶指针初始化 fillchar(co， sizeof(co)， 0)； 存储多项式的栈清零 degree1 1；初始时栈里只有一个元素x co1， 1 1； read(s)；输入Dam程序 for I 1 to length(s) do依次执行Dam程序中的每一条命令case sI ofD： begin 把栈顶元素复制一次加到

20、栈顶 inc(top)；degreetop degreetop 1； for j 0 to degreetop do cotop， j cotop 1， j； end； DA： begin 把栈顶元素取出，加到新的栈顶元素中 dec(top)； if degreetop degreetop + 1 then degreetop degreetop + 1； for j 0 to degreetop do cotop， j cotop， j + cotop + 1， j； end； AM：begin 把栈顶元素取出，乘到新的栈顶元素中 dec(top)；fillchar(tmp，sizeof(t

21、mp)，0)；ddegreetop+degreetop +1； for a0 to degreetop do for b 0 to degreetop + 1 do tmpa + btmpa+b+cotop， a*cotop+1， b degreetop d； for j 0 to d do cotop， j tmpj； end； Mend；case first true；按照降幂的顺序输出栈顶多项式 for I degreetop downto 1 do if cotop， I 0 then begin if first then first false else write(+)； if

22、abs(cotop， I 1.0) 1e-6 then write(cotop， I ： 0 ： 0)； write(x)； if I 1 then write(， I)； end；then writeln；end.main跳远在水平面上整齐的放着n个正三角形，相邻两个三角形的底边之间无空隙，如左图所示。一个小孩子想站在某个三角形i的顶端，跳到三角形j的顶端上(ij)。他总是朝着斜向45度的方向起跳，且初始水平速度v不超过一个给定值v0。在跳跃过程中，由于受到重力作用（忽略空气阻力），小孩子将沿着抛物线行进，水平运动方程为x = x0 + vt，竖直运动方程为y = y0 + vt 0.5gt

23、2，运动轨迹是一条上凸的抛物线。取g=10.0，(x0， y0)是起跳点坐标。请编程求出他从每个位置起跳能到达的最远三角形的编号。注意：跳跃过程中不许碰到非起点和终点的其他三角形。输入第一行为两个正整数n，v0(3n10， 1v0100)，表示三角形的个数和最大水平初速度。第二行有n个正整数li(1li20)，表示从左到右各个三角形的边长。输出输出仅一行，包括n-1个数，表示从三角形1，2，3n-1的顶点出发能到达的最右的三角形编号。如果从某三角形出发无法达到任何三角形，相应的数为0。状态：起跳点i和i点后的点j。每个状态元素的取值范围：1in-1，i+1jn 约束条件的分析：判断小孩能否从i

24、点跳到j点的方法如下：设起点和终点间的水平距离为l、垂直距离为h。则由物理知识（已在题目中给出）有：t = l / vh = vt 5t2 = l 5*(l/v)2 。因此，v = sqrt(5*l*l/ (l - h)。当然，这个v不一定符合要求，它需要满足两个条件。 它不能大于极限速度v0，即必须有v v0 跳跃过程中不得碰到其他三角形。 如何判断顶点k是否在抛物线下呢？我们可以算出到达时间t0 = dx / v（其中dx为起点到顶点k的水平坐标增量），然后算出该时刻的竖直坐标增量vt0 0.5t02。如果此增量大于起点到顶点k的竖直坐标增量，则抛物线在上方。只有起点和终点之间任何一个三角

25、形的顶点不在抛物线下方，则跳远不能完成。我们在枚举过程中不断将小孩所能跳到的点j调整为best。 枚举结束后，best即为试题要求的最远点。var len ： array1 . 20 of longint； x， y ： array1 . 20 of double；三角形顶端顶点的坐标序列 l， h， t， v， v0 ： double； ok ： boolean；跳跃成功标志 i， j， k， n， best ： integer；begin read(n， v0)；输入三角形的个数和最大水平初速度 for i 1 to n do read(leni)；入从左到右各个三角形的边长 x1 len

26、1 / 2；计算每一个三角形顶端顶点的坐标 y1 len1 * sqrt(3) / 2； for i 2 to n do begin xi xi - 1 + leni - 1 / 2 + leni / 2； yi leni * sqrt(3) / 2； end；forfor i 1 to n - 1 do依次计算每一个三角形所能到达的最远点 begin best 0；从三角形i出发能到达的最右的三角形编号初始化 for j i + 1 to n do依次枚举右方的每一个三角形 begin l xj - xi；计算三角形i与三角形j的两个顶端顶点的水平距离和垂直距离 h yj - yi； if

27、l v0 then break；若大于极限速度v0，则无法从三角形i起跳 ok true； for k i + 1 to j - 1 do判断跳跃过程中是否碰到其他三角形 begin t (xk - xi) / v；计算到达三角形k的时间 if (v * t - 5 * t * t) - (yk - yi) 1e-6 then begin如果该时刻的竖直坐标增量大于起点到顶点k的竖直坐标增量，则抛物线在上方 ok false； break； end；then end；forif ok then best j 若跳远成功，则三角形j为目前三角形i所能到达的最远点，否则跳远不能完成 else br

28、eak； end；for write(best， )；输出从三角形i的顶点出发所能到达的最右的三角形编号） end；for writeln；end.main筛选法模拟 模拟过程中可能产生的所有解组成一个筛。筛选法模拟即先从题意中找出约束条件，然后将筛中的每一个可能解放到约束条件的过滤器上，一次一次地将不符合条件的解过滤掉，最后沉淀在筛中的即为问题的解。“筛选法模拟”的结构和思路简明、清晰，但带有盲目性，因此时间效率并不一定令人满意。“筛选法模拟”的关键是找准约束条件，任何错误和疏漏都会导致模拟失败。 蒙特卡洛法 计算定积分其中ab，0f(x)d， 输入：a b d a0a1ak(表示f(x)=

29、ak*xk+a1*x+a0) 产生n(足够大)个均匀分布在长方形a b c d上的随机数点(xi，yi)。其中 xi均匀分布在区间a，b上的随机数，即xi=a+(b-a)*random(1)； yi均匀分布在区间0，d上的随机数，即yi=d*random(1)； n个随机数点组成一个筛。约束条件的过滤器是某点(xi，yi)是否落在曲边梯形a e f b外。如果是（yif(xi)），则该点从筛中过滤掉。 最后有m个随机数点留在筛中（这些随机数点落在曲边梯形a e f b内）。曲边梯形a e f b的面积应该为m和n的比值乘以长方形a b c d的面积 function f(x)：real；计算f

30、(x) begin f(x)akxk+ak-1kk-1+a1x+a0； end；f function amoncar (a， b， d， n)：real；计算 begin randomize； m0； for i1 to n do begin xa+(b-a)*random(1)；产生ki yd*random(1)；产生yi if yf(x) then mm+1；若(xi，yI)落入曲边梯形内，则累计其点数 end；for amoncarm/n*(b-a)*d；返回曲边梯形面积 end；amoncar 在主程序中，输入随机点的个数n和a，b，d，然后通过调用函数amoncar (a，b，d，n

31、)计算和输出定积分的值。注意，n愈大，定积分的值愈精确，但速度愈慢。 self-number对任意一个正整数n，定义d(n)为n加上其每一位上的数字，比如d(75) = 75 + 7 + 5 = 87。并且称n是d(n)的一个generator。一个正整数，如果没有任何generator，就说这个数是一个self-number。给出一列数s1，s2，sK，问范围1, N内第s1，s2，sK大的self-number分别是什么。输入： n k(1 N 107,1 K 5000) s1，s2，sK输出： 范围1, N内第s1，s2，sK大的self-number用筛数方法产生1, N中的所有sel

32、f-number 在一张一维的布尔表中，从小到大将每个数n的d(n)都标记为不可能是self-number，那么未被标记的一定就是self-number了。 布尔表的容量：因为d(n) n并不会很大：最大也不过9*lgn=81。计算d(n)的时间复杂度原时间复杂度为O(NlgN)：因为每次计算d(n)时侯分离其每一位的时间复杂度是O(lgN)。本题中N高达107，因此这个O(lgN)的因子不可以忽略。优化首先预处理，开一个sumi数组，记录i的每一位之和，但是这里i的范围不用太大，只要在O(sqrt(n)=104就可以了。这样计算d(n)的时侯，就可以将n的各位和分成低4位和高3位来计算，而每

33、次计算不过是调用sumi，这样计算d(n)的时间复杂度就降到了O(1)。综上，本题的时间复杂度就是O(sqrt(n)lgN + N + Mlog2M)，其中Mlog2M是在输出的时侯需要对si进行排序。设筛data，其中datai 将数i的d(i)标记为不可能是self-number。筛长为1000。self-number序列为request，其中request i. request 为si，request i. number为si的输入顺序，request i. answer为顺序为si的self-number数初始化read(N , K); for i := 1 to K do输入s1，s

34、2，sK ，记下输入顺序 begin read(requesti.request); requesti.number := i; end;qk_sort(1 , K)；按照requesti.request (si)递增顺序排列request计算sub0sub10000，其中subi为整数i的各位数的和； fillchar(data , sizeof(data) , 0);初始时筛满，即所有数可能是self-number数 now := 1; total := 0; p := 1; for i := 1 to N do顺序搜索1, N内第s1，s2，sK大的self-number begin i

35、f not datanow then若now在筛中 begin inc(total);累计self-number的个数 while (p Limit do dec(tmp , Limit);将di限制在1000范围内 datatmp := true; datanow := false; 在data筛中保留第now个元素，去掉第di个元素 if now = Limit循环右移data筛的指针now then now := 1 else inc(now); end; 输出self-numberfor i := 1 to K do outarrrequesti.number := requesti.

36、answer;按照输入要求记下各个self-number数输出1.n中self-number的个数 total输出outarr1 outarrk；构造法模拟 构造法模拟需要完整精确地构造出反映问题本质的数学模型，根据该模型设计状态变化的参数，计算模拟结果。由于数学模型建立了客观事物间准确的运算关系，因此其效率一般比较高。“构造法模拟”的关键是找到数学模型。问题是，能产生正确结果的数学模型并不是唯一的，从不同的思维角度看问题，可以得出不同的数学模型，而模拟效率和编程复杂度往往因数学模型而异。即便有数学模型，但解该模型的准确方法是否有现成算法、编程复杂度如何，这些都是我们要考虑的问题。化学试验安排

37、 阿扁是一位出色的化学研究员。近日，他正致力于研制一种化学药物，用以纠正他糟糕的嗓音。阿扁给他这次研究起的代号是”acm”（arbains chemical magic，“阿扁的化学魔术”)。 经过两个星期的寻找，阿扁已经采集了若干种化学原料。现在，他需要对每种原料进行精密的分析，以确定有效成分的含量。每种原料的分析都必须依次经过两个步骤：首先让原料接受一定时间一定量的粒子轰击（称放射试验）；然后在156.0973下与浓硫酸共热（称加热试验），两个试验都必须在特制的精密昂贵的仪器内进行。 现在的问题是，由于经费的问题，阿扁的实验室里只有一台做放射试验的仪器及一台做加热试验的仪器。换句话说，同一

38、时间内最多只能做一个放射试验和一个加热试验。而各种原料需做试验的时间是不尽相同的（幸而关于这些时间的数据阿扁已经做了做精确的预算）。现在请你预计一下阿扁能结束试验的最早时间。输入 ： 第一行为原料的数量n（整数，0=n=1000）。以下n行每行各两整数ai，bi，表示第i种原料做放射试验的时间为ai，做加热试验的时间为bi。（0ai，bi100且aibi）输出 ：只有一行，为结束试验的最早时间。 本题“分析试验”的特殊性在于：每份原料必须先进行放射试验，再进行加热试验；一次只能有一份原料在某一台仪器上做试验。整个试验的进行非常类似于计算机的“并行处理”。易知，由于放射实验所受到的限制少，没有“

39、空闲”的时间，所以放射试验的总时间是确定的（=ai）。问题就在于加热试验对放射试验的“等待”。从最简单的情况开始 首先，当只有一份原料时，无需安排，先“放射”再“加热”就可以了。当有两份原料时，如Sample 1，情况也很简单，无非是1-2和2-1的区别。 放射试验a1a2时间12345678910加热试验b1b2放射试验a2a1时间123456789加热试验b2b1结论 考虑两份原料i、j，当按照先i后j的顺序做试验时，总耗时 进一步，我们设 (先i后j顺序中的重合部分)，其含义为在两台仪器上同时试验的时间。那么再分析原料数增多的情况确定原料两两之间的较优顺序 应把p排在试验最前面 应把p排

40、在最后试验 const TaskLim=1000；最多原料数var task:array1.2，1.TaskLimof byte；每种原料做放射、加热试验的时间 odr:array1.TaskLimof integer；最优化顺序 n，totTime:longint；procedure init；读入数据var i，j，k:integer；begin readln(n)； 读原料数 for i1 to n do readln(task1，i，task2，i)；读每种原料的放射试验时间和加热试验时间end； init procedure Order； 安排试验顺序var i，j，k， min，b

41、estj，bestk，当前安排试验的费时、原料和实验内容 pfront，ptail:integer；头、尾指针 tick:array1.TaskLimof 0.1；试验工序beginfillchar(tick，sizeof(tick)，0)；试验工序初始化pfront0；ptailn+1；头尾指针初始化for i1 to n do 依次安排每个试验 begin min30000；在未安排试验的原料中，寻找试验时间最短的原料bestj,试验内容为k for j1 to n do if (tickj=0)then for k1 to 2 do if taskk，jtmi在tottime时刻开始做原

42、料j的加热试验 then inc(tottime，task2，j) else tottimetmi+task2，j；顺序做原料j的放射试验和加热试验 end；forend； CalcTime begin init；输入数据 order；计算试验工序 calctime；计算总耗时 writeln(tottime)；输出总耗时End.main模拟策略举例 在自然界和日常生活中，许多现象具有不确定的性质，有些问题甚至很难建立数学模型，或者很难用计算机建立递推、递归、枚举、回溯法等算法。在这种情况下，一般采用模拟策略。所谓模拟策略就是模拟某个过程，通过改变数学模型的各种参数，进而观察变更这些参数所引起

43、过程状态的变化，由此展开算法设计。 等价表达式【问题描述】明明进了中学之后，学到了代数表达式。有一天，他碰到一个很麻烦的选择题。这个题目的题干中首先给出了一个代数表达式，然后列出了若干选项，每个选项也是一个代数表达式，题目的要求是判断选项中哪些代数表达式是和题干中的表达式等价的。 这个题目手算很麻烦，因为明明对计算机编程很感兴趣，所以他想是不是可以用计算机来解决这个问题。假设你是明明，能完成这个任务吗？这个选择题中的每个表达式都满足下面的性质：1 表达式只可能包含一个变量a。2 表达式中出现的数都是正整数，而且都小于10000。3 表达式中可以包括四种运算+（加），-（减），*（乘），（乘幂）

44、，以及小括号(，)。小括号的优先级最高，其次是，然后是*，最后是+和-。+和-的优先级是相同的。相同优先级的运算从左到右进行。（注意：运算符+，-，*，以及小括号(，)都是英文字符）4 幂指数只可能是1到10之间的正整数（包括1和10）。5 表达式内部，头部或者尾部都可能有一些多余的空格。下面是一些合理的表达式的例子：(a1) 2)3，a*a+a-a，(a+a)，9999+(a-a)*a，1 + (a -1)3，1109【输入文件】输入文件equal.in的第一行给出的是题干中的表达式。第二行是一个整数n（2 n 26），表示选项的个数。后面n行，每行包括一个选项中的表达式。这n个选项的标号分

45、别是A，B，C，D 输入中的表达式的长度都不超过50个字符，而且保证选项中总有表达式和题干中的表达式是等价的。【输出文件】输出文件equal.out包括一行，这一行包括一系列选项的标号，表示哪些选项是和题干中的表达式等价的。选项的标号按照字母顺序排列，而且之间没有空格。问题的核心是如何判断表达式等价 判断表达式等价的方法一般有两种：表达式化简后判断表达式代值后判断判断等价的方法1：展开多项式后判断 将所有的表达式全部转化为最简形式，然后再计算。其一般过程:先将阶乘化乘，再展开。计算同时合并同类项，并用数组记录每一个表达式的最简形式。然后比较每一个表达式的数组与题干表达式的数组是否相同。若相同，

46、则说明该表达式与题干表达式是等价的。优点:准确和严密缺点:实现相当麻烦，时间效率不高，尤其是在乘幂多、幂次大的情况下。 判断等价的方法2：代值后判断 将数值代入并计算。 误判的可能:假如碰巧代入的值使两个多项式值相等 避免的方法：多次代入不同数值、代入较大数值等等。虽然这个算法并不一定正确，但多次随机代值后的出错概率已经可以忽略不计了，而且实现又比较简单。取值的有效方法：取随机函数生成的数列。这种方法比较有效，无规律。取伪随机数列。这是一种比较便于人工控制的手段。取实数。优点:由于系数和次幂和常数皆为整数，因此小数部分便成为判断的优越条件。缺点:由于计算中出现了次方运算，所以可能溢出。避免整数

47、溢出的方法:在求值过程中采用取模运算，并且多取几个模。我们采取多代整数、多取模的方法判断表达式等价。于是，如何计算表达式的值成了问题的关键表达式求值的方法1:栈操作 建立两个栈，一个是存储操作数的数栈，一个是存储运算符的符号栈。每一个符号定义一个优先级,优先级高的运算符先算。为了方便起见，我们定义特殊符号#的级别最低（赋-1），先将它置符号栈的栈底。然后依次读入每个字符，如果是数字，则入数栈。如果是运算符，则与符号栈的栈顶元素比较优先级。如果相等，则出栈，读下一字符；如果栈外大，则入栈；如果栈内大，则符号栈的栈顶元素出栈，与数栈最顶2元素运算，结果入数栈。这个符号继续处理（再与栈顶比较）。直到

48、读到最后符号#使栈底#出栈时，数栈顶即为表达式结果。 表达式求值的方法2:并查集操作 每次在尚未运算的运算符找出一个优先级最高的符号，进行相应的运算，直至仅剩一个数字时返回。这种方法符合自然思维和运算规则，实现简单明了，不易出错。我们由左而右扫描表达式串st的每一个字符，存储每一个运算的信息。其中第i个运算的运算符存储在ci，优先级存储在di（di= ），操作数存储在ri（若第i个运算的操作数为变量a，则ri=-1）1、数据结构 我们将目前所有参与过运算的操作数放在集合里，其中第p个操作数参与运算后的结果记入第fp个操作数，即所有具有同一个f值的操作数组成一个集合，它们运算后的结果记入第fp个

49、操作数。 如果ci为当前的运算符，则从fi和fi+1出发，顺着f指针即可找到参与运算的两个操作数。const xn=3;代入的a的总数 mn=2;模的总数var cm,rc,nn,n,i,j:longint;选项数为nn；运算数为n st:string;表达式串 c:array 1.30 of char;ci为第i个运算的运算符 d:array 1.30 of longint; di为第i个运算的优先级 r,u:array 1.30 of int64; ri为第i个运算的操作数。若ri=-1，则第i个运算的操作数为变量a a:array 1.xn,1.mn of int64;将第i个变量值和第

50、j个模代入题干后的值为ai,j x:array 1.xn of longint;a的第i个代入值为xi；模的第i个代入值为yi y:array 1.mn of longint; yes:boolean;当前选项与题干等价的标志 mv:int64;当前选项的值2、记录当前选项的每一个运算 procedure ff; var top,i,j,v:longint;i为读字符串的指针；top为括号嵌套重数，v为操作数 begin top:=0;n:=1;i:=0;括号嵌套重数、运算顺序数和字串指针初始化 fillchar(r,sizeof(r),0);操作数序列初始化 while ilength(st

51、) do begin inc(i);字串指针右移 case sti of分析第i个字符的类型 (:inc(top);若为左括号，括号嵌套重数+1 ):dec(top); 若为右括号，括号嵌套重数-1 0.9:begin若为数串，则计算对应的数字，记入rn。字串指针指向数串后的第一个字符 j:=i;v:=0; while(j=0)and(stj=9)or(stj= )do begin if stj then v:=v*10+ord(stj)-48;inc(j) end; while rn:=v;i:=j-1 end; 0.9 a: rn:=-1; :continue; else begin cn

52、:=sti;记下运算符 case sti of记下优先级 +,-:dn:=top*3+1; *:dn:=top*3+2; :dn:=top*3+3 end; case inc(n)运算顺序+1 end else end;caseend;whileend; ff 3、求值过程设b为运算完成的标志序列，其中bi=true，标志已完成ci运算符指定的运算。在含有n个运算的表达式中，含有n-1个运算符。参与当前运算的两个操作数为rp和rq。我们采用类似并查集的方法计算表达式值，即初始时，N个操作数各组成n个集合。当计算rprp op rq后，集合q并入集合p （fqp），表明第p个操作数和第q个操作数已经完成了运算，计算结果记入第p个操作数。首先将n个变量操作数进行代值，并对n个操作数进行取摸运算。然后在未参与运算的运算符中寻找运算级最高的运算符cmax,dmax= 。然后从max和max+1位置开始沿着f指针寻找两个待运算的操作数up和uq（fp=p，fq=q），完成由cmax指定的运算，结果记入up，集合q并入集合p。bmaxtrue。依次类推，直至完成n-1个运算为止。 例如变量a=1、模为10时，计算表达式a+(1+2)3的值：r序列-1123f序列1234c序列+d序列143b序列falsefalsefalsefalse找出运算符优先级最高的d2（对应括号内的+）和两个操