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

《高中信息技术 全国青少年奥林匹克联赛教案 模拟法二》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、模拟法课题：模拟法目标：知识目标：模拟的的实现能力目标：模拟的实现重点：模拟的实现难点：模拟的实现板书示意：1）模拟的引入（例31）2）模拟的应用（例32）授课过程：有些问题很难建立枚举、递归等算法，甚至建立不了数学模型，但可以根据问题的描述，用程序模拟某种现象或规律，从而跟踪出结果。根据模拟对象的不同特点，可以把计算机模拟分为决定型模拟和随机行模拟两大类。决定型模拟是对决定性现象进行的模拟，其所模拟的事件按照固有则规律发生发展，并且最终有明确的结果。在这种题目中，由于数学模型中各种参数的变化多半是有规律的，所以算法设计一般不是很困难。随机模拟是模拟随机现象，由于随

2、机现象中至少有一个不确定的因素，因此在模拟中，必须建立一个用随机值来模拟事件的进程，在随机模拟过程中，通过修改变问题的各种参数，进而观察变更这些参数所引起的状态变化。一般情况是，题目给出某一概率，设计者利用随机函数去设定在某一范围的随机值，将符合概率的随机值作为参数。然后根据这一模拟模型展开算法设计。随机模拟的关键是在概率已知的条件下，如何确定随机值产生的范围。这个随机值设计得好，模拟效果就好。本节仅讨论决定性模拟问题。有关随机模拟的问题，大家可以参考一些相关书籍。例31：约瑟夫问题N个人排成一个圆圈，然后把这N个人按逆时针方向分别编号为1、2、……、N。从编号为1

3、的人开始按逆时针计数，当某人计数为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);例

4、32：SERNET模拟（NOI98-5）计算机网络是现代科技发展的热点，传播性能是计算机网络的主要性能指标。SERNET网络开发小组设计了一种称为SERNET的网络，并希望开发一个模拟软件来模拟该网络的数据传输情况，进而计算出网络的传输性能。SERNET网络由服务器及连接它们的网络传输线路组成，服务器用服务器地址予以标识，网络传输线路为双向传输线路。网络传输过程中将各种传输数据分隔为若干个大小相同的数据包，以数据包为单位进行传输。数据包在传输线路上传输时需要一定的传输时间，不同的传输线路的传输时间不同。服务器处理数据的时间较之于传输时间很小，可忽略不计。每一个数据包

5、中除了包括具体的数据信息外，还含有如下标识信息：①数举包编号；②数据包源服务器地址；③数据包目的服务器地址。网络传输的功能就是将一个个数据包从源服务器传输到目的服务器。对于每一个数据包，具体的网络传输方案为：①源服务器将待发送的数据包一律复制若干份并向与之相连的所有赋予其发送该数据包。②服务器接收到一个数据包后，如果该数据包符合下面任何一个条件：l数据包的源服务器地址与本服务器地址相同l数据包的目的服务器地址与本服务器地址相同l本服务器已转发过与该数据包编号相同的数据包则接收该数据包；否则，服务器将其复制若干份并向它相连的所有服务器转发该数据包。这里，两台服务器“相

6、连”的含义是它们之间有网络传输线路直接相连。现在需要你编一个程序来模拟SERNET网络中的数据包传输情况。输入数据：输入文件的第一行为一个正整数N（N<100），表示SERNET中服务器的数目。第二行有N个互不相等的不超过100的正整数，表示每个服务器的地址。第三行有一个正整数M，表示SERNET中传输线路的数目。接下来的M行每行用三个正整数表示一条传输线路连接的两台服务器的地址以及该传输线路的传输时间。线路传输时间为不超过100的正整数。接下来的一行为一个正整数K（K<10000），表示SERNET中数据包的数目。以下的K行每行表示一个数据包的信息，格式为：数据包

7、编号起始发送时间源服务器地址目的服务器地址其中数据包的编号为互不相同的小于100000的正整数，输入文件的最后一行为一个正整数T（T<10000），T为输出时刻，输入文件中同一行相邻两项之间用一个或多个空格隔开。输出数据：输出文件仅含义个整数P，表示T时刻后还在网络中传输的数据包数目（编号相同的数据包为同一数据包）。约定：①本题中所有时间量的单位均相同；②每一条传输线路上在同一时刻能传输任意多个数据包。输入输出示例：SERNET.INSERNET.OUT457421093457426429354210210931024331057105678114293231分