高中信息技术全国青少年奥林匹克联赛教案模拟法二

模拟法课题：模拟法目的：知识目的：模拟的的实现能力目的：模拟的实现重点：模拟的实现难点：模拟的实现板书示意：模拟的引入（例31）模拟的应用（例32）授课过程：有些问题很难建立枚举、递归等算法，甚至建立不了数学模型，但可以根据问题的描述，用程序模拟某种现象或规律，从而跟踪出结果。根据模拟对象的不同特点，可以把计算机模拟分为决定型模拟和随机行模拟两大类。决定型模拟是对决定性现象进行的模拟，其所模拟的事件按照固有则规律发生发展，并且最终有明确的结果。在这种题目中，由于数学模型中各种参数的变化多半是有规律的，所以算法设计一般不是很困难。随机模拟是模拟随机现象，由于随机现象中至少有一个不拟定的因素，因此在模拟中，必须建立一个用随机值来模拟事件的进程，在随机模拟过程中，通过修改变问题的各种参数，进而观测变更这些参数所引起的状态变化。一般情况是，题目给出某一概率，设计者运用随机函数去设定在某一范围的随机值，将符合概率的随机值作为参数。然后根据这一模拟模型展开算法设计。随机模拟的关键是在概率已知的条件下，如何拟定随机值产生的范围。这个随机值设计得好，模拟效果就好。本节仅讨论决定性模拟问题。有关随机模拟的问题，大家可以参考一些相关书籍。例31：约瑟夫问题N个人排成一个圆圈，然后把这N个人按逆时针方向分别编号为1、2、……、N。从编号为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]]; {编号为P[Now]的人出圈}untilP[Now]=Now; {直到圈中只剩下一个人}Writeln('Thelastmanis',Now);例32：SERNET模拟（NOI98-5）计算机网络是现代科技发展的热点，传播性能是计算机网络的重要性能指标。SERNET网络开发小组设计了一种称为SERNET的网络，并希望开发一个模拟软件来模拟该网络的数据传输情况，进而计算出网络的传输性能。SERNET网络由服务器及连接它们的网络传输线路组成，服务器用服务器地址予以标记，网络传输线路为双向传输线路。网络传输过程中将各种传输数据分隔为若干个大小相同的数据包，以数据包为单位进行传输。数据包在传输线路上传输时需要一定的传输时间，不同的传输线路的传输时间不同。服务器解决数据的时间较之于传输时间很小，可忽略不计。每一个数据包中除了涉及具体的数据信息外，还具有如下标记信息：数举包编号；数据包源服务器地址；数据包目的服务器地址。网络传输的功能就是将一个个数据包从源服务器传输到目的服务器。对于每一个数据包，具体的网络传输方案为：源服务器将待发送的数据包一律复制若干份并向与之相连的所有赋予其发送该数据包。服务器接受到一个数据包后，假如该数据包符合下面任何一个条件：数据包的源服务器地址与本服务器地址相同数据包的目的服务器地址与本服务器地址相同本服务器已转发过与该数据包编号相同的数据包则接受该数据包；否则，服务器将其复制若干份并向它相连的所有服务器转发该数据包。这里，两台服务器“相连”的含义是它们之间有网络传输线路直接相连。现在需要你编一个程序来模拟SERNET网络中的数据包传输情况。输入数据：输入文献的第一行为一个正整数N（N<100），表达SERNET中服务器的数目。第二行有N个互不相等的不超过100的正整数，表达每个服务器的地址。第三行有一个正整数M，表达SERNET中传输线路的数目。接下来的M行每行用三个正整数表达一条传输线路连接的两台服务器的地址以及该传输线路的传输时间。线路传输时间为不超过100的正整数。接下来的一行为一个正整数K（K<10000），表达SERNET中数据包的数目。以下的K行每行表达一个数据包的信息，格式为：数据包编号起始发送时间源服务器地址目的服务器地址其中数据包的编号为互不相同的小于100000的正整数，输入文献的最后一行为一个正整数T（T<10000），T为输出时刻，输入文献中同一行相邻两项之间用一个或多个空格隔开。输出数据：输出文献仅含义个整数P，表达T时刻后还在网络中传输的数据包数目（编号相同的数据包为同一数据包）。约定：本题中所有时间量的单位均相同；每一条传输线路上在同一时刻能传输任意多个数据包。输入输出示例：SERNET.INSERNET.OUT457421093457426429354210210931024331057105678114293231分析：很显然，本题是对平常生活中的网络文献传输进行模拟。对于模拟的事物，一方面是将其抽象成数学模型。于是我们将输入文献给出的网络信息转换成一张带权无向图。网上的服务器作为顶点，服务器之间的传输线路作为无向边，传输线路的传输时间作为边上的权。这里要注意两点：试题中服务器数N的上限是给定的（N<100），可以按惯例采用二维数组存储图的信息。但问题是，服务器用服务器的地址予以标记，而这些地址是无序的。假如采用服务器地址作为数组下表，即会带来计算的不便，导致内存的无端浪费。因此我们改变服务器的标记方式，用服务器地址的输入顺序标记服务器并将这些序号作为数组下标。例如：服务器地址57421093服务器标记（ID）1234一条传输线路上的信息也许会由于有多种传输时间而反复输入多次。我们取其中最小传输时间和最大传输时间作为线路的传输时间范围。若一条传输线路的信息仅输入一次，则线路的最小传输时间的最大传输时间设为输入的传输时间。设：typeTlink=record {传输线路的时间类型}Short， {最短传输时间}Long:Byte; {最长传输时间}End;varLinks:array[1..N,1..N]ofTlink; {网络}下表列出了样例中的网络信息：服务器I地址（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=1 Links[1,2].Long=Links[2,1].Long=6 Links[2,4].Short=Links[4,2].Short=5 Links[2,4].Long=Links[4,2].Long=5 Links[2,3].Short=Links[3,2].Short=2 Links[2,3].Long=Links[3,2].Long=2 Links[3,4].Short=Links[4,3].Short=10 图27网络传输示例图Links[3,4].Long=Links[4,3].Long=10图27网络传输示例图见图2-17由于试题约定“每一条传输线路上在同一时刻能传输任意多个数据包”，因此数据包的传输互不影响。我们可以一个一个的模拟数据包的传输过程，从中记录出T时刻后仍在网络中传输的数据包数。现在的问题是如何判别T时刻后当前一个数据包是否还在网络中传输模拟一个数据包在网络中的传输情况是算法的基础。设：it——当前数据包序号；accepted[I]——服务器I接受it数据包的标志（1≦I≦N）recevie[I]是服务器I向与它相连的所有服务器转发数据包的开始时刻。由于服务器解决数据的时间忽略不计，因此收到数据包的时刻即为转发时刻。Recevie[I]=$FFFF时说明当前未拟定服务器I转发数据包的时刻或者服务器I已接受了it。显然，假如receive[I]<>$FFFF且accepted[I]=false，则服务器I也许即将收到it。假如按照网络的传输方案拟定服务器I已接受了it，则accepted[I]=true。开始时，it的源服务器一方面将it复制若干份并同与之相连的所有服务器发送，即receive[it的源服务器]=it的源服务器的起始发送时间，其余服务器的receive值为$FFFF。此时，除可拟定it的目的服务器（但不能与it的服务器同址）为接受服务器外，其余服务器为收到it，即ifit的源服务器<>it的目的服务器thenbeginaccepted[it的目的服务器]:=true；其余服务器的accepted值设为false；end；然后反复如下过程：在可接受it的服务器集合中寻找一个最早收到数据包的满足下属条件的服务器I：min{receive[I]|（receive[I]<>$FFFF）and（accepted[I]=false）}服务器I试图向与之相连的所有服务器J（Links[I,J].Short<>0|1≦J≦N）发送数据包。假如服务器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=record {数据包类型}Send:Word; {发出时刻}Source:Byte; {源服务器}Target:Byte; {目的服务器}end;TLink=record {传输线的时间类型}Short:Byte; {最短传输时间}Long:Byte; {最长传输时间}end;varN:Byte; {服务器数}K:Word; {数据包数}T:Word; {输出时刻}P:Word; {输出时刻后还在网络中传输的数据包数}Index:array[1..MaxN]ofByte; {Index[I]——地址为I的服务器序号}Links:array[1..MaxN,1..MaxN]ofTLink; {Links[I,J]——服务器I的服务器J的传输时间}Packages:array[1..MaxPackage]ofTPackage; {数据包序列}procedureInit; {输入数据}varI,J:Word;M:Word; {传输线路数}S1,S2:Byte; {当前传输线相连的两个服务器序号}Time:Word; {当前传输线路的传输时间}PackageID:Longint; {数据包编号}Begin Assign(Input,Inp); Reset(Input); Readln(N); {读服务器数}forI:=1toNdobegin {度入每个服务器地址，计算Index表}Read(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); {读数据包数}forI:=1toKdo {读每一个数据包的信息}withPackages[I]doReadln(PackageID,Send,Source,Target);{读第I个数据包的编号，起始发送时间，源服务器地址，目的服务器地址}Readln(T); {读入输出时刻}Close(Input);end;functionAlive(It:TPackage):Boolean;{模拟数据包It在T时刻还在网络中传输，则返回True；否则返回False}varI,J:Byte;Time:Word;Receive:array[1..MaxN]ofWord; {Receive[I]：服务器I收到下一个数据的时刻}Accepted:array[1..MaxN]ofBoolean; {Accepted[I]：为服务器I接受It的标志}beginAlive:=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;{若源服务器与目的服务器不同，则拟定目的服务器收到数据包It}repeatI:=1; {计算最早收到下一个数据包的服务器I}forJ:=2toNdo ifReceive[J]<Receive[I]thenI:=J;ifReceive[I]=$FFFFthenBreak; {若所有服务器收到It，则返回false}ifnotAccepted[I]thenbegin{若服务器未接受数据包It，则搜索与服务器I相连的服务器}forJ:=1toNdoifLinks[I,J].Short<>0thenbeginTime:=Receive[I]+Links[I,J].Short; ifTime<Receive[J]thenReceive[J]:=Time;{若服务器J能在Receive[J]前收到来自服务器I发来的数据包}ifReceive[I]+Links[I,J].Long>TthenExit;{若在该线路上传输It将超是，则返回True}end;Accepted[I]:=True; {设定服务器I收到It标志}end;Receive[I]:=$FFFF; {设服务器I转发过It标志}untilFalse;Alive:=False; {It在TimeLine时刻前结束传输}end;procedureMain; {记录T时刻后还在网络中传输的数据包数}varY:Word;beginP:=0;forY:=1toKdoifAlive(Packages[Y])thenInc(P);end;procedureOut; {输出}beginAssign(Output,Outp);Rewrite(Output);Writeln(P);Close(Output);end;beginInit; Main; Out; end.习题1．多精度值解决古印度国王要褒奖他的聪明能干的宰相达依尔（国际象棋的发明者），问他要什么。达依尔回答：“殿下只要在棋盘上第一个格子放一粒麦粒，在第二个格子放两粒，在第三个格子放四粒，以后的格子都是前一格的两倍。如此放满64格，我就心满意足了。”国王想，这不难办到。但一袋麦子不久就用完了，一仓库也用完了，全印度的麦子也远远不够。请编程计算所需的麦子总数。2．逻辑判断题来自不同国家的四位留学生A,B,C,D在一起交谈,他们只会中、英、法、日四种语言中的2种,情况是,没有人既会日语又会法语;A会日语,但D不会,A和D能互相交谈,B不会英语,但A和C交谈时却要B当翻译,B,C,D三个想互相交谈,但找不到共同的语言,只有一种语言3人都会,编程拟定A,B