高中信息技術 全國青少年奧林匹克聯(lián)賽教案 模擬法二

1、模擬法課題：模擬法目標：知識目標：模擬的的實現(xiàn)能力目標：模擬的實現(xiàn)重點：模擬的實現(xiàn)難點：模擬的實現(xiàn)板書示意：1） 模擬的引入（例31）2） 模擬的應用（例32）授課過程：有些問題很難建立枚舉、遞歸等算法，甚至建立不了數(shù)學模型，但可以根據問題的描述，用程序模擬某種現(xiàn)象或規(guī)律，從而跟蹤出結果。根據模擬對象的不同特點，可以把計算機模擬分為決定型模擬和隨機行模擬兩大類。決定型模擬是對決定性現(xiàn)象進行的模擬，其所模擬的事件按照固有則規(guī)律發(fā)生發(fā)展，并且最終有明確的結果。在這種題目中，由于數(shù)學模型中各種參數(shù)的變化多半是有規(guī)律的，所以算法設計一般不是很困難。隨機模擬是模擬隨機現(xiàn)象，由于隨機現(xiàn)象中至少有一個不確定

2、的因素，因此在模擬中，必須建立一個用隨機值來模擬事件的進程，在隨機模擬過程中，通過修改變問題的各種參數(shù)，進而觀察變更這些參數(shù)所引起的狀態(tài)變化。一般情況是，題目給出某一概率，設計者利用隨機函數(shù)去設定在某一范圍的隨機值，將符合概率的隨機值作為參數(shù)。然后根據這一模擬模型展開算法設計。隨機模擬的關鍵是在概率已知的條件下，如何確定隨機值產生的范圍。這個隨機值設計得好，模擬效果就好。本節(jié)僅討論決定性模擬問題。有關隨機模擬的問題，大家可以參考一些相關書籍。例31：約瑟夫問題N個人排成一個圓圈，然后把這N個人按逆時針方向分別編號為1、2、N。從編號為1的人開始按逆時針計數(shù)，當某人計數(shù)為M的倍數(shù)是，該人出圈；如

3、此循環(huán)下去，直到圈中只有一個人留下。分析：這道題似乎用不上什么算法，只需建立一個循環(huán)鏈表，然后按照題目中要求的模擬即可。算法描述如下：for I := 1 to N DO PI := I + 1; 建立循環(huán)鏈表PN := 1;Now := N;repeat 模擬出圈過程 Now := N; for I := 1 to M - 1 do Now := PNow; 模擬報數(shù) PNow := PNowNow; 編號為PNow的人出圈until PNow = Now; 直到圈中只剩下一個人Writeln('The last man is ', Now);例32：SERNET模擬（NOI

4、98-5）計算機網絡是現(xiàn)代科技發(fā)展的熱點，傳播性能是計算機網絡的主要性能指標。SERNET網絡開發(fā)小組設計了一種稱為SERNET的網絡，并希望開發(fā)一個模擬軟件來模擬該網絡的數(shù)據傳輸情況，進而計算出網絡的傳輸性能。SERNET網絡由服務器及連接它們的網絡傳輸線路組成，服務器用服務器地址予以標識，網絡傳輸線路為雙向傳輸線路。網絡傳輸過程中將各種傳輸數(shù)據分隔為若干個大小相同的數(shù)據包，以數(shù)據包為單位進行傳輸。數(shù)據包在傳輸線路上傳輸時需要一定的傳輸時間，不同的傳輸線路的傳輸時間不同。服務器處理數(shù)據的時間較之于傳輸時間很小，可忽略不計。每一個數(shù)據包中除了包括具體的數(shù)據信息外，還含有如下標識信息： 數(shù)舉包編

