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

2019-2020年高中信息技术 全国青少年奥林匹克联赛教案 模拟法二课题：模拟法目标：知识目标：模拟的的实现能力目标：模拟的实现重点：模拟的实现难点：模拟的实现板书示意：1） 模拟的引入（例31）2） 模拟的应用（例32）授课过程：有些问题很难建立枚举、递归等算法，甚至建立不了数学模型，但可以根据问题的描述，用程序模拟某种现象或规律，从而跟踪出结果。根据模拟对象的不同特点，可以把计算机模拟分为决定型模拟和随机行模拟两大类。决定型模拟是对决定性现象进行的模拟，其所模拟的事件按照固有则规律发生发展，并且最终有明确的结果。在这种题目中，由于数学模型中各种参数的变化多半是有规律的，所以算法设计一般不是很困难。随机模拟是模拟随机现象，由于随机现象中至少有一个不确定的因素，因此在模拟中，必须建立一个用随机值来模拟事件的进程，在随机模拟过程中，通过修改变问题的各种参数，进而观察变更这些参数所引起的状态变化。一般情况是，题目给出某一概率，设计者利用随机函数去设定在某一范围的随机值，将符合概率的随机值作为参数。然后根据这一模拟模型展开算法设计。随机模拟的关键是在概率已知的条件下，如何确定随机值产生的范围。这个随机值设计得好，模拟效果就好。本节仅讨论决定性模拟问题。有关随机模拟的问题，大家可以参考一些相关书籍。例31：约瑟夫问题N个人排成一个圆圈，然后把这N个人按逆时针方向分别编号为1、2、N。从编号为1的人开始按逆时针计数，当某人计数为M的倍数是，该人出圈；如此循环下去，直到圈中只有一个人留下。分析：这道题似乎用不上什么算法，只需建立一个循环链表，然后按照题目中要求的模拟即可。算法描述如下：for I := 1 to N DO PI := I + 1; 建立循环链表PN := 1;Now := N;repeat 模拟出圈过程 Now := N; for I := 1 to M - 1 do Now := PNow; 模拟报数 PNow := PNowNow; 编号为PNow的人出圈until PNow = Now; 直到圈中只剩下一个人Writeln(The last man is , Now);例32：SERNET模拟（NOI98-5）计算机网络是现代科技发展的热点，传播性能是计算机网络的主要性能指标。SERNET网络开发小组设计了一种称为SERNET的网络，并希望开发一个模拟软件来模拟该网络的数据传输情况，进而计算出网络的传输性能。SERNET网络由服务器及连接它们的网络传输线路组成，服务器用服务器地址予以标识，网络传输线路为双向传输线路。网络传输过程中将各种传输数据分隔为若干个大小相同的数据包，以数据包为单位进行传输。数据包在传输线路上传输时需要一定的传输时间，不同的传输线路的传输时间不同。服务器处理数据的时间较之于传输时间很小，可忽略不计。每一个数据包中除了包括具体的数据信息外，还含有如下标识信息： 数举包编号； 数据包源服务器地址； 数据包目的服务器地址。网络传输的功能就是将一个个数据包从源服务器传输到目的服务器。对于每一个数据包，具体的网络传输方案为： 源服务器将待发送的数据包一律复制若干份并向与之相连的所有赋予其发送该数据包。 服务器接收到一个数据包后，如果该数据包符合下面任何一个条件：l 数据包的源服务器地址与本服务器地址相同l 数据包的目的服务器地址与本服务器地址相同l 本服务器已转发过与该数据包编号相同的数据包则接收该数据包；否则，服务器将其复制若干份并向它相连的所有服务器转发该数据包。这里，两台服务器“相连”的含义是它们之间有网络传输线路直接相连。现在需要你编一个程序来模拟SERNET网络中的数据包传输情况。输入数据：输入文件的第一行为一个正整数N（N100），表示SERNET中服务器的数目。第二行有N个互不相等的不超过100的正整数，表示每个服务器的地址。第三行有一个正整数M，表示SERNET中传输线路的数目。接下来的M行每行用三个正整数表示一条传输线路连接的两台服务器的地址以及该传输线路的传输时间。线路传输时间为不超过100的正整数。接下来的一行为一个正整数K（K10000），表示SERNET中数据包的数目。以下的K行每行表示一个数据包的信息，格式为：数据包编号 起始发送时间 源服务器地址 目的服务器地址其中数据包的编号为互不相同的小于100000的正整数，输入文件的最后一行为一个正整数T（T10000），T为输出时刻，输入文件中同一行相邻两项之间用一个或多个空格隔开。输出数据：输出文件仅含义个整数P，表示T时刻后还在网络中传输的数据包数目（编号相同的数据包为同一数据包）。约定： 本题中所有时间量的单位均相同； 每一条传输线路上在同一时刻能传输任意多个数据包。输入输出示例：SERNET.INSERNET.OUT457 42 10 93457 42 642 93 542 10 210 93 102433 10 57 105678 11 42 9323 1分析：很显然，本题是对日常生活中的网络文件传输进行模拟。对于模拟的事物，首先是将其抽象成数学模型。于是我们将输入文件给出的网络信息转换成一张带权无向图。网上的服务器作为顶点，服务器之间的传输线路作为无向边，传输线路的传输时间作为边上的权。这里要注意两点： 试题中服务器数N的上限是给定的（N100），可以按惯例采用二维数组存储图的信息。但问题是，服务器用服务器的地址予以标识，而这些地址是无序的。如果采用服务器地址作为数组下表，即会带来计算的不便，造成内存的无端浪费。因此我们改变服务器的标识方式，用服务器地址的输入顺序标识服务器并将这些序号作为数组下标。例如：服务器地址57421093服务器标识（ID）1234 一条传输线路上的信息可能会因为有多种传输时间而重复输入多次。我们取其中最小传输时间和最大传输时间作为线路的传输时间范围。若一条传输线路的信息仅输入一次，则线路的最小传输时间的最大传输时间设为输入的传输时间。设：type Tlink = record传输线路的时间类型 Short， 最短传输时间 Long: Byte;最长传输时间 End;var Links: array 1 . N, 1 . N of Tlink; 网络下表列出了样例中的网络信息：服务器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）10Links1, 2.Short = Links2, 1.Short = 1Links1,2.Long = Links2, 1.Long = 6 Links2, 4.Short = Links4, 2.Short = 5Links2,4.Long = Links4, 2.Long = 5 Links2, 3.Short = Links3, 2.Short = 2Links2,3.Long = Links3, 2.Long = 2 Links3, 4.Short = Links4, 3.Short = 10图27 网络传输示例图Links3,4.Long = Links4, 3.Long = 10见图2-17由于试题约定“每一条传输线路上在同一时刻能传输任意多个数据包”，因此数据包的传输互不影响。我们可以一个一个的模拟数据包的传输过程，从中统计出T时刻后仍在网络中传输的数据包数。现在的问题是如何判别T时刻后当前一个数据包是否还在网络中传输模拟一个数据包在网络中的传输情况是算法的基础。设：it当前数据包序号；acceptedI服务器I接受it数据包的标志（1IN）recevieI是服务器I向与它相连的所有服务器转发数据包的开始时刻。由于服务器处理数据的时间忽略不计，因此收到数据包的时刻即为转发时刻。RecevieI = $FFFF时说明当前未确定服务器I转发数据包的时刻或者服务器I已接受了it。显然，如果receiveI $FFFF且acceptedI = false，则服务器I可能即将收到it。如果按照网络的传输方案确定服务器I已接受了it，则acceptedI = true。开始时，it的源服务器首先将it复制若干份并同与之相连的所有服务器发送，即receiveit的源服务器=it的源服务器的起始发送时间，其余服务器的receive值为$FFFF。此时，除可确定it的目标服务器（但不能与it的服务器同址）为接受服务器外，其余服务器为收到it，即if it的源服务器it的目标服务器 then begin acceptedit的目标服务器:=true； 其余服务器的accepted值设为false；end；然后重复如下过程：在可接受it的服务器集合中寻找一个最早收到数据包的满足下属条件的服务器I：minreceiveI |（receiveI $FFFF）and（acceptedI = false）服务器I试图向与之相连的所有服务器J（LinksI, J.Short 0 | 1 J N）发送数据包。如果服务器J可收到it（receiveI + LinksI, J.Short T），则判定T时刻后仍有一个数据包在网络中传输，算法结束；如果在T时刻前与服务器I相连的所有线路完成传输it的任务，则按照网络的传输方案确定服务器I接受了it，acceptedITrue，receiveI$FFFF。这一过程一直进行到所有服务器都不再转发数据包为止，即所有服务器的receive值为$FFFF。上述算法由一个布尔函数Alive（it）描述。若数据包it在T时刻后还在网络中传播，则该函数返回True；否则返回False。算法描述如下：function Alive(it): Boolean; Begin Alive := True; 初始化receive的值为$FFFF; Receiveit的源服务器 = it的开始发送时间 初始化Accepted的值为False; Acceptedit的目标服务器 = true repeat 寻找一个receive值最小的服务器I; if ReceiveI = $FFFF then Break ; if AcceptedI = False then for J := 1 to N do begin if 服务器I与服务器J有传输线路 then 修正receiveJ值; if 服务器J在T时刻后才能接收it then exit; end; AcceptedI := True; ReceiveI := $FFFF; until False; Alive := False; end;对每一个数据包都求一次Alive，Alive函数值为True的次数P就是T时刻后仍在网络中传输的数据包数。如下：P := 0;for I := 1 to 数据包数K do if Alive(I) then P := P + 1；Writeln(P)程序如下：$R-,S-,Q-program NOI98_5; const Inp = sernet.in;输入文件名串 Outp = sernet.out;输出文件名串 MaxN = 99;服务器数的上限 MaxK = 9999;数据包数的上限 type TPackage = record数据包类型 Send: Word;发出时刻 Source: Byte;源服务器 Target: Byte;目的服务器 end; TLink = record传输线的时间类型 Short: Byte;最短传输时间 Long: Byte;最长传输时间 end; var N: Byte;服务器数 K: Word;数据包数 T: Word;输出时刻 P: Word;输出时刻后还在网络中传输的数据包数 Index: array 1 . MaxN of Byte; IndexI地址为I的服务器序号 Links: array 1 . MaxN, 1. MaxN of TLink; LinksI, J服务器I的服务器J的传输时间 Packages: array 1 . MaxPackage of TPackage; 数据包序列 procedure Init;输入数据 var I, J: Word; M: Word;传输线路数 S1, S2: Byte;当前传输线相连的两个服务器序号 Time: Word; 当前传输线路的传输时间 PackageID: Longint;数据包编号 Begin Assign(Input, Inp); Reset(Input); Readln(N);读服务器数 for I := 1 to N do begin 度入每个服务器地址，计算Index表 Read(J); IndexJ := I; end; Readln(M);读传输线路输 FillChar(Links, Sizeof(Links), 0);Links表初始化 for I := 1 to M do begin 输入每条线路的信息 Readln(S1, S2, Time);读相连的两台服务器地址和传输时间 S1 := IndexS1;计算这两台服务器的序号 S2 := IndexS2; if (LinksS1,S2.Short=0)or(LinksS1,S2.ShortTime) then计算该线路的最短传输时间和最长传输时间 LinksS1, S2.Short := Time; if LinksS1, S2.Long Time then LinksS1, S2.Long := Time; LinksS2, S1 := LinksS1, S2; end; Readln(K);读数据包数 for I := 1 to K do读每一个数据包的信息 with PackagesI do Readln(PackageID, Send, Source, Target); 读第I个数据包的编号，起始发送时间，源服务器地址，目的服务器地址 Readln(T);读入输出时刻 Close(Input); end;function Alive(It: TPackage): Boolean;模拟数据包It在T时刻还在网络中传输，则返回True；否则返回False var I, J: Byte; Time: Word; Receive: array 1 . MaxN of Word;ReceiveI：服务器I收到下一个数据的时刻 Accepted: array 1.MaxN of Boolean; AcceptedI：为服务器I接收It的标志 begin Alive := True; FillChar(Receive, Sizeof(Receive), $FF); 初始时，所有服务器未收到任何数据包 FillChar(Accepted, Sizeof(Accepted), False); ReceiveIndexIt.Source := It.Send; 源服务器在发送了It后开始接受下一个数据包 if It.Source It.Target then AcceptedIndexIt.Target := True; 若源服务器与目的服务器不同，则确定目的服务器收到数据包It repeat I := 1;计算最早收到下一个数据包的服务器I for J := 2 to N do if ReceiveJ ReceiveI then I := J; if ReceiveI = $FFFF then Break;若所有服务器收到It，则返回false if not AcceptedI then begin 若服务器未接收数据包It，则搜索与服务器I相连的服务器 for J := 1 to N do if LinksI, J.Short 0 then begin Time := ReceiveI + LinksI, J.Short; if Time T then Exit; 若在该线路上传输It将超是，则返回True end; AcceptedI := True;设定服务器I收到It标志 end; ReceiveI := $FFFF;设服务器I转发过It标志 until False; Alive := False;It在TimeLine时刻前结束传输 end;procedure Main;统计T时刻后还在网络中传输的数据包数 var Y: Word; begin P := 0; for Y := 1 to K do if Alive(PackagesY) then Inc(P); end; procedure Out;输出 begin Assign(Output, Outp); Rewrite(Output); Writeln(P); Close(Output); end; begin Init; 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,C,D四位留学生各会哪两种语言。3枚举排列数任意输入由小写字母组成的字符串（长度不超过15），求从中取出K个小写字母的排列和排列总数。4货郎担问题。某售货员要到若干个村庄售货，各个村庄的路程是已知的，为了提高效率，售货员决定从商店出发到每个村庄售一次货然后返回商店，问他应选择一条什么样的路径，才能使走的总路程最短。输入:从文本文件读入N(第一行)，表示一个商店和N-1个村庄。其下N行为一个N*N的矩阵，每个矩阵元素(i，j)的值表示从i村庄(或商店)到j村庄(或商店)的距离。i=1或j=1表示商店。数值均为整数，数值之间用空格隔开。输出:在屏幕上输出从商店出发经过每一个村庄一次，最后返回商店的路线(第一行)输出最短路线长度(第二行)。5汽油花费一些旅行车从城市A到城市B运送包裹。在沿途由很多价格不同的加油站。第一个加油站的位置在路程的开始。旅行车的油箱容积可能不同，车在沿途需要及时给油箱加油，我们假设，每个油站有足够的油。输入：在文本文件中的第一行为一个整数p表示油箱的容量, 1 p = 1000000. 在第二行有一个整数n表是沿途加油站的数目。1 n = 1000000。接下来的n行每行有两个用单个正整数分隔的整数ci, di, 其中ci表示第I油站的价格。di 表示I和第(i+1)个油站的距离- (dn 就是最后一个油站到结束点的距离)。1 = ci = 1000, 1 = di = 1000000。AB的路线长度(所有di之和) 不超过1000000输出：路线AB中加油的最少花费. 6剔除多余括号键盘输入一个含有括号的四则运算表式，可能含有多余的括号，编程整理该表达式，去掉所有多余的括号，原表达式中所有变量和运算符相对位置保持不变，并保持与原表达式等价。例：输入表达式应输出表达式a+(b+c) a+b+c (a*b)+c/d a*b+c/d a+b/(c-d) a+b/(c-d) 注意输入a+b时不能输出b+a。表达式以字符串输入，长度不超过255。输入不要判错。所有变量为单个小写字母。只是要求去掉所有多余括号，不要求对表达式化简