2019-2020年高中信息技术全国青少年奥林匹克联赛教案枚举法二

2019-2020年高中信息技术全国青少年奥林匹克联赛教课方案列举法二课题：列举法目标：知识目标：列举算法的实质和应用

能力目标：列举算法的应用！重点：利用列举算法解决实责问题难点：列举算法的次数确定板书表示：1）简单列举（例

7、例

8、例

9）2）利用列举解决逻辑判断问题（例3）列举解决竞赛问题（例12、例

10、例11）13、例14）授课过程:所谓列举法，指的是从可能的解会集中一一列举各元素些是无用的，哪些是适用的?能使命题建立，即为其解。一般思路

:

，用题目给定的检验条件判断哪对命题建立正确的数学模型；依照命题确定的数学模型中各变量的变化范围（即可能解的范围）

；利用循环语句、条件判断语句渐渐求解或证明；列举法的特点是算法简单，但有时运算量大。对于可能确定解的值域又一时找不到其他更好的算法时能够采用列举法。例7:求满足表达式A+B=C的全部整数解，其中A,B,C为1~3之间的整数。解析：本题特别简单，即列举全部情况，吻合表达式即可。算法以下：forA:=1to3doforB:=1to3doforC:=1to3doifA+B=CthenWriteln（A,

‘+'

,B,

‘='

,C）;上例采用的就是列举法。所谓列举法，指的是从可能的解的会集中一一列举各元素，用题目给定的检验条件判断哪些是无用的，哪些是适用的。能使命题建立的，即为解。从列举法的定义能够看出，列举法实质上属于搜寻。但与隐式图的搜寻有所差异，在采用列举法求解的问题时，必定满足两个条件:①起初确定解的个数n；②对每个解变量A1，A2,An的取值，其变化范围需起初确定A?{Xi1,Xq}A?{X11,,XP}{Xnl,,%k}例7中的解变量有3个：AB,C。其中AB

解变量值的可能取值范围A?{1解变量值的可能取值范围B?{1

,2,3},2,3}C解变量值的可能取值范围C?{1,2,3}(A,B,C)?{(1，1，则问题的可能解有27个1),(1,1,2),(1,1,3),(1,2,1),(1,2,2),(1,2,3),(3,3,1),(3,3,2),(3,3,3)}在上述可能解会集中，满足题目给定的检验条件的解元素，即为问题的解。若是我们无法起初确定解的个数或各解的值域，则不能够用列举，只能采用搜寻等算法求解。由于回溯法在搜寻每个可能解的列举次数一般不仅一次，因此，对于同样规模的问题，回溯算法要比列举法时间复杂度稍高。例8给定一个二元一次方程aX+bY=c。从键盘输入a,b,c的数值，求X在［0,100］,Y在［0,100］范围内的全部整数解。解析：要求方程的在一个范围内的解，只要对这个范围内的全部整数点进队列举，看这些点可否满足方程即可。参照程序：programexam8;vara,b,c:integer;x,y:integer;beginwrite('Inputa,b,c:');readln(a,b,c);forx:=0to100dofory:=0to100doifa*x+b*y=cthenwriteln(x,'',y);end.从上例能够看出，所谓列举法，指的是从可能的解会集中一一列举各元素，用题目给定的检验条件判断哪些是无用的，哪些是适用的?能使命题建立，即为其解。例9巧妙填数将1?9这九个数字填入九个空格中。每一横行的三个数字组成一个三位数。若是要使第二行的三位数是第一行的两倍，第三行的三位数是第一行的三倍，应怎样填数。如图6:192384576图6解析：本题目有9个格子，要求填数，若是不考虑问题给出的条件，共有9!=362880种方案，在这些方案中吻合问题条件的即为解。因此能够采用列举法。但仔细解析问题，显然第一行的数不会高出400，实质上只要确定第一行的数就可以依照条件算出其他两行的数了。这样仅需列举400次。因此设计参照程序：programexam9;vari,j,k,s:integer;functionsum(s:integer):integer;beginsum:=sdiv100+sdiv10mod10+smod10end;functionmul(s:integer):longint;beginmul:=(sdiv100)*(sdiv10mod10)*(smod10)end;beginfori:=1to3doforj:=1to9doifj<>ithenfork:=1to9doif(k<>j)and(k<>i)thenbegins:=i*100+j*10+k;{求第一行数}if3*s<1000thenif(sum(s)+sum(2*s)+sum(3*s)=45)and(mul(s)*mul(2*s)*mul(3*s)=362880)then{满足条件，并数字都由1~9组成}beginwriteln(s);writeln(2*s);writeln(3*s);writeln;end;end;end.例10

在某次数学竞赛中

,A

、B、C、D、E

五名学生被取为前五名。请据以下说法判断

出他们的详尽名次

,

即谁是第几名？

条件

1:

你若是认为

