模拟法
课题：模拟法 目标：
知识目标：模拟的的实现 能力目标：模拟的实现 重点：模拟的实现 难点：模拟的实现 板书示意：
1） 模拟的引入（例31） 2） 模拟的应用（例32）
授课过程：
有些问题很难建立枚举、递归等算法，甚至建立不了数学模型，但可以根据问题的描述，用程序模拟某种现象或规律，从而跟踪出结果。
根据模拟对象的不同特点，可以把计算机模拟分为决定型模拟和随机行模拟两大类。 决定型模拟是对决定性现象进行的模拟，其所模拟的事件按照固有则规律发生发展，并且最终有明确的结果。在这种题目中，由于数学模型中各种参数的变化多半是有规律的，所以算法设计一般不是很困难。
随机模拟是模拟随机现象，由于随机现象中至少有一个不确定的因素，因此在模拟中，必须建立一个用随机值来模拟事件的进程，在随机模拟过程中，通过修改变问题的各种参数，进而观察变更这些参数所引起的状态变化。一般情况是，题目给出某一概率，设计者利用随机函数去设定在某一范围的随机值，将符合概率的随机值作为参数。然后根据这一模拟模型展开算法设计。随机模拟的关键是在概率已知的条件下，如何确定随机值产生的范围。这个随机值设计得好，模拟效果就好。本节仅讨论决定性模拟问题。有关随机模拟的问题，大家可以参考一些相关书籍。
例31：约瑟夫问题
N个人排成一个圆圈，然后把这N个人按逆时针方向分别编号为1、2、……、N。从编号为1的人开始按逆时针计数，当某人计数为M的倍数是，该人出圈；如此循环下去，直到圈中只有一个人留下。
分析：这道题似乎用不上什么算法，只需建立一个循环链表，然后按照题目中要求的模拟即可。
算法描述如下：
for I := 1 to N DO P[I] := I + 1; {建立循环链表} P[N] := 1; Now := N; repeat {模拟出圈过程} Now := N; for I := 1 to M - 1 do 1
Now := P[Now]; {模拟报数} P[Now] := P[Now[Now]]; {编号为P[Now]的人出圈} until P[Now] = Now; {直到圈中只剩下一个人} Writeln('The last man is ', 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时刻后还在网络中传输的数据包数目（编号相同的数
2
据包为同一数据包）。
约定：
① 本题中所有时间量的单位均相同；
② 每一条传输线路上在同一时刻能传输任意多个数据包。 输入输出示例： SERNET.IN 4 57 42 10 93 4 57 42 6 42 93 5 42 10 2 10 93 10 2 433 10 57 10 5678 11 42 93 23 SERNET.OUT 1 分析：
很显然，本题是对日常生活中的网络文件传输进行模拟。对于模拟的事物，首先是将其抽象成数学模型。于是我们将输入文件给出的网络信息转换成一张带权无向图。网上的服务器作为顶点，服务器之间的传输线路作为无向边，传输线路的传输时间作为边上的权。这里要注意两点：
① 试题中服务器数N的上限是给定的（N<100），可以按惯例采用二维数组存储图的信息。但问题是，服务器用服务器的地址予以标识，而这些地址是无序的。如果采用服务器地址作为数组下表，即会带来计算的不便，造成内存的无端浪费。因此我们改变服务器的标识方式，用服务器地址的输入顺序标识服务器并将这些序号作为数组下标。例如： 服务器地址 服务器标识（ID） 57 1 42 2 10 3 93 4 ② 一条传输线路上的信息可能会因为有多种传输时间而重复输入多次。我们取其中最小传输时间和最大传输时间作为线路的传输时间范围。若一条传输线路的信息仅输入一次，则线路的最小传输时间的最大传输时间设为输入的传输时间。设：
type
Tlink = record {传输线路的时间类型} Short， {最短传输时间} Long: Byte; {最长传输时间} End; var
Links: array [1 .. N, 1 .. N] of Tlink; {网络}
下表列出了样例中的网络信息： 服务器I地址（ID） 57（1） 57（1）
服务器J地址（ID） 42（2） 42（2） 传输时间 1 3 3
57（1） 42（2） 42（2） 10（3） 42（2） 93（4） 10（3） 93（4）
6 5 2 10 Links[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 Links[3,4].Long = Links[4, 3].Long = 10 见图2-17
图27 网络传输示例图
由于试题约定“每一条传输线路上在同一时刻能传输任意多个数据包”，因此数据包的传输互不影响。我们可以一个一个的模拟数据包的传输过程，从中统计出T时刻后仍在网络中传输的数据包数。
现在的问题是如何判别T时刻后当前一个数据包是否还在网络中传输 模拟一个数据包在网络中的传输情况是算法的基础。 设：
it——当前数据包序号；
accepted[I]——服务器I接受it数据包的标志（1≦I≦N）
Trueaccepted[I]???False?服务器i接受it
服务器i未接受it或将收到的it转发给与它相邻的所有服务器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的服务器同址）为接受服务器外，其余服务
4
器为收到it，即
if it的源服务器<>it的目标服务器 then begin accepted[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。
算法描述如下：
function Alive(it): Boolean; Begin Alive := True; 初始化receive的值为$FFFF; Receive[it的源服务器] = it的开始发送时间 初始化Accepted的值为False; Accepted[it的目标服务器] = true repeat 寻找一个receive值最小的服务器I; if Receive[I] = $FFFF then Break ; if Accepted[I] = False then for J := 1 to N do begin if 服务器I与服务器J有传输线路 then 修正receive[J]值; if 服务器J在T时刻后才能接收it then exit; end; Accepted[I] := True; Receive[I] := $FFFF; until False; Alive := False; end;
5
高中信息技术 全国青少年奥林匹克联赛教案 模拟法二
