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

《2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 模擬法二.doc》由會員分享，可在線閱讀，更多相關(guān)《2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 模擬法二.doc（10頁珍藏版）》請在裝配圖網(wǎng)上搜索。

2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 模擬法二 課題：模擬法 目標： 知識目標：模擬的的實現(xiàn) 能力目標：模擬的實現(xiàn) 重點：模擬的實現(xiàn) 難點：模擬的實現(xiàn) 板書示意： 1） 模擬的引入（例31） 2） 模擬的應用（例32） 授課過程： 有些問題很難建立枚舉、遞歸等算法，甚至建立不了數(shù)學模型，但可以根據(jù)問題的描述，用程序模擬某種現(xiàn)象或規(guī)律，從而跟蹤出結(jié)果。 根據(jù)模擬對象的不同特點，可以把計算機模擬分為決定型模擬和隨機行模擬兩大類。 決定型模擬是對決定性現(xiàn)象進行的模擬，其所模擬的事件按照固有則規(guī)律發(fā)生發(fā)展，并且最終有明確的結(jié)果。在這種題目中，由于數(shù)學模型中各種參數(shù)的變化多半是有規(guī)律的，所以算法設(shè)計一般不是很困難。 隨機模擬是模擬隨機現(xiàn)象，由于隨機現(xiàn)象中至少有一個不確定的因素，因此在模擬中，必須建立一個用隨機值來模擬事件的進程，在隨機模擬過程中，通過修改變問題的各種參數(shù)，進而觀察變更這些參數(shù)所引起的狀態(tài)變化。一般情況是，題目給出某一概率，設(shè)計者利用隨機函數(shù)去設(shè)定在某一范圍的隨機值，將符合概率的隨機值作為參數(shù)。然后根據(jù)這一模擬模型展開算法設(shè)計。隨機模擬的關(guān)鍵是在概率已知的條件下，如何確定隨機值產(chǎn)生的范圍。這個隨機值設(shè)計得好，模擬效果就好。本節(jié)僅討論決定性模擬問題。有關(guān)隨機模擬的問題，大家可以參考一些相關(guān)書籍。 例31：約瑟夫問題 N個人排成一個圓圈，然后把這N個人按逆時針方向分別編號為1、2、……、N。從編號為1的人開始按逆時針計數(shù)，當某人計數(shù)為M的倍數(shù)是，該人出圈；如此循環(huán)下去，直到圈中只有一個人留下。 分析：這道題似乎用不上什么算法，只需建立一個循環(huán)鏈表，然后按照題目中要求的模擬即可。 算法描述如下： for I := 1 to N DO P[I] := I + 1; {建立循環(huán)鏈表} P[N] := 1; Now := N; repeat {模擬出圈過程} Now := N; for I := 1 to M - 1 do Now := P[Now]; {模擬報數(shù)} P[Now] := P[Now[Now]]; {編號為P[Now]的人出圈} until P[Now] = Now; {直到圈中只剩下一個人} Writeln(The last man is , Now); 例32：SERNET模擬（NOI98-5） 計算機網(wǎng)絡(luò)是現(xiàn)代科技發(fā)展的熱點，傳播性能是計算機網(wǎng)絡(luò)的主要性能指標。SERNET網(wǎng)絡(luò)開發(fā)小組設(shè)計了一種稱為SERNET的網(wǎng)絡(luò)，并希望開發(fā)一個模擬軟件來模擬該網(wǎng)絡(luò)的數(shù)據(jù)傳輸情況，進而計算出網(wǎng)絡(luò)的傳輸性能。 SERNET網(wǎng)絡(luò)由服務(wù)器及連接它們的網(wǎng)絡(luò)傳輸線路組成，服務(wù)器用服務(wù)器地址予以標識，網(wǎng)絡(luò)傳輸線路為雙向傳輸線路。網(wǎng)絡(luò)傳輸過程中將各種傳輸數(shù)據(jù)分隔為若干個大小相同的數(shù)據(jù)包，以數(shù)據(jù)包為單位進行傳輸。數(shù)據(jù)包在傳輸線路上傳輸時需要一定的傳輸時間，不同的傳輸線路的傳輸時間不同。服務(wù)器處理數(shù)據(jù)的時間較之于傳輸時間很小，可忽略不計。每一個數(shù)據(jù)包中除了包括具體的數(shù)據(jù)信息外，還含有如下標識信息： ① 數(shù)舉包編號； ② 數(shù)據(jù)包源服務(wù)器地址； ③ 數(shù)據(jù)包目的服務(wù)器地址。 網(wǎng)絡(luò)傳輸?shù)墓δ芫褪菍⒁粋€個數(shù)據(jù)包從源服務(wù)器傳輸?shù)侥康姆?wù)器。對于每一個數(shù)據(jù)包，具體的網(wǎng)絡(luò)傳輸方案為： ① 源服務(wù)器將待發(fā)送的數(shù)據(jù)包一律復制若干份并向與之相連的所有賦予其發(fā)送該數(shù)據(jù)包。 ② 服務(wù)器接收到一個數(shù)據(jù)包后，如果該數(shù)據(jù)包符合下面任何一個條件： l 數(shù)據(jù)包的源服務(wù)器地址與本服務(wù)器地址相同 l 數(shù)據(jù)包的目的服務(wù)器地址與本服務(wù)器地址相同 l 本服務(wù)器已轉(zhuǎn)發(fā)過與該數(shù)據(jù)包編號相同的數(shù)據(jù)包 則接收該數(shù)據(jù)包；否則，服務(wù)器將其復制若干份并向它相連的所有服務(wù)器轉(zhuǎn)發(fā)該數(shù)據(jù)包。 這里，兩臺服務(wù)器“相連”的含義是它們之間有網(wǎng)絡(luò)傳輸線路直接相連。 現(xiàn)在需要你編一個程序來模擬SERNET網(wǎng)絡(luò)中的數(shù)據(jù)包傳輸情況。 輸入數(shù)據(jù)： 輸入文件的第一行為一個正整數(shù)N（N<100），表示SERNET中服務(wù)器的數(shù)目。第二行有N個互不相等的不超過100的正整數(shù)，表示每個服務(wù)器的地址。 第三行有一個正整數(shù)M，表示SERNET中傳輸線路的數(shù)目。接下來的M行每行用三個正整數(shù)表示一條傳輸線路連接的兩臺服務(wù)器的地址以及該傳輸線路的傳輸時間。線路傳輸時間為不超過100的正整數(shù)。 接下來的一行為一個正整數(shù)K（K<10000），表示SERNET中數(shù)據(jù)包的數(shù)目。以下的K行每行表示一個數(shù)據(jù)包的信息，格式為： 數(shù)據(jù)包編號 起始發(fā)送時間 源服務(wù)器地址 目的服務(wù)器地址 其中數(shù)據(jù)包的編號為互不相同的小于100000的正整數(shù)，輸入文件的最后一行為一個正整數(shù)T（T<10000），T為輸出時刻，輸入文件中同一行相鄰兩項之間用一個或多個空格隔開。 輸出數(shù)據(jù)： 輸出文件僅含義個整數(shù)P，表示T時刻后還在網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)包數(shù)目（編號相同的數(shù)據(jù)包為同一數(shù)據(jù)包）。 約定： ① 本題中所有時間量的單位均相同； ② 每一條傳輸線路上在同一時刻能傳輸任意多個數(shù)據(jù)包。 輸入輸出示例： SERNET.IN SERNET.OUT 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 1 分析： 很顯然，本題是對日常生活中的網(wǎng)絡(luò)文件傳輸進行模擬。對于模擬的事物，首先是將其抽象成數(shù)學模型。于是我們將輸入文件給出的網(wǎng)絡(luò)信息轉(zhuǎn)換成一張帶權(quán)無向圖。網(wǎng)上的服務(wù)器作為頂點，服務(wù)器之間的傳輸線路作為無向邊，傳輸線路的傳輸時間作為邊上的權(quán)。這里要注意兩點： ① 試題中服務(wù)器數(shù)N的上限是給定的（N<100），可以按慣例采用二維數(shù)組存儲圖的信息。但問題是，服務(wù)器用服務(wù)器的地址予以標識，而這些地址是無序的。如果采用服務(wù)器地址作為數(shù)組下表，即會帶來計算的不便，造成內(nèi)存的無端浪費。因此我們改變服務(wù)器的標識方式，用服務(wù)器地址的輸入順序標識服務(wù)器并將這些序號作為數(shù)組下標。例如： 服務(wù)器地址 57 42 10 93 服務(wù)器標識（ID） 1 2 3 4 ② 一條傳輸線路上的信息可能會因為有多種傳輸時間而重復輸入多次。我們?nèi)∑渲凶钚鬏敃r間和最大傳輸時間作為線路的傳輸時間范圍。若一條傳輸線路的信息僅輸入一次，則線路的最小傳輸時間的最大傳輸時間設(shè)為輸入的傳輸時間。設(shè)： type Tlink = record {傳輸線路的時間類型} Short， {最短傳輸時間} Long: Byte; {最長傳輸時間} End; var Links: array [1 .. N, 1 .. N] of Tlink; {網(wǎng)絡(luò)} 下表列出了樣例中的網(wǎng)絡(luò)信息： 服務(wù)器I地址（ID） 服務(wù)器J地址（ID） 傳輸時間 57（1） 42（2） 1 57（1） 42（2） 3 57（1） 42（2） 6 42（2） 93（4） 5 42（2） 10（3） 2 10（3） 93（4） 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 圖27 網(wǎng)絡(luò)傳輸示例圖 Links[3,4].Long = Links[4, 3].Long = 10 見圖2-17 由于試題約定“每一條傳輸線路上在同一時刻能傳輸任意多個數(shù)據(jù)包”，因此數(shù)據(jù)包的傳輸互不影響。我們可以一個一個的模擬數(shù)據(jù)包的傳輸過程，從中統(tǒng)計出T時刻后仍在網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)包數(shù)。 現(xiàn)在的問題是如何判別T時刻后當前一個數(shù)據(jù)包是否還在網(wǎng)絡(luò)中傳輸 模擬一個數(shù)據(jù)包在網(wǎng)絡(luò)中的傳輸情況是算法的基礎(chǔ)。 設(shè)： it——當前數(shù)據(jù)包序號； accepted[I]——服務(wù)器I接受it數(shù)據(jù)包的標志（1≦I≦N） recevie[I]是服務(wù)器I向與它相連的所有服務(wù)器轉(zhuǎn)發(fā)數(shù)據(jù)包的開始時刻。由于服務(wù)器處理數(shù)據(jù)的時間忽略不計，因此收到數(shù)據(jù)包的時刻即為轉(zhuǎn)發(fā)時刻。Recevie[I] = $FFFF時說明當前未確定服務(wù)器I轉(zhuǎn)發(fā)數(shù)據(jù)包的時刻或者服務(wù)器I已接受了it。顯然，如果receive[I] <> $FFFF且accepted[I] = false，則服務(wù)器I可能即將收到it。如果按照網(wǎng)絡(luò)的傳輸方案確定服務(wù)器I已接受了it，則accepted[I] = true。 開始時，it的源服務(wù)器首先將it復制若干份并同與之相連的所有服務(wù)器發(fā)送，即receive[it的源服務(wù)器]=it的源服務(wù)器的起始發(fā)送時間，其余服務(wù)器的receive值為$FFFF。此時，除可確定it的目標服務(wù)器（但不能與it的服務(wù)器同址）為接受服務(wù)器外，其余服務(wù)器為收到it，即 if it的源服務(wù)器<>it的目標服務(wù)器 then begin accepted[it的目標服務(wù)器]:=true； 其余服務(wù)器的accepted值設(shè)為false； end； 然后重復如下過程： 在可接受it的服務(wù)器集合中尋找一個最早收到數(shù)據(jù)包的滿足下屬條件的服務(wù)器I： min{receive[I] |（receive[I] <> $FFFF）and（accepted[I] = false）} 服務(wù)器I試圖向與之相連的所有服務(wù)器J（Links[I, J].Short <> 0 | 1 ≦ J ≦ N）發(fā)送數(shù)據(jù)包。 如果服務(wù)器J可收到it（receive[I] + Links[I, J].Short < receive[J]），則將服務(wù)器J的receive值修正為receive[I] + Links[I, J].Short，讓其在該時刻收到和轉(zhuǎn)發(fā)it； 如果其中一個服務(wù)器J在T時刻后才能接受來自服務(wù)器I的it（receive[I] + Links[I,J].Long > T），則判定T時刻后仍有一個數(shù)據(jù)包在網(wǎng)絡(luò)中傳輸，算法結(jié)束； 如果在T時刻前與服務(wù)器I相連的所有線路完成傳輸it的任務(wù)，則按照網(wǎng)絡(luò)的傳輸方案確定服務(wù)器I接受了it，accepted[I]True，receive[I]$FFFF。 這一過程一直進行到所有服務(wù)器都不再轉(zhuǎn)發(fā)數(shù)據(jù)包為止，即所有服務(wù)器的receive值為$FFFF。 上述算法由一個布爾函數(shù)Alive（it）描述。若數(shù)據(jù)包it在T時刻后還在網(wǎng)絡(luò)中傳播，則該函數(shù)返回True；否則返回False。 算法描述如下： function Alive(it): Boolean; Begin Alive := True; 初始化receive的值為$FFFF; Receive[it的源服務(wù)器] = it的開始發(fā)送時間 初始化Accepted的值為False; Accepted[it的目標服務(wù)器] = true repeat 尋找一個receive值最小的服務(wù)器I; if Receive[I] = $FFFF then Break ; if Accepted[I] = False then for J := 1 to N do begin if 服務(wù)器I與服務(wù)器J有傳輸線路 then 修正receive[J]值; if 服務(wù)器J在T時刻后才能接收it then exit; end; Accepted[I] := True; Receive[I] := $FFFF; until False; Alive := False; end; 對每一個數(shù)據(jù)包都求一次Alive，Alive函數(shù)值為True的次數(shù)P就是T時刻后仍在網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)包數(shù)。如下： P := 0; for I := 1 to 數(shù)據(jù)包數(shù)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; {服務(wù)器數(shù)的上限} MaxK = 9999; {數(shù)據(jù)包數(shù)的上限} type TPackage = record {數(shù)據(jù)包類型} Send: Word; {發(fā)出時刻} Source: Byte; {源服務(wù)器} Target: Byte; {目的服務(wù)器} end; TLink = record {傳輸線的時間類型} Short: Byte; {最短傳輸時間} Long: Byte; {最長傳輸時間} end; var N: Byte; {服務(wù)器數(shù)} K: Word; {數(shù)據(jù)包數(shù)} T: Word; {輸出時刻} P: Word; {輸出時刻后還在網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)包數(shù)} Index: array [1 .. MaxN] of Byte; {Index[I]——地址為I的服務(wù)器序號} Links: array [1 .. MaxN, 1.. MaxN] of TLink; {Links[I, J]——服務(wù)器I的服務(wù)器J的傳輸時間} Packages: array [1 .. MaxPackage] of TPackage; {數(shù)據(jù)包序列} procedure Init; {輸入數(shù)據(jù)} var I, J: Word; M: Word; {傳輸線路數(shù)} S1, S2: Byte; {當前傳輸線相連的兩個服務(wù)器序號} Time: Word; {當前傳輸線路的傳輸時間} PackageID: Longint; {數(shù)據(jù)包編號} Begin Assign(Input, Inp); Reset(Input); Readln(N); {讀服務(wù)器數(shù)} for I := 1 to N do begin {度入每個服務(wù)器地址，計算Index表} Read(J); Index[J] := I; end; Readln(M); {讀傳輸線路輸} FillChar(Links, Sizeof(Links), 0); {Links表初始化} for I := 1 to M do begin {輸入每條線路的信息} Readln(S1, S2, Time); {讀相連的兩臺服務(wù)器地址和傳輸時間} S1 := Index[S1]; {計算這兩臺服務(wù)器的序號} S2 := Index[S2]; if (Links[S1,S2].Short=0)or(Links[S1,S2].Short>Time) then {計算該線路的最短傳輸時間和最長傳輸時間} Links[S1, S2].Short := Time; if Links[S1, S2].Long < Time then Links[S1, S2].Long := Time; Links[S2, S1] := Links[S1, S2]; end; Readln(K); {讀數(shù)據(jù)包數(shù)} for I := 1 to K do {讀每一個數(shù)據(jù)包的信息} with Packages[I] do Readln(PackageID, Send, Source, Target); {讀第I個數(shù)據(jù)包的編號，起始發(fā)送時間，源服務(wù)器地址，目的服務(wù)器地址} Readln(T); {讀入輸出時刻} Close(Input); end; function Alive(It: TPackage): Boolean; {模擬數(shù)據(jù)包It在T時刻還在網(wǎng)絡(luò)中傳輸，則返回True；否則返回False} var I, J: Byte; Time: Word; Receive: array [1 .. MaxN] of Word; {Receive[I]：服務(wù)器I收到下一個數(shù)據(jù)的時刻} Accepted: array [1..MaxN] of Boolean; {Accepted[I]：為服務(wù)器I接收It的標志} begin Alive := True; FillChar(Receive, Sizeof(Receive), $FF); {初始時，所有服務(wù)器未收到任何數(shù)據(jù)包} FillChar(Accepted, Sizeof(Accepted), False); Receive[Index[It.Source]] := It.Send; {源服務(wù)器在發(fā)送了It后開始接受下一個數(shù)據(jù)包} if It.Source <> It.Target then Accepted[Index[It.Target]] := True; {若源服務(wù)器與目的服務(wù)器不同，則確定目的服務(wù)器收到數(shù)據(jù)包It} repeat I := 1; {計算最早收到下一個數(shù)據(jù)包的服務(wù)器I} for J := 2 to N do if Receive[J] < Receive[I] then I := J; if Receive[I] = $FFFF then Break; {若所有服務(wù)器收到It，則返回false} if not Accepted[I] then begin {若服務(wù)器未接收數(shù)據(jù)包It，則搜索與服務(wù)器I相連的服務(wù)器} for J := 1 to N do if Links[I, J].Short <> 0 then begin Time := Receive[I] + Links[I, J].Short; if Time < Receive[J] then Receive[J] := Time; {若服務(wù)器J能在Receive[J]前收到來自服務(wù)器I發(fā)來的數(shù)據(jù)包} if Receive[I] + Links[I, J].Long > T then Exit; {若在該線路上傳輸It將超是，則返回True} end; Accepted[I] := True; {設(shè)定服務(wù)器I收到It標志} end; Receive[I] := $FFFF; {設(shè)服務(wù)器I轉(zhuǎn)發(fā)過It標志} until False; Alive := False; {It在TimeLine時刻前結(jié)束傳輸} end; procedure Main; {統(tǒng)計T時刻后還在網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)包數(shù)} var Y: Word; begin P := 0; for Y := 1 to K do if Alive(Packages[Y]) then 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個小寫字母的排列和排列總數(shù)。 4．貨郎擔問題。 某售貨員要到若干個村莊售貨，各個村莊的路程是已知的，為了提高效率，售貨員決定從商店出發(fā)到每個村莊售一次貨然后返回商店，問他應選擇一條什么樣的路徑，才能使走的總路程最短。 輸入:從文本文件讀入N(第一行)，表示一個商店和N-1個村莊。 其下N行為一個N*N的矩陣，每個矩陣元素(i，j)的值表示從i村莊(或商店)到j(luò)村莊(或商店)的距離。i=1或j=1表示商店。數(shù)值均為整數(shù)，數(shù)值之間用空格隔開。 輸出:在屏幕上輸出從商店出發(fā)經(jīng)過每一個村莊一次，最后返回商店的路線(第一行)輸出最短路線長度(第二行)。 5．汽油花費 一些旅行車從城市A到城市B運送包裹。在沿途由很多價格不同的加油站。第一個加油站的位置在路程的開始。旅行車的油箱容積可能不同，車在沿途需要及時給油箱加油，我們假設(shè)，每個油站有足夠的油。 輸入：在文本文件中的第一行為一個整數(shù)p表示油箱的容量, 1 < p <= 1000000. 在第二行有一個整數(shù)n表是沿途加油站的數(shù)目。1 < n <= 1000000。接下來的n行每行有兩個用單個正整數(shù)分隔的整數(shù)ci, di, 其中ci表示第I油站的價格。di 表示I和第(i+1)個油站的距離- (dn 就是最后一個油站到結(jié)束點的距離)。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。輸入不要判錯。 所有變量為單個小寫字母。只是要求去掉所有多余括號，不要求對表達式化簡