A,B,C,D,E

就是这些人的第一至第五名的名次排列

,

便大错。由于

没猜对任何一个优胜者的名次。也没猜对任何一对名次相邻的学生。条件2:你若是按D,A,E,C,B来排列五人名次的话,其结果是:说对了其中两个人的名次。还猜中了两对名次相邻的学生的名次序次。解析：本题是一个逻辑判断题，一般的逻辑判断题都采用列举法进行解决。5个人的名次分别能够有5!=120种排列可能，由于120比较小，因此我们对每种情况进队列举,然后依照条件判断哪些吻合问题的要求。依照已知条件，A<>1,B<>2,C<>3,D<>4,E<>5,因此消除了一种可能性，只有4！=24种情况了。参照程序：ProgramExamIO;VarA,B,C,D,E

:lnteger;Cr

:Array[1..5]OfChar;BeginForA:=1To5DoForB:=1To5DoForC:=1To5DoForD:=1To5DoForE:=1To5DoBegin{ABCDE没猜对一个人的名次}If(A=1)Or(B=2)Or(C=3)Or(D=4)Or(E=5)ThenContinue;If[A,B,C,D,E]<>[1,2,3,4,5]ThenContinue;{他们名次互不重复}{DAECB猜对了两个人的名次}IfOrd(A=2)+Ord(B=5)+Ord(C=4)+Ord(D=1)+Ord(E=3)<>2ThenContinue;{ABCDE没猜对一对相邻名次}If(B=A+1)Or(C=B+1)Or(D=C+1)Or(E=D+1)ThenContinue;{DAECB猜对了两对相街坊名次}IfOrd(A=D+1)+Ord(E=A+1)+Ord(C=E+1)+Ord(B=C+1)<>2ThenContinue;Cr[A]:='A';Cr[B]:='B';Cr[C]:=C;Cr[D]:='D';Cr[E]:='E：WRITELN(CR[1],'',CR[2],'',CR[3],'',CR[4],'',CR[5]);End;End.例11:来自不同样国家的四位留学生A,B,C,D在一起讲话，他们只会中、英、法、日四种语言中的2种，情况是，没有人既会日语又会法语;A会日语，但D不会,A和D能互相讲话,B不会英语，但A和C讲话时却要B当翻译,B,C,D三个想互相讲话，但找不到共同的语言,只有一种语言3人都会，编程确定A,B,C,D四位留学生各会哪两种语言。解析：将中、法、日、英四种语言分别定义为CHNFRHJPNENG则四种语言中取两种共有(CHN,ENG),(CHN,FRH,(CHN,JPN),(ENG,FRH),(ENG,JPN),(FRH,JPN)六种组合，分别定义为1、2、3、4、5、6。据已知，没有人既会日语又会法语；因此，组合6不会出现；A会日语，因此A只可能等于3、5；D不会日语，因此D只可能等于1、2、4；B不会英语，因此B只可能等于2、3;见下表。若是我们对ABC、D分别进队列举，依照判断条件，即可找到答案。(CHN,ENG)(CHN,FRH)(CHN,JPN)(ENG,FRH)(ENG,JPN)AXXXBXXXCD程序以下：

XXprogramEXAM11;typeLanguage=(CHN,ENG,FRH,JPN);TNoSet=setofLanguage;constNo:array[1..5]ofTNoSet=([CHN,ENG],[CHN,FRH],[CHN,JPN],[ENG,FRH],[ENG,JPN]);varA,B,C,D:1..5;Can1,Can2,Can3,Can4:Boolean;functionMight(Lang:Language):Boolean;varBool:Boolean;beginBool:=false;ifNo[A]*No[A]*No[C]=[Lang]thenBool:=True;ifNo[A]*No[B]*No[D]=[Lang]thenBool:=True;ifNo[A]*No[C]*No[D]=[Lang]thenBool:=True;ifNo[B]*No[C]*No[D]=[Lang]thenBool:=True;Might:=Boolend;procedurePrint(A,B,C,D:Integer);procedureShow(P:Integer;Ch:Char);varInteger;Lang:Language;beginWrite(ch,':');forLang:=CHNtoJPNdoifLanginNo[P]thencaseLangofCHN:Write('CHN':5);FRH:Write('FRH':5);JPN:Write('JPN':5);ENG:Write('ENG':5);end;WriteIn;end;beginShow(A,'A');Show(B,'B');三个想互相讲话，但找不到共同的语言Show(C,C);Show(D,'D');end;beginforA:=3to5doifA<>4thenforB:=2to3doforC:=1to5doforD:=1to4doifD<>3thenbegin{A和D能互相讲话}Can1:=No[A]*No[D]<>[];{A和C讲话时却要B当翻译

}Can2:=(No[A]*No[C]=[])and(No[A]*No[B]<>[])and(No[B]*No[C]<>[]);{B,C,D}Can3:=No[B]*No[C]*No[D]=[];{只有一种语言3人都会}Can4:=Ord(Might(CHN))+Ord(Might(ENG))+Ord(Might(FRH))+Ord(Might(JPN))=1;ifCan1andCan2andCan3andCan4thenPrint(A,B,C,D);end;end.例12