5、號； 數(shù)據包源服務器地址； 數(shù)據包目的服務器地址。網絡傳輸?shù)墓δ芫褪菍⒁粋€個數(shù)據包從源服務器傳輸?shù)侥康姆掌?。對于每一個數(shù)據包，具體的網絡傳輸方案為： 源服務器將待發(fā)送的數(shù)據包一律復制若干份并向與之相連的所有賦予其發(fā)送該數(shù)據包。 服務器接收到一個數(shù)據包后，如果該數(shù)據包符合下面任何一個條件：l 數(shù)據包的源服務器地址與本服務器地址相同l 數(shù)據包的目的服務器地址與本服務器地址相同l 本服務器已轉發(fā)過與該數(shù)據包編號相同的數(shù)據包則接收該數(shù)據包；否則，服務器將其復制若干份并向它相連的所有服務器轉發(fā)該數(shù)據包。這里，兩臺服務器“相連”的含義是它們之間有網絡傳輸線路直接相連?，F(xiàn)在需要你編一個程序來模擬SERNE

6、T網絡中的數(shù)據包傳輸情況。輸入數(shù)據：輸入文件的第一行為一個正整數(shù)N（N<100），表示SERNET中服務器的數(shù)目。第二行有N個互不相等的不超過100的正整數(shù)，表示每個服務器的地址。第三行有一個正整數(shù)M，表示SERNET中傳輸線路的數(shù)目。接下來的M行每行用三個正整數(shù)表示一條傳輸線路連接的兩臺服務器的地址以及該傳輸線路的傳輸時間。線路傳輸時間為不超過100的正整數(shù)。接下來的一行為一個正整數(shù)K（K<10000），表示SERNET中數(shù)據包的數(shù)目。以下的K行每行表示一個數(shù)據包的信息，格式為：數(shù)據包編號 起始發(fā)送時間 源服務器地址 目的服務器地址其中數(shù)據包的編號為互不相同的小于100000的正

7、整數(shù)，輸入文件的最后一行為一個正整數(shù)T（T<10000），T為輸出時刻，輸入文件中同一行相鄰兩項之間用一個或多個空格隔開。輸出數(shù)據：輸出文件僅含義個整數(shù)P，表示T時刻后還在網絡中傳輸?shù)臄?shù)據包數(shù)目（編號相同的數(shù)據包為同一數(shù)據包）。約定： 本題中所有時間量的單位均相同； 每一條傳輸線路上在同一時刻能傳輸任意多個數(shù)據包。輸入輸出示例：SERNET.INSERNET.OUT457 42 10 93457 42 642 93 542 10 210 93 102433 10 57 105678 11 42 9323 1分析：很顯然，本題是對日常生活中的網絡文件傳輸進行模擬。對于模擬的事物，首先是將其

8、抽象成數(shù)學模型。于是我們將輸入文件給出的網絡信息轉換成一張帶權無向圖。網上的服務器作為頂點，服務器之間的傳輸線路作為無向邊，傳輸線路的傳輸時間作為邊上的權。這里要注意兩點： 試題中服務器數(shù)N的上限是給定的（N<100），可以按慣例采用二維數(shù)組存儲圖的信息。但問題是，服務器用服務器的地址予以標識，而這些地址是無序的。如果采用服務器地址作為數(shù)組下表，即會帶來計算的不便，造成內存的無端浪費。因此我們改變服務器的標識方式，用服務器地址的輸入順序標識服務器并將這些序號作為數(shù)組下標。例如：服務器地址57421093服務器標識（ID）1234 一條傳輸線路上的信息可能會因為有多種傳輸時間而重復輸入多次

9、。我們取其中最小傳輸時間和最大傳輸時間作為線路的傳輸時間范圍。若一條傳輸線路的信息僅輸入一次，則線路的最小傳輸時間的最大傳輸時間設為輸入的傳輸時間。設：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.Sh

10、ort = 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由于試題約定

11、“每一條傳輸線路上在同一時刻能傳輸任意多個數(shù)據包”，因此數(shù)據包的傳輸互不影響。我們可以一個一個的模擬數(shù)據包的傳輸過程，從中統(tǒng)計出T時刻后仍在網絡中傳輸?shù)臄?shù)據包數(shù)?，F(xiàn)在的問題是如何判別T時刻后當前一個數(shù)據包是否還在網絡中傳輸模擬一個數(shù)據包在網絡中的傳輸情況是算法的基礎。設：it當前數(shù)據包序號；acceptedI服務器I接受it數(shù)據包的標志（1IN）recevieI是服務器I向與它相連的所有服務器轉發(fā)數(shù)據包的開始時刻。由于服務器處理數(shù)據的時間忽略不計，因此收到數(shù)據包的時刻即為轉發(fā)時刻。RecevieI = $FFFF時說明當前未確定服務器I轉發(fā)數(shù)據包的時刻或者服務器I已接受了it。顯然，如果rec

12、eiveI <> $FFFF且acceptedI = false，則服務器I可能即將收到it。如果按照網絡的傳輸方案確定服務器I已接受了it，則acceptedI = true。開始時，it的源服務器首先將it復制若干份并同與之相連的所有服務器發(fā)送，即receiveit的源服務器=it的源服務器的起始發(fā)送時間，其余服務器的receive值為$FFFF。此時，除可確定it的目標服務器（但不能與it的服務器同址）為接受服務器外，其余服務器為收到it，即if it的源服務器<>it的目標服務器 then begin acceptedit的目標服務器:=true； 其余服務器的

13、accepted值設為false；end；然后重復如下過程：在可接受it的服務器集合中尋找一個最早收到數(shù)據包的滿足下屬條件的服務器I：minreceiveI |（receiveI <> $FFFF）and（acceptedI = false）服務器I試圖向與之相連的所有服務器J（LinksI, J.Short <> 0 | 1 J N）發(fā)送數(shù)據包。如果服務器J可收到it（receiveI + LinksI, J.Short < receiveJ），則將服務器J的receive值修正為receiveI + LinksI, J.Short，讓其在該時刻收到和轉發(fā)it；

14、如果其中一個服務器J在T時刻后才能接受來自服務器I的it（receiveI + LinksI,J.Long > T），則判定T時刻后仍有一個數(shù)據包在網絡中傳輸，算法結束；如果在T時刻前與服務器I相連的所有線路完成傳輸it的任務，則按照網絡的傳輸方案確定服務器I接受了it，acceptedIßTrue，receiveIß$FFFF。這一過程一直進行到所有服務器都不再轉發(fā)數(shù)據包為止，即所有服務器的receive值為$FFFF。上述算法由一個布爾函數(shù)Alive（it）描述。若數(shù)據包it在T時刻后還在網絡中傳播，則該函數(shù)返回True；否則返回False。算法描述如下：func

15、tion Alive(it): Boolean; Begin Alive := True; 初始化receive的值為$FFFF; Receiveit的源服務器 = it的開始發(fā)送時間 初始化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時刻后才能

16、接收it then exit; end; AcceptedI := True; ReceiveI := $FFFF; until False; Alive := False; end;對每一個數(shù)據包都求一次Alive，Alive函數(shù)值為True的次數(shù)P就是T時刻后仍在網絡中傳輸?shù)臄?shù)據包數(shù)。如下：P := 0;for I := 1 to 數(shù)據包數(shù)K do if Alive(I) then P := P + 1；Writeln(P)程序如下：$R-,S-,Q-program NOI98_5; const Inp = 'sernet.in'輸入文件名串 Outp = 'ser

17、net.out'輸出文件名串 MaxN = 99;服務器數(shù)的上限 MaxK = 9999;數(shù)據包數(shù)的上限 type TPackage = record數(shù)據包類型 Send: Word;發(fā)出時刻 Source: Byte;源服務器 Target: Byte;目的服務器 end; TLink = record傳輸線的時間類型 Short: Byte;最短傳輸時間 Long: Byte;最長傳輸時間 end; var N: Byte;服務器數(shù) K: Word;數(shù)據包數(shù) T: Word;輸出時刻 P: Word;輸出時刻后還在網絡中傳輸?shù)臄?shù)據包數(shù) Index: array 1 . MaxN o

18、f Byte; IndexI地址為I的服務器序號 Links: array 1 . MaxN, 1. MaxN of TLink; LinksI, J服務器I的服務器J的傳輸時間 Packages: array 1 . MaxPackage of TPackage; 數(shù)據包序列 procedure Init;輸入數(shù)據 var I, J: Word; M: Word;傳輸線路數(shù) S1, S2: Byte;當前傳輸線相連的兩個服務器序號 Time: Word; 當前傳輸線路的傳輸時間 PackageID: Longint;數(shù)據包編號 Begin Assign(Input, Inp); Reset(

19、Input); Readln(N);讀服務器數(shù) 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(Link

20、sS1,S2.Short>Time) then計算該線路的最短傳輸時間和最長傳輸時間 LinksS1, S2.Short := Time; if LinksS1, S2.Long < Time then LinksS1, S2.Long := Time; LinksS2, S1 := LinksS1, S2; end; Readln(K);讀數(shù)據包數(shù) for I := 1 to K do讀每一個數(shù)據包的信息 with PackagesI do Readln(PackageID, Send, Source, Target); 讀第I個數(shù)據包的編號，起始發(fā)送時間，源服務器地址，目的服務

21、器地址 Readln(T);讀入輸出時刻 Close(Input); end;function Alive(It: TPackage): Boolean;模擬數(shù)據包It在T時刻還在網絡中傳輸，則返回True；否則返回False var I, J: Byte; Time: Word; Receive: array 1 . MaxN of Word;ReceiveI：服務器I收到下一個數(shù)據的時刻 Accepted: array 1.MaxN of Boolean; AcceptedI：為服務器I接收It的標志 begin Alive := True; FillChar(Receive, Sizeo

22、f(Receive), $FF); 初始時，所有服務器未收到任何數(shù)據包 FillChar(Accepted, Sizeof(Accepted), False); ReceiveIndexIt.Source := It.Send; 源服務器在發(fā)送了It后開始接受下一個數(shù)據包 if It.Source <> It.Target then AcceptedIndexIt.Target := True; 若源服務器與目的服務器不同，則確定目的服務器收到數(shù)據包It repeat I := 1;計算最早收到下一個數(shù)據包的服務器I for J := 2 to N do if ReceiveJ &

23、lt; ReceiveI then I := J; if ReceiveI = $FFFF then Break;若所有服務器收到It，則返回false if not AcceptedI then begin 若服務器未接收數(shù)據包It，則搜索與服務器I相連的服務器 for J := 1 to N do if LinksI, J.Short <> 0 then begin Time := ReceiveI + LinksI, J.Short; if Time < ReceiveJ then ReceiveJ := Time; 若服務器J能在ReceiveJ前收到來自服務器I發(fā)來

24、的數(shù)據包if ReceiveI + LinksI, J.Long > T then Exit; 若在該線路上傳輸It將超是，則返回True end; AcceptedI := True;設定服務器I收到It標志 end; ReceiveI := $FFFF;設服務器I轉發(fā)過It標志 until False; Alive := False;It在TimeLine時刻前結束傳輸 end;procedure Main;統(tǒng)計T時刻后還在網絡中傳輸?shù)臄?shù)據包數(shù) var Y: Word; begin P := 0; for Y := 1 to K do if Alive(PackagesY) then

25、 Inc(P); end; procedure Out;輸出 begin Assign(Output, Outp); Rewrite(Output); Writeln(P); Close(Output); end; begin Init; Main; Out; end.習 題1多精度值處理古印度國王要褒獎他的聰明能干的宰相達依爾（國際象棋的發(fā)明者），問他要什么。達依爾回答：“殿下只要在棋盤上第一個格子放一粒麥粒，在第二個格子放兩粒，在第三個格子放四粒，以后的格子都是前一格的兩倍。如此放滿64格，我就心滿意足了?！眹跸?，這不難辦到。但一袋麥子很快就用完了，一倉庫也用完了，全印度的麥子也遠遠不夠。請編程計算所需的麥子總數(shù)。2邏輯判斷題來自不同國家的四位留學生A,B,C,D在一起交談,他們只會中、英、法、日四種語言中的2種,情況是, 沒有人既會日語又會法語;A會日語,但D不會,A和D能互相交談,B不會英語,但A和C交談時卻要B當翻譯,B,C,D三個想互相交談,但找不到共同的語言,只有一種語言3人都會,編程確定A,B,C,D四位留學生各會哪兩種語言。3枚舉排列數(shù)任意輸入由小寫字母組成的字符串（長度不超過15），求從中取出K個小寫字母的排