古纸残篇在一位数学家的藏书中夹有一张古旧的纸片。

纸片上的字早已模糊不清了

，只留下以前写过字的印迹，隐约还可以够看出它是一个乘法算式

，如图

7

所示。这个算式上原来的数字是什么呢？夹着这张纸片的册页上，“素数”两个字被醒目的划了出来。难道说,这个算式与素数有什么关系吗？有人对此作了深入的研究

，果然发现这个算式中

***的每一个数字都是素数

，而且这样的算式是唯一的。请你也研究

x**一番，并把这个算式写出来。解析：实质上，

只要知道乘数和被乘数就可以写出乘法算式，

因此我们能够列举乘数与被乘数的每一位。尔后再判断可否是满足条件即可。计算量是

45=1024

，对于计算机来说，计算量特别小。参照程序：ProgramExam12;ConstSu:Array[1..4]OfLongint=(2,3,5,7);VarA1,A2,A3,B1,B2,X,Y,S:Longint;FunctionKx(S:Longint):Boolean;{判断一个数BeginKx:=True;WhileS<>0DoBeginIfNot((SMod10)In[2,3,5,7])ThenBeginKx:=False;Exit;End;

可否是都是由素数组成

}S:=SDiv10;End;End;BeginForA1:=1To4DoForA2:=1To4DoForA3:=1To4DoForB1:=1To4DoForB2:=1To4DoBeginX:=Su[A1]*100+Su[A2]*10+Su[A3];{X为被乘数}IfX*Su[B1]<1000ThenContinue;IfX*Su[B2]<1000ThenContinue;IfX*(Su[B1]*10+Su[B2])<10000ThenContinue;{它们分别是两个四位数，一个五位数}If(Kx(X*Su[B1])=False)Or(Kx(X*Su[B2])=False)Or(Kx(X*(Su[B1]*10+Su[B2]))=False)ThenContinue;{满足其他数都是由质数组成}Writeln('',Su[A1],Su[A2],Su[A3]);Writeln('*',Su[B1],Su[B2]);Writeln('----------');Writeln('',X*Su[B2]);Writeln('',X*Su[B1]);Writeln('----------');Writeln('',X*(Su[B1]*10+Su[B2]));End;End.例13:时钟问题（10194-4）在图8所示的3*3矩阵中有9个时钟，我们的目标是旋转时钟指针，使全部时钟的指针都指向12点。赞同旋转时钟指针的方法有9种，每一种搬动用一个数字号（1，2，，9）??O?????OOOOOOOOOOOO123?OOoeoooe?OO???ooe?OOoeoooe456OOOOOOOO??OOOOOo????O???o??7呂5图8九种时钟状态表示。图2-11示出9个数字号与相应的受控制的时钟，这些时钟在图中以灰色标出，其指——受控制的时钟图9九种被控制方式针将顺时针旋转90度。输入数据：由输入文件INPUT.TXT读9个数码，这些数码给出了9个时钟时针的初始地址。数码与时刻的对应关系为：0――12点1――3点2――63――9

点点图2-11中的例子对应以下输入数据：330222212输出数据：将一个最短的搬动序列（数字序列）写入输出文件0UTPUT.TXT中，该序列要使全部的时钟指针指向12点，若有等价的多个解，仅需给出其中一个。在我们的例子中，相应的0UTPUT.TXT勺内容为：5849输入输出示例:INPUT.TXTOUTPUT.TXT3305489222212详尽的搬动方案如图10所示。5pool8[OOOlIr■—1J■kjTW^.1OQJ=>O0OOOQt==>ooo==>?oIIQQQJIpooJIQOQJtpoojQOQ图10示例搬动方案解析：第一，我们解析一下表示时钟时针初始地址的数码j(0WjW3)与时刻的对应关系：0――12点1――3点2――63――9

点点每搬动一次，时针将顺时针旋转90度。由此我们能够得出：对于任意一个时钟i(1WiW9)来说，从初始地址j出倡始码需要C=(4-j)mod4次操作，才能使得时针指向12点。而对每种搬动方法要么不采用，要么采用1次、2次或3次，由于操作四次今后，时钟将重复以前状态。因此，9种旋转方案最多产生49个状态。搬动方案采用与序次没关。样例中，最正确搬动序列为5849，同样4589序列也可达到目标。因此，求解过程中能够直接采用序列中从小至大排列的搬动序列即可。设pi表示第i种旋转方法的使用次数(0WpiW3,1WiW9)。则可能的解的会集为｛P,PP｝，该会集共含49个状态。从图2.11中，我们能够解析出9个时钟分129别被哪些方法所控制，见下表：时钟号控制时钟方案检验条件11、2、4C1=(P1+P2+P4)mod421、2、3、5C2=(P1+P2+P3+R)mod432、3、6C3=(P2+P3+P6)mod441、4、5、7G=(P计P4+P5+H)mod451、3、5、7、9G=(P计Ps+R+FV+B)mod463、5、6、9C6=(Ps+P5+P6+Pg)mod474、7、8Cz=(P4+P7+P8)mod485、7、8、9C8=(P5+PZ+P3+P9)mod496、&9Co=(P6+P3+P9)mod4因此我们能够设计以以下举算法:forp1:=0to3doforp2:=0to3doforp9:=0to3doifcl满足时钟1andc2满足时钟2and...andc9满足时钟9then打印解路径；显然，上述列举算法列举了全部49=262144个状态，运算量和运行时间颇大。我们能够采用减小可能解范围的局部列举法，仅列举第1、2、3种旋转方法可能取的43个状态，根据这三种旋转方法的当前状态值，由下述公式P4=order(C1-P1-P2);P5=order(C2-P1-P2-P3)；P6=order(C3-P2-P3)；P7=order(C4-P1-P4-P5);P8=order(C8-P5-PP9)；Pg=order(C6-P3-P5-P6);其中cmod4c0order(c^(cN4)mod4c：：0得出其他P4P9的相应状态值。尔后将P1,P2,，P9代入下述三个检验条件C5=(P1+P3+P5+P7+P9)mod4O=(P4+P7+F8)mod4C9=(P6+R+P9)mod4一一列举，以求得确实解。因此可知，上述局部列举的方法(列举状态数为43个)比较全部列举的方法(列举状态数为49个)来说，由于大幅度减少了列举量，减少运算次数，因此其时效显然改进，是一种优化了的算法。程序以下：program10194_4;constInp='input.txt';Outp='output.txt';varClock,Map:array[1..3,1..3]ofInteger;｛Clock:第((I+2)mod3)*3+J个时钟从初始时间到12点的最少搬动次数｝｛Map:最短搬动序列中，数字((I+2)mod3)*3+J的次数｝procedureInit;varI,J:Integer;beginAssign(lnput.Inp);Reset(Input);forI:=1to3do｛读入9个时钟指针的初始地址，求出每个时钟从初始到12点的最少搬动次数｝forJ:=1to3dobeginRead(Clock[l,J]);Clock[l,J]:=(4-Clock[I,J])mod4;end;Close(Input);end;functionOrder(K:Integer):Integer;varc:Integer;beginc:=k;whilec<0doinc(c,4);whilec>4thendec(c,4);Order:=k;end;procedureMain;{计算和输出最短搬动序列}varI,J,K:Integer;begin{列举最短搬动序列中数字1、2、3的个数可能取的343种状态}Assign(Output,Outp);Rewrite(Output);forMap[1,1]:=0to3doforMap[1,2]:=0to3doforMap[1,3]:=0to3dobeginMap[2,1]:=Order(Clock[1,1]-Map[1,1]-Map[1,2]);Map[2,3]:=Order(Clock[1,3]-Map[1,2]-Map[1,3]);Map[2,2]:=Order(Clock[1,2]-Map[1,1]-Map[1,2]-Map[1,3]);Map[3,1]:=Order(Clock[2,1]-Map[1,1]-Map[2,1]-Map[2,2]);Map[3,3]:=Order(Clock[2,3]-Map[1,3]-Map[2,2]-Map[2,3]);Map[3,2]:=Order(Clock[3,2]-Map[3,1]-Map[3,3]-Map[2,2]);{依照数字1、2、3个数的当前值，得出数字4~9的个数}if((Map[2,1]+Map[3,1]+Map[3,2])mod4=Clock[3,1])and((Map[2,3]+Map[3,2]+Map[3,3])mod4=Clock[3,3])and((Map[2,2]+Map[1,1]+Map[1,3]+Map[3,1]+Map[3,3])mod4=Clock[2,2])thenbegin{若数字4~9的个数满足检验条件，则输出方案}forI:=1to3doforJ:=1to3doforK:=1toMap[I,J]doWrite((I-1)*3+J);Exit;{找到一个解退后出}end;end;Writeln('NoAnswer!');Close(Output);end;beginInit;Main;end.在上例中，由于起初能够消除那些显然不属于解集的元素，使得算法效率特别高。而减少重复运算、力求提前计算所需数据、使用合适的数据结构进行算法优化等方法也是优化列举算法的常用手段。例14：最正确旅游线路（NOI94）某旅游区的街道成网格状（图2.13）。其中东西向的街道都是旅游街，南北向的街道都是林荫道。由于游客众多，旅游街被规定为单行道，游客在旅游街上只能从西向东走，在林阴道上则既可从南向北走，也能够从北向南走。阿龙想到这个旅游区游玩。他的好友阿福给了他一些建议，用分值表示全部旅游街相邻两个路口之间的街道值得旅游的程度，分值时从-100到100的整数，全部林阴道不打分。全部分值不能能全部是负分。比方图11是被打过分的某旅游区的街道图：-5036-30北17■1943-42-4334-45图11某旅游区街道示例图阿龙能够从任一个路口开始旅游，在任一个路口结束旅游。请你写一个程序，帮助阿龙找一条最正确的旅游线路，使得这条线路的全部分值总和最大。输入数据：输入文件是

INPUT.TXT

。文件的第一行是两个整数

M

和

N,之间用一个空格符分开，

M表示有多少条旅游街（

1

三

MW100

）,

N

表示有多少条林阴道（

1W

腐

xx1

）。接下来的

M

行依次给出了由北向南每条旅游街的分值信息。

每行有

个整数，依次表示了自西向东旅游街每一小段的分值。同一行相邻两个数之间用一个空格分开。输出数据：输出文件是

OUTPUT.TXT

文件只有一行，是一个整数，表示你的程序找到的最正确旅游线

路的总分值。输入输出示例：INPUT.TXT

OUTPUT.TXT-50-4736-30-2317-19-34-13-8-42-3-4334-45解析:设Lij为第I条旅游街上自西向东第J段的分值(iwIwM,1wJwN-1)。比方样例中Li2=17,L23=-34,L34=34。我们将网格状的旅游区街道以林荫道为界分为N-1个段，每一段由M条旅游街的对应段成，即第J段成为{Lu,L2J,,LM}(1WJwN-1)。由于旅游方向规定横向自西向东，纵向即可沿林阴道由南向北，亦可由北向南，而横行的街段有分值，纵行无分值,因此最正确旅游路现必定具备以下三个特点：①来自如干个连续的段，每一个段中取一个分值；②每一个分值是所在段中最大的；③起点段和终点段任意，但经过段的分值和最大。设L为第I个段中的分值最大的段。即L=Max{Ln,L21,,LM}(1w|wN-1)。比方对于样例数据：L1=Max(-50,17,-42)=17;L2=Max(-47,-19,-3)=-3;L3=Max(36,-34,-43)=36;L4=Max(-30,-13,34)=34;L5=Max(-23,-8,-45)=-8;有了以上的基础，我们便能够经过图示描述解题过程，见图12。我们把将段设为极点，所在段的最大分值设为极点的权，各极点按自西向东的序次相连,组成一条旅游路线。显然，若是确定西端为起点、东段为终点，则这条旅游路线的总分值最大。LiU图12求解过程示例图问题是某些段的最大分值可能是负值，而最优旅游路线的起点和终点任意，在这种情况下，上述旅游路线就不用然最正确了。因此，我们只能列举这条旅游路线的全部可能的子路线，从中找出一条子路线II+1J(1w|<JwN-1),使得经过极点的权和LI+L+1++LJ最大。设Best为最正确旅游路线的总分值，初始时为Sum为0当前旅游路线的总分值。我们能够获取以下算法:Best:=0;Sum:=0;forI:=1toN-2doforJ:=I+1toNSum:=Li+ifSum>Bestthen

1dobegin+LJ；Best:=Sum;end显然，这个算法的时间复杂度为0(N2)。而N在1~xx1之间，时间复杂度比较高。于是，我们必定对这个算法进行优化。依旧从极点1开始列举最优路线。若当前子路线延伸至极点I时发现总分值Sum^0,则应放弃当前子路线。由于无论LI+1为何值，当前子路线延伸至极点I+1后的总分值不会大于LI+1。因此应该从极点I+1开始重新考虑新的一条子路线。经过这种优化,能够使得算法的时间复杂度降到了0(N)。优化后的算法描述以下:Best:=0;Sum:=0;forI:=1toN—1dobeginSum:=Sum+LI;ifSum>BestthenBest:=Sum;ifSum<0thenSum:=0;end程序描述以下：{$R-,S-,Q-}{$M65520,0,655360}programNoi94;constMaxN=xx1;Inp='input.txt';0utp='output.txt';varM,N:Word;Best:Longint;Score:array[1..MaxN]ofShortInt;{旅游街数和林阴道数}{最正确旅游路线的总分值}{描述每个段的最大分值procedureInit;}varI,J,K:Integer;Buffer:array[1..40960]ofChar;beginAssign(Input,Inp);Reset(Input);SetTextBuf(Input,Buffer);Readln(M,N);FillChar(Score,Sizeof(Score),$80);forI:=1toMdo{开辟文件缓冲区}forJ:=1toN-1dobegin{读入旅游街数和林阴道数}{初始化各段的最大分值}{计算1~N-1段的最大分值}

{林阴道数的上限}{文件缓冲区}Read(K);ifK>Score[J]thenScore[J]:=K;end;Close(lnput);end;procedureOut;beginAssign(Output,Outp);Rewrite(Output);Writeln(Best);Close(Output);end;procedureMain;varI:Integer;Sum:Longint;{当前旅游路线的总分值}begin{最正确旅游路线的总分值和当前旅游路线的总分值初始化}Best:=0;Sum:=0;｛序次列举旅游路线的总分值｝forI:=1toN-1dobegin｛统计当前旅游路线的总分值｝Inc(Sum,Score[I]);｛若当前最正确，则记下｝ifSum>BestthenBest:=Sum;ifSum<0thenSum:=0;{若总分值＜0,则考虑一条新路线｝end;end;beginInit;｛输入数据｝Main;｛主过程｝Out;｛输出｝end.2019-2020年高中信息技术全国青少年奥林匹克联赛教课方案模拟法二课题：模拟法目标：知识目标：模拟的的实现能力目标：模拟的实现重点：模拟的实现难点：模拟的实现板书表示：1）模拟的引入（例31）2）模拟的应用（例32）授课过程：有些问题很难建立列举、

递归等算法，

甚至建立不了数学模型，

但能够依照问题的描述，

用程序模拟某种现象或规律，进而追踪出结果。依照模拟对象的不同样特点，能够把计算机模拟分为决定型模拟和随机行模拟两大类。决定型模拟是对决定性现象进行的模拟，其所模拟的事件依照固有则规律发生发展，而且最后有明确的结果。在这种题目中，由于数学模型中各种参数的变化多半是有规律的，因此算法设计一般不是很困难。随机模拟是模拟随机现象，由于随机现象中最少有一个不确定的因素，因此在模拟中，必定建立一个用随机值来模拟事件的进度，在随机模拟过程中，经过更正变问题的各种参数，进而观察改正这些参数所引起的状态变化。一般情况是，题目给出某一概率，设计者利用随机函数去设定在某一范围的随机值，将吻合概率的随机值作为参数。尔后依照这一模拟模型张开算法设计。随机模拟的重点是在概率已知的条件下，怎样确定随机值产生的范围。这个随机值设计得好，模拟收效就好。本节仅谈论决定性模拟问题。相关随机模拟的问题，大家能够参照一些相关书籍。例31：约瑟夫问题N

个人排成一个圆圈，尔后把这

N

个人按逆时针方向分别编号为

1、2、、

No

从编号为

1

的人开始按逆时针计数，当某人计数为

M

的倍数是，该人出圈；这样循环下去，直到圈中只有一个人留下。解析：这道题忧如用不上什么算法，只要建立一个循环链表，尔后依照题目中要求的模拟即可。算法描述以下：forI:=1toNDOP[I]:=I+1;{建立循环链表}P[N]:=1;Now:=N;repeat{模拟出圈过程}Now:=N;forI:=1toM-1doNow:=P[Now];{模拟报数}P[Now]:=P[Now[Now]];until编号为P[Now]的人出圈}{P[Now]=Now;Writeln('Thelast直到圈中只剩下一个人}{manis',Now);例32:SERNET模拟（NOI98-5）SERNET计算机网络是现代科技发展的热点，流传性能是计算机网络的主要性能指标。网络开发小组设计了一种称为SERNET勺网络，并希望开发一个模拟软件来模拟该网络的数据传输情况，进而计算出网络的传输性能。SERNET网络由服务器及连接它们的网络传输线路组成，服务器用服务器地址予以表记，网络传输线路为双向传输线路。网络传输过程中将各种传输数据分开为若干个大小同样的数据包，以数据包为单位进行传输。数据包在传输线路上传输时需要必然的传输时间，不同样的传输线路的传输时间不同样。服务器办理数据的时间较之于传输时间很小，可忽略不计。每一个数据包中除了包括详尽的数据信息外，还含有以下表记信息：①数举包编号；②数据包源服务器地址；③数据包目的服务器地址。网络传输的功能就是将一个个数据包从源服务器传输到目的服务器。对于每一个数据包，详尽的网络传输方案为：①源服务器将待发送的数据包一律复制若干份并向与之相连的全部赐予其发送该数据包。②服务器接收到一个数据包后，若是该数据包吻合下面任何一个条件：数据包的源服务器地址与本服务器地址同样数据包的目的服务器地址与本服务器地址同样本服务器已转发过与该数据包编号同样的数据包则接收该数据包；否则，服务器将其复制若干份并向它相连的全部服务器转发该数据包。这里，两台服务器“相连”的含义是它们之间有网络传输线路直接相连。现在需要你编一个程序来模拟SERNE■网络中的数据包传输情况。输入数据：输入文件的第一行为一个正整数N(N<100),表示SERNET中服务器的数目。第二行有N个互不相等的不高出100的正整数，表示每个服务器的地址。第三行有一个正整数

M

表示

SERNET

中传输线路的数目。

接下来的

M

行每行用三个正整

数表示一条传输线路连接的两台服务器的地址以及该传输线路的传输时间。

线路传输时间为不高出

100

的正整数。接下来的一行为一个正整数

K(K<10000

)，表示

SERNET

中数据包的数目。

以下的

K

行每行表示一个数据包的信息，格式为：数据包编号

初步发送时间

源服务器地址

目的服务器地址其中数据包的编号为互不同样的小于

100000

的正整数，输入文件的最后一行为一个正整数T(T<10000),T为输出时刻，输入文件中同一行相邻两项之间用一个或多个空格分开。输出数据：输出文件仅含义个整数P,表示T时刻后还在网络中传输的数据包数目(编号同样的数据包为同一数据包)。约定：①本题中全部时间量的单位均同样；②每一条传输线路上在同一时刻能传输任意多个数据包。输入输出示例：SERNET」NSERNET.OUT415742109345742642935421021093102433105710567811429323解析：很显然，本题是对平常生活中的网络文件传输进行模拟。对于模拟的事物，第一是将其抽象成数学模型。于是我们将输入文件给出的网络信息变换成一张带权无向图。

网上的服务器作为极点，服务器之间的传输线路作为无向边，

传输线路的传输时间作为边上的权。

这里要注意两点：①试题中服务器数N的上限是给定的（N<100）,能够按常例采用二维数组储藏图的信息。但问题是，服务器用服务器的地址予以表记，而这些地址是无序的。若是采用服务器地址作为数组下表，即会带来计算的不便，造成内存的无端浪费。因此我们改变服务器的表记方式，用服务器地址的输入序次表记服务器并将这些序号作为数组下标。比方：服务器地址57421093服务器表记（ID）1234②一条传输线路上的信息可能会由于有多种传输时间而重复输入多次。我们取其中最小传输时间和最大传输时间作为线路的传输时间范围。若一条传输线路的信息仅输入一次，则线路的最小传输时间的最大传输时间设为输入的传输时间。设：typeTlink=recordShort，Long:Byte;End;varLinks:array[1..N,1..N]ofTlink;

｛传输线路的时间种类｝｛最短传输时间｝｛最长传输时间｝｛网络｝F表列出了样例中的网络信息:服务器1地址（ID）服务器J地址（ID）传输时间57（1）42（2）157（1）42（2）357（1）42（2）642（2）93（4）542（2）10（3）210（3）93（4）10Links[1,2].Short=Links[2,1].Short=1Links[1,2].Long=Links[2,1].Long=6Links[2,4].Short=Links[4,2].Short=5Links[2,4].Long=Links[4,2].Long=5Links[2,3].Short=Links[3,2].Short=2Links[2,3].Long=Links[3,2].Long=2Links[3,4].Short=Links[4,3].Short=10Links[3,4].Long=Links[4,3].Long=10见图2-17图27网络传输示例图由于试题约定“每一条传输线路上在同一时刻能传输任意多个数据包”，因此数据包的传输互不影响。我们能够一个一个的模拟数据包的传输过程，从中统计出T时刻后仍在网络中传输的数据包数。现在的问题是怎样鉴识T时刻后当前一个数据包可否还在网络中传输模拟一个数据包在网络中的传输情况是算法的基础。设：it――当前数据包序号；accepted[l]---------服务器I接受it数据包的标志(1=I=N)True服务器i接受it〔False服务器i未接受it或将收到的it转发给与它相邻的全部服务器recevie[I]是服务器I向与它相连的全部服务器转发数据包的开始时刻。由于服务器处理数据的时间忽略不计，因此收到数据包的时刻即为转发时刻。Recevie[l]=$FFFF时说明当前未确定服务器I转发数据包的时刻也许服务器I已接受了ito显然，若是receive[I]<>$FFFF且accepted[I]=false，则服务器I可能立刻收到ito若是依照网络的传输方案确定服务器I已接受了it，贝Uaccepted[I]=true。开始时，it的源服务器第一将it复制若干份并同与之相连的全部服务器发送，即receive[it的源服务器]=it的源服务器的初步发送时间，其他服务器的receive值为$FFFF。此时，除可确定it的目标服务器(但不能够与it的服务器同址)为接受服务器外，其他服务器为收到it，即ifit的源服务器<>it的目标服务器thenbeginaccepted[it的目标服务器]:=true;其他服务器的accepted值设为false;end;尔后重复以下过程：在可接受it的服务器会集中搜寻一个最早收到数据包的满足手下条件的服务器min{receive[I]|(receive[I]<>$FFFF)and(accepted[I]=false)}服务器I试图向与之相连的全部服务器J(Links[l,J].Short<>0|1wJwN发送数据包。I

):若是服务器J可收到it(receive[I]+Links[I,J].Short<receive[J])，则将服务器J的receive值修正为receive[I]+Links[I,J].Short，让其在该时刻收到和转发it；若是其中一个服务器J在T时刻后才能接受来自服务器I的it(receive[I]+Links[I,J].Long>T),则判断T时刻后仍有一个数据包在网络中传输，算法结束；若是在T时刻前与服务器I相连的全部线路完成传输it的任务，则依照网络的传输方案确定服务器I接受了it，accepted[I]True，receive[I]$FFFF。这一过程素来进行到全部服务器都不再转发数据包为止，即全部服务器的receive值为$FFFF。上述算法由一个布尔函数Alive(it)描述。若数据包it在T时刻后还在网络中流传，则该函数返回True;否则返回False。算法描述以下：functionAlive(it):Boolean;BeginAlive:=True;初始化receive的值为$FFFF;Receive[it的源服务器]=it的开始发送时间初始化Accepted的值为False;Accepted[it的目标服务器]=truerepeat搜寻一个receive值最小的服务器I;ifReceive[I]=$FFFFthenBreak;ifAccepted[I]=FalsethenforJ:=1toNdobeginif服务器I与服务器J有传输线路then修正receive[J]值;if服务器J在T时刻后才能接收itthenexit;end;Accepted[I]:=True;Receive[I]:=$FFFF;untilFalse;Alive:=False;end;对每一个数据包都求一次Alive，Alive函数值为True的次数P就是T时刻后仍在网络中传输的数据包数。如下：P:=0;forI:=1to数据包数KdoifAlive(I)thenP:=P+1；Writeln(P)程序以下：{$R-,S-,Q-}programNOI98_5;constInp='sernet.in';Outp='sernet.out';MaxN=99;MaxK=9999;typeTPackage=recordSend:Word;Source:Byte;Target:Byte;end;TLink=recordShort:Byte;Long:Byte;end;varN:Byte;K:Word;T:Word;Index:array[1..MaxN]ofByte;

{输入文件名串}{输出文件名串}{服务器数的上限}{数据包数的上限}{数据包种类}{发出时刻}{源服务器}{目的服务器}{传输线的时间种类}{最短传输时间}{最长传输时间}{Ind{服务器数}e{数据包数}x{[}输出时刻P:Word;{输出时刻后还在网络中传输的数据包数}{I输入数据}]——地址为I的服务器序号}Links:array[1..MaxN,1..MaxN]ofTLink;{Links[I,J]——服务器I的服务器J的传输时间}Packages:array[1..MaxPackage]ofTPackage;{数据包序列}procedureInit;var{传输线路数}I,J:Word;{当前传输线相连的两个服务器序号}M:Word;{当前传输线路的传输时间}S1,S2:Byte;{数据包编号}Time:Word;PackageID:Longint;BeginAssign(Input,Inp);{读服务器数}Reset(Input);表}{度入每个服务器地址，计算IndexReadln(N);forI:=1toNdobeginRead(J);Index[J]:=I;end;Readln(M);{读传输线路输}FillChar(Links,Sizeof(Links),0);{Links表初始化}forI:=1toMdobegin{输入每条线路的信息}Readln(S1,S2,Time);{读相连的两台服务器地址和传输时间}S1:=Index[S1];{计算这两台服务器的序号}S2:=Index[S2];if{计(Links[S1,S2].Short=0)or(Links[S1,S2].Short>Time)then算该线路的最短传输时间和最长传输时间Links[S1,S2].Short:=Time;ifLinks[S1,S2].Long<TimethenLinks[S1,S2].Long:=Time;Links[S2,S1]:=Links[S1,S2];end;Readln(K);for{读数据包数}I:=1toKdo{读每一个数据包的信息}withPackages[I]doReadln(PackageID,Send,Source,Target);{读第I个数据包的编号，初步发送时间，源服务器地址，目的服务器地址Readln(T);{读入输出时刻}Close(Input);end;functionAlive(It:TPackage):Boolean;{模拟数据包It在T时刻还在网络中传输，则返回TrueI,J:Byte;Time:Word;Receive:array[1..MaxN]ofWord;{Receive[I]：服务器I收到下一个数据的时刻Accepted:array[1..MaxN]ofBoolean;{Accepted[I]：为服务器I接收It的标志}

;否则返回}

False}varbeginAlive:=True;FillChar(Receive,Sizeof(Receive),$FF);{初始时，全部服务器未收到任何数据包}FillChar(Accepted,Sizeof(Accepted),False);Receive[Index[It.Source]]:=It.Send;{源服务器在发送了It后开始接受下一个数据包ifIt.Source<>It.TargetthenAccepted[Index[It.Target]]:=True;

}{

若源服务器与目的服务器不同样，则确定目的服务器收到数据包