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

2019-2020年高中信息技術(shù)全國青少年奧林匹克聯(lián)賽教課方案列舉法二課題：列舉法目標(biāo)：知識(shí)目標(biāo)：列舉算法的實(shí)質(zhì)和應(yīng)用

能力目標(biāo)：列舉算法的應(yīng)用！重點(diǎn)：利用列舉算法解決實(shí)責(zé)問題難點(diǎn)：列舉算法的次數(shù)確定板書表示：1）簡單列舉（例

7、例

8、例

9）2）利用列舉解決邏輯判斷問題（例3）列舉解決競(jìng)賽問題（例12、例

10、例11）13、例14）授課過程:所謂列舉法，指的是從可能的解會(huì)集中一一列舉各元素些是無用的，哪些是適用的?能使命題建立，即為其解。一般思路

:

，用題目給定的檢驗(yàn)條件判斷哪對(duì)命題建立正確的數(shù)學(xué)模型；依照命題確定的數(shù)學(xué)模型中各變量的變化范圍（即可能解的范圍）

；利用循環(huán)語句、條件判斷語句漸漸求解或證明；列舉法的特點(diǎn)是算法簡單，但有時(shí)運(yùn)算量大。對(duì)于可能確定解的值域又一時(shí)找不到其他更好的算法時(shí)能夠采用列舉法。例7:求滿足表達(dá)式A+B=C的全部整數(shù)解，其中A,B,C為1~3之間的整數(shù)。解析：本題特別簡單，即列舉全部情況，吻合表達(dá)式即可。算法以下：forA:=1to3doforB:=1to3doforC:=1to3doifA+B=CthenWriteln（A,

‘+'

,B,

‘='

,C）;上例采用的就是列舉法。所謂列舉法，指的是從可能的解的會(huì)集中一一列舉各元素，用題目給定的檢驗(yàn)條件判斷哪些是無用的，哪些是適用的。能使命題建立的，即為解。從列舉法的定義能夠看出，列舉法實(shí)質(zhì)上屬于搜尋。但與隱式圖的搜尋有所差異，在采用列舉法求解的問題時(shí)，必定滿足兩個(gè)條件:①起初確定解的個(gè)數(shù)n；②對(duì)每個(gè)解變量A1，A2,An的取值，其變化范圍需起初確定A?{Xi1,Xq}A?{X11,,XP}{Xnl,,%k}例7中的解變量有3個(gè)：AB,C。其中AB

解變量值的可能取值范圍A?{1解變量值的可能取值范圍B?{1

,2,3},2,3}C解變量值的可能取值范圍C?{1,2,3}(A,B,C)?{(1，1，則問題的可能解有27個(gè)1),(1,1,2),(1,1,3),(1,2,1),(1,2,2),(1,2,3),(3,3,1),(3,3,2),(3,3,3)}在上述可能解會(huì)集中，滿足題目給定的檢驗(yàn)條件的解元素，即為問題的解。若是我們無法起初確定解的個(gè)數(shù)或各解的值域，則不能夠用列舉，只能采用搜尋等算法求解。由于回溯法在搜尋每個(gè)可能解的列舉次數(shù)一般不僅一次，因此，對(duì)于同樣規(guī)模的問題，回溯算法要比列舉法時(shí)間復(fù)雜度稍高。例8給定一個(gè)二元一次方程aX+bY=c。從鍵盤輸入a,b,c的數(shù)值，求X在［0,100］,Y在［0,100］范圍內(nèi)的全部整數(shù)解。解析：要求方程的在一個(gè)范圍內(nèi)的解，只要對(duì)這個(gè)范圍內(nèi)的全部整數(shù)點(diǎn)進(jìn)隊(duì)列舉，看這些點(diǎn)可否滿足方程即可。參照程序：programexam8;vara,b,c:integer;x,y:integer;beginwrite('Inputa,b,c:');readln(a,b,c);forx:=0to100dofory:=0to100doifa*x+b*y=cthenwriteln(x,'',y);end.從上例能夠看出，所謂列舉法，指的是從可能的解會(huì)集中一一列舉各元素，用題目給定的檢驗(yàn)條件判斷哪些是無用的，哪些是適用的?能使命題建立，即為其解。例9巧妙填數(shù)將1?9這九個(gè)數(shù)字填入九個(gè)空格中。每一橫行的三個(gè)數(shù)字組成一個(gè)三位數(shù)。若是要使第二行的三位數(shù)是第一行的兩倍，第三行的三位數(shù)是第一行的三倍，應(yīng)怎樣填數(shù)。如圖6:192384576圖6解析：本題目有9個(gè)格子，要求填數(shù)，若是不考慮問題給出的條件，共有9!=362880種方案，在這些方案中吻合問題條件的即為解。因此能夠采用列舉法。但仔細(xì)解析問題，顯然第一行的數(shù)不會(huì)高出400，實(shí)質(zhì)上只要確定第一行的數(shù)就可以依照條件算出其他兩行的數(shù)了。這樣僅需列舉400次。因此設(shè)計(jì)參照程序：programexam9;vari,j,k,s:integer;functionsum(s:integer):integer;beginsum:=sdiv100+sdiv10mod10+smod10end;functionmul(s:integer):longint;beginmul:=(sdiv100)*(sdiv10mod10)*(smod10)end;beginfori:=1to3doforj:=1to9doifj<>ithenfork:=1to9doif(k<>j)and(k<>i)thenbegins:=i*100+j*10+k;{求第一行數(shù)}if3*s<1000thenif(sum(s)+sum(2*s)+sum(3*s)=45)and(mul(s)*mul(2*s)*mul(3*s)=362880)then{滿足條件，并數(shù)字都由1~9組成}beginwriteln(s);writeln(2*s);writeln(3*s);writeln;end;end;end.例10

在某次數(shù)學(xué)競(jìng)賽中

,A

、B、C、D、E

五名學(xué)生被取為前五名。請(qǐng)據(jù)以下說法判斷

出他們的詳盡名次

,

即誰是第幾名？

條件

1:

你若是認(rèn)為

A,B,C,D,E

就是這些人的第一至第五名的名次排列

,

便大錯(cuò)。由于

沒猜對(duì)任何一個(gè)優(yōu)勝者的名次。也沒猜對(duì)任何一對(duì)名次相鄰的學(xué)生。條件2:你若是按D,A,E,C,B來排列五人名次的話,其結(jié)果是:說對(duì)了其中兩個(gè)人的名次。還猜中了兩對(duì)名次相鄰的學(xué)生的名次序次。解析：本題是一個(gè)邏輯判斷題，一般的邏輯判斷題都采用列舉法進(jìn)行解決。5個(gè)人的名次分別能夠有5!=120種排列可能，由于120比較小，因此我們對(duì)每種情況進(jìn)隊(duì)列舉,然后依照條件判斷哪些吻合問題的要求。依照已知條件，A<>1,B<>2,C<>3,D<>4,E<>5,因此消除了一種可能性，只有4！=24種情況了。參照程序：ProgramExamIO;VarA,B,C,D,E

:lnteger;Cr

:Array[1..5]OfChar;BeginForA:=1To5DoForB:=1To5DoForC:=1To5DoForD:=1To5DoForE:=1To5DoBegin{ABCDE沒猜對(duì)一個(gè)人的名次}If(A=1)Or(B=2)Or(C=3)Or(D=4)Or(E=5)ThenContinue;If[A,B,C,D,E]<>[1,2,3,4,5]ThenContinue;{他們名次互不重復(fù)}{DAECB猜對(duì)了兩個(gè)人的名次}IfOrd(A=2)+Ord(B=5)+Ord(C=4)+Ord(D=1)+Ord(E=3)<>2ThenContinue;{ABCDE沒猜對(duì)一對(duì)相鄰名次}If(B=A+1)Or(C=B+1)Or(D=C+1)Or(E=D+1)ThenContinue;{DAECB猜對(duì)了兩對(duì)相街坊名次}IfOrd(A=D+1)+Ord(E=A+1)+Ord(C=E+1)+Ord(B=C+1)<>2ThenContinue;Cr[A]:='A';Cr[B]:='B';Cr[C]:=C;Cr[D]:='D';Cr[E]:='E：WRITELN(CR[1],'',CR[2],'',CR[3],'',CR[4],'',CR[5]);End;End.例11:來自不同樣國家的四位留學(xué)生A,B,C,D在一起講話，他們只會(huì)中、英、法、日四種語言中的2種，情況是，沒有人既會(huì)日語又會(huì)法語;A會(huì)日語，但D不會(huì),A和D能互相講話,B不會(huì)英語，但A和C講話時(shí)卻要B當(dāng)翻譯,B,C,D三個(gè)想互相講話，但找不到共同的語言,只有一種語言3人都會(huì)，編程確定A,B,C,D四位留學(xué)生各會(huì)哪兩種語言。解析：將中、法、日、英四種語言分別定義為CHNFRHJPNENG則四種語言中取兩種共有(CHN,ENG),(CHN,FRH,(CHN,JPN),(ENG,FRH),(ENG,JPN),(FRH,JPN)六種組合，分別定義為1、2、3、4、5、6。據(jù)已知，沒有人既會(huì)日語又會(huì)法語；因此，組合6不會(huì)出現(xiàn)；A會(huì)日語，因此A只可能等于3、5；D不會(huì)日語，因此D只可能等于1、2、4；B不會(huì)英語，因此B只可能等于2、3;見下表。若是我們對(duì)ABC、D分別進(jìn)隊(duì)列舉，依照判斷條件，即可找到答案。(CHN,ENG)(CHN,FRH)(CHN,JPN)(ENG,FRH)(ENG,JPN)AXXXBXXXCD程序以下：

XXprogramEXAM11;typeLanguage=(CHN,ENG,FRH,JPN);TNoSet=setofLanguage;constNo:array[1..5]ofTNoSet=([CHN,ENG],[CHN,FRH],[CHN,JPN],[ENG,FRH],[ENG,JPN]);varA,B,C,D:1..5;Can1,Can2,Can3,Can4:Boolean;functionMight(Lang:Language):Boolean;varBool:Boolean;beginBool:=false;ifNo[A]*No[A]*No[C]=[Lang]thenBool:=True;ifNo[A]*No[B]*No[D]=[Lang]thenBool:=True;ifNo[A]*No[C]*No[D]=[Lang]thenBool:=True;ifNo[B]*No[C]*No[D]=[Lang]thenBool:=True;Might:=Boolend;procedurePrint(A,B,C,D:Integer);procedureShow(P:Integer;Ch:Char);varInteger;Lang:Language;beginWrite(ch,':');forLang:=CHNtoJPNdoifLanginNo[P]thencaseLangofCHN:Write('CHN':5);FRH:Write('FRH':5);JPN:Write('JPN':5);ENG:Write('ENG':5);end;WriteIn;end;beginShow(A,'A');Show(B,'B');三個(gè)想互相講話，但找不到共同的語言Show(C,C);Show(D,'D');end;beginforA:=3to5doifA<>4thenforB:=2to3doforC:=1to5doforD:=1to4doifD<>3thenbegin{A和D能互相講話}Can1:=No[A]*No[D]<>[];{A和C講話時(shí)卻要B當(dāng)翻譯

}Can2:=(No[A]*No[C]=[])and(No[A]*No[B]<>[])and(No[B]*No[C]<>[]);{B,C,D}Can3:=No[B]*No[C]*No[D]=[];{只有一種語言3人都會(huì)}Can4:=Ord(Might(CHN))+Ord(Might(ENG))+Ord(Might(FRH))+Ord(Might(JPN))=1;ifCan1andCan2andCan3andCan4thenPrint(A,B,C,D);end;end.例12

古紙殘篇在一位數(shù)學(xué)家的藏書中夾有一張古舊的紙片。

紙片上的字早已模糊不清了

，只留下以前寫過字的印跡，隱約還可以夠看出它是一個(gè)乘法算式

，如圖

7

所示。這個(gè)算式上原來的數(shù)字是什么呢？夾著這張紙片的冊(cè)頁上，“素?cái)?shù)”兩個(gè)字被醒目的劃了出來。難道說,這個(gè)算式與素?cái)?shù)有什么關(guān)系嗎？有人對(duì)此作了深入的研究

，果然發(fā)現(xiàn)這個(gè)算式中

***的每一個(gè)數(shù)字都是素?cái)?shù)

，而且這樣的算式是唯一的。請(qǐng)你也研究

x**一番，并把這個(gè)算式寫出來。解析：實(shí)質(zhì)上，

只要知道乘數(shù)和被乘數(shù)就可以寫出乘法算式，

因此我們能夠列舉乘數(shù)與被乘數(shù)的每一位。爾后再判斷可否是滿足條件即可。計(jì)算量是

45=1024

，對(duì)于計(jì)算機(jī)來說，計(jì)算量特別小。參照程序：ProgramExam12;ConstSu:Array[1..4]OfLongint=(2,3,5,7);VarA1,A2,A3,B1,B2,X,Y,S:Longint;FunctionKx(S:Longint):Boolean;{判斷一個(gè)數(shù)BeginKx:=True;WhileS<>0DoBeginIfNot((SMod10)In[2,3,5,7])ThenBeginKx:=False;Exit;End;

可否是都是由素?cái)?shù)組成

}S:=SDiv10;End;End;BeginForA1:=1To4DoForA2:=1To4DoForA3:=1To4DoForB1:=1To4DoForB2:=1To4DoBeginX:=Su[A1]*100+Su[A2]*10+Su[A3];{X為被乘數(shù)}IfX*Su[B1]<1000ThenContinue;IfX*Su[B2]<1000ThenContinue;IfX*(Su[B1]*10+Su[B2])<10000ThenContinue;{它們分別是兩個(gè)四位數(shù)，一個(gè)五位數(shù)}If(Kx(X*Su[B1])=False)Or(Kx(X*Su[B2])=False)Or(Kx(X*(Su[B1]*10+Su[B2]))=False)ThenContinue;{滿足其他數(shù)都是由質(zhì)數(shù)組成}Writeln('',Su[A1],Su[A2],Su[A3]);Writeln('*',Su[B1],Su[B2]);Writeln('----------');Writeln('',X*Su[B2]);Writeln('',X*Su[B1]);Writeln('----------');Writeln('',X*(Su[B1]*10+Su[B2]));End;End.例13:時(shí)鐘問題（10194-4）在圖8所示的3*3矩陣中有9個(gè)時(shí)鐘，我們的目標(biāo)是旋轉(zhuǎn)時(shí)鐘指針，使全部時(shí)鐘的指針都指向12點(diǎn)。贊同旋轉(zhuǎn)時(shí)鐘指針的方法有9種，每一種搬動(dòng)用一個(gè)數(shù)字號(hào)（1，2，，9）??O?????OOOOOOOOOOOO123?OOoeoooe?OO???ooe?OOoeoooe456OOOOOOOO??OOOOOo????O???o??7呂5圖8九種時(shí)鐘狀態(tài)表示。圖2-11示出9個(gè)數(shù)字號(hào)與相應(yīng)的受控制的時(shí)鐘，這些時(shí)鐘在圖中以灰色標(biāo)出，其指——受控制的時(shí)鐘圖9九種被控制方式針將順時(shí)針旋轉(zhuǎn)90度。輸入數(shù)據(jù)：由輸入文件INPUT.TXT讀9個(gè)數(shù)碼，這些數(shù)碼給出了9個(gè)時(shí)鐘時(shí)針的初始地址。數(shù)碼與時(shí)刻的對(duì)應(yīng)關(guān)系為：0――12點(diǎn)1――3點(diǎn)2――63――9

點(diǎn)點(diǎn)圖2-11中的例子對(duì)應(yīng)以下輸入數(shù)據(jù)：330222212輸出數(shù)據(jù)：將一個(gè)最短的搬動(dòng)序列（數(shù)字序列）寫入輸出文件0UTPUT.TXT中，該序列要使全部的時(shí)鐘指針指向12點(diǎn)，若有等價(jià)的多個(gè)解，僅需給出其中一個(gè)。在我們的例子中，相應(yīng)的0UTPUT.TXT勺內(nèi)容為：5849輸入輸出示例:INPUT.TXTOUTPUT.TXT3305489222212詳盡的搬動(dòng)方案如圖10所示。5pool8[OOOlIr■—1J■kjTW^.1OQJ=>O0OOOQt==>ooo==>?oIIQQQJIpooJIQOQJtpoojQOQ圖10示例搬動(dòng)方案解析：第一，我們解析一下表示時(shí)鐘時(shí)針初始地址的數(shù)碼j(0WjW3)與時(shí)刻的對(duì)應(yīng)關(guān)系：0――12點(diǎn)1――3點(diǎn)2――63――9

點(diǎn)點(diǎn)每搬動(dòng)一次，時(shí)針將順時(shí)針旋轉(zhuǎn)90度。由此我們能夠得出：對(duì)于任意一個(gè)時(shí)鐘i(1WiW9)來說，從初始地址j出倡始碼需要C=(4-j)mod4次操作，才能使得時(shí)針指向12點(diǎn)。而對(duì)每種搬動(dòng)方法要么不采用，要么采用1次、2次或3次，由于操作四次今后，時(shí)鐘將重復(fù)以前狀態(tài)。因此，9種旋轉(zhuǎn)方案最多產(chǎn)生49個(gè)狀態(tài)。搬動(dòng)方案采用與序次沒關(guān)。樣例中，最正確搬動(dòng)序列為5849，同樣4589序列也可達(dá)到目標(biāo)。因此，求解過程中能夠直接采用序列中從小至大排列的搬動(dòng)序列即可。設(shè)pi表示第i種旋轉(zhuǎn)方法的使用次數(shù)(0WpiW3,1WiW9)。則可能的解的會(huì)集為｛P,PP｝，該會(huì)集共含49個(gè)狀態(tài)。從圖2.11中，我們能夠解析出9個(gè)時(shí)鐘分129別被哪些方法所控制，見下表：時(shí)鐘號(hào)控制時(shí)鐘方案檢驗(yàn)條件11、2、4C1=(P1+P2+P4)mod421、2、3、5C2=(P1+P2+P3+R)mod432、3、6C3=(P2+P3+P6)mod441、4、5、7G=(P計(jì)P4+P5+H)mod451、3、5、7、9G=(P計(jì)Ps+R+FV+B)mod463、5、6、9C6=(Ps+P5+P6+Pg)mod474、7、8Cz=(P4+P7+P8)mod485、7、8、9C8=(P5+PZ+P3+P9)mod496、&9Co=(P6+P3+P9)mod4因此我們能夠設(shè)計(jì)以以下舉算法:forp1:=0to3doforp2:=0to3doforp9:=0to3doifcl滿足時(shí)鐘1andc2滿足時(shí)鐘2and...andc9滿足時(shí)鐘9then打印解路徑；顯然，上述列舉算法列舉了全部49=262144個(gè)狀態(tài)，運(yùn)算量和運(yùn)行時(shí)間頗大。我們能夠采用減小可能解范圍的局部列舉法，僅列舉第1、2、3種旋轉(zhuǎn)方法可能取的43個(gè)狀態(tài)，根據(jù)這三種旋轉(zhuǎn)方法的當(dāng)前狀態(tài)值，由下述公式P4=order(C1-P1-P2);P5=order(C2-P1-P2-P3)；P6=order(C3-P2-P3)；P7=order(C4-P1-P4-P5);P8=order(C8-P5-PP9)；Pg=order(C6-P3-P5-P6);其中cmod4c0order(c^(cN4)mod4c：：0得出其他P4P9的相應(yīng)狀態(tài)值。爾后將P1,P2,，P9代入下述三個(gè)檢驗(yàn)條件C5=(P1+P3+P5+P7+P9)mod4O=(P4+P7+F8)mod4C9=(P6+R+P9)mod4一一列舉，以求得確實(shí)解。因此可知，上述局部列舉的方法(列舉狀態(tài)數(shù)為43個(gè))比較全部列舉的方法(列舉狀態(tài)數(shù)為49個(gè))來說，由于大幅度減少了列舉量，減少運(yùn)算次數(shù)，因此其時(shí)效顯然改進(jìn)，是一種優(yōu)化了的算法。程序以下：program10194_4;constInp='input.txt';Outp='output.txt';varClock,Map:array[1..3,1..3]ofInteger;｛Clock:第((I+2)mod3)*3+J個(gè)時(shí)鐘從初始時(shí)間到12點(diǎn)的最少搬動(dòng)次數(shù)｝｛Map:最短搬動(dòng)序列中，數(shù)字((I+2)mod3)*3+J的次數(shù)｝procedureInit;varI,J:Integer;beginAssign(lnput.Inp);Reset(Input);forI:=1to3do｛讀入9個(gè)時(shí)鐘指針的初始地址，求出每個(gè)時(shí)鐘從初始到12點(diǎn)的最少搬動(dòng)次數(shù)｝forJ:=1to3dobeginRead(Clock[l,J]);Clock[l,J]:=(4-Clock[I,J])mod4;end;Close(Input);end;functionOrder(K:Integer):Integer;varc:Integer;beginc:=k;whilec<0doinc(c,4);whilec>4thendec(c,4);Order:=k;end;procedureMain;{計(jì)算和輸出最短搬動(dòng)序列}varI,J,K:Integer;begin{列舉最短搬動(dòng)序列中數(shù)字1、2、3的個(gè)數(shù)可能取的343種狀態(tài)}Assign(Output,Outp);Rewrite(Output);forMap[1,1]:=0to3doforMap[1,2]:=0to3doforMap[1,3]:=0to3dobeginMap[2,1]:=Order(Clock[1,1]-Map[1,1]-Map[1,2]);Map[2,3]:=Order(Clock[1,3]-Map[1,2]-Map[1,3]);Map[2,2]:=Order(Clock[1,2]-Map[1,1]-Map[1,2]-Map[1,3]);Map[3,1]:=Order(Clock[2,1]-Map[1,1]-Map[2,1]-Map[2,2]);Map[3,3]:=Order(Clock[2,3]-Map[1,3]-Map[2,2]-Map[2,3]);Map[3,2]:=Order(Clock[3,2]-Map[3,1]-Map[3,3]-Map[2,2]);{依照數(shù)字1、2、3個(gè)數(shù)的當(dāng)前值，得出數(shù)字4~9的個(gè)數(shù)}if((Map[2,1]+Map[3,1]+Map[3,2])mod4=Clock[3,1])and((Map[2,3]+Map[3,2]+Map[3,3])mod4=Clock[3,3])and((Map[2,2]+Map[1,1]+Map[1,3]+Map[3,1]+Map[3,3])mod4=Clock[2,2])thenbegin{若數(shù)字4~9的個(gè)數(shù)滿足檢驗(yàn)條件，則輸出方案}forI:=1to3doforJ:=1to3doforK:=1toMap[I,J]doWrite((I-1)*3+J);Exit;{找到一個(gè)解退后出}end;end;Writeln('NoAnswer!');Close(Output);end;beginInit;Main;end.在上例中，由于起初能夠消除那些顯然不屬于解集的元素，使得算法效率特別高。而減少重復(fù)運(yùn)算、力求提前計(jì)算所需數(shù)據(jù)、使用合適的數(shù)據(jù)結(jié)構(gòu)進(jìn)行算法優(yōu)化等方法也是優(yōu)化列舉算法的常用手段。例14：最正確旅游線路（NOI94）某旅游區(qū)的街道成網(wǎng)格狀（圖2.13）。其中東西向的街道都是旅游街，南北向的街道都是林蔭道。由于游客眾多，旅游街被規(guī)定為單行道，游客在旅游街上只能從西向東走，在林陰道上則既可從南向北走，也能夠從北向南走。阿龍想到這個(gè)旅游區(qū)游玩。他的好友阿福給了他一些建議，用分值表示全部旅游街相鄰兩個(gè)路口之間的街道值得旅游的程度，分值時(shí)從-100到100的整數(shù)，全部林陰道不打分。全部分值不能能全部是負(fù)分。比方圖11是被打過分的某旅游區(qū)的街道圖：-5036-30北17■1943-42-4334-45圖11某旅游區(qū)街道示例圖阿龍能夠從任一個(gè)路口開始旅游，在任一個(gè)路口結(jié)束旅游。請(qǐng)你寫一個(gè)程序，幫助阿龍找一條最正確的旅游線路，使得這條線路的全部分值總和最大。輸入數(shù)據(jù)：輸入文件是

INPUT.TXT

。文件的第一行是兩個(gè)整數(shù)

M

和

N,之間用一個(gè)空格符分開，

M表示有多少條旅游街（

1

三

MW100

）,

N

表示有多少條林陰道（

1W

腐

xx1

）。接下來的

M

行依次給出了由北向南每條旅游街的分值信息。

每行有

個(gè)整數(shù)，依次表示了自西向東旅游街每一小段的分值。同一行相鄰兩個(gè)數(shù)之間用一個(gè)空格分開。輸出數(shù)據(jù)：輸出文件是

OUTPUT.TXT

文件只有一行，是一個(gè)整數(shù)，表示你的程序找到的最正確旅游線

路的總分值。輸入輸出示例：INPUT.TXT

OUTPUT.TXT-50-4736-30-2317-19-34-13-8-42-3-4334-45解析:設(shè)Lij為第I條旅游街上自西向東第J段的分值(iwIwM,1wJwN-1)。比方樣例中Li2=17,L23=-34,L34=34。我們將網(wǎng)格狀的旅游區(qū)街道以林蔭道為界分為N-1個(gè)段，每一段由M條旅游街的對(duì)應(yīng)段成，即第J段成為{Lu,L2J,,LM}(1WJwN-1)。由于旅游方向規(guī)定橫向自西向東，縱向即可沿林陰道由南向北，亦可由北向南，而橫行的街段有分值，縱行無分值,因此最正確旅游路現(xiàn)必定具備以下三個(gè)特點(diǎn)：①來自如干個(gè)連續(xù)的段，每一個(gè)段中取一個(gè)分值；②每一個(gè)分值是所在段中最大的；③起點(diǎn)段和終點(diǎn)段任意，但經(jīng)過段的分值和最大。設(shè)L為第I個(gè)段中的分值最大的段。即L=Max{Ln,L21,,LM}(1w|wN-1)。比方對(duì)于樣例數(shù)據(jù)：L1=Max(-50,17,-42)=17;L2=Max(-47,-19,-3)=-3;L3=Max(36,-34,-43)=36;L4=Max(-30,-13,34)=34;L5=Max(-23,-8,-45)=-8;有了以上的基礎(chǔ)，我們便能夠經(jīng)過圖示描述解題過程，見圖12。我們把將段設(shè)為極點(diǎn)，所在段的最大分值設(shè)為極點(diǎn)的權(quán)，各極點(diǎn)按自西向東的序次相連,組成一條旅游路線。顯然，若是確定西端為起點(diǎn)、東段為終點(diǎn)，則這條旅游路線的總分值最大。LiU圖12求解過程示例圖問題是某些段的最大分值可能是負(fù)值，而最優(yōu)旅游路線的起點(diǎn)和終點(diǎn)任意，在這種情況下，上述旅游路線就不用然最正確了。因此，我們只能列舉這條旅游路線的全部可能的子路線，從中找出一條子路線II+1J(1w|<JwN-1),使得經(jīng)過極點(diǎn)的權(quán)和LI+L+1++LJ最大。設(shè)Best為最正確旅游路線的總分值，初始時(shí)為Sum為0當(dāng)前旅游路線的總分值。我們能夠獲取以下算法:Best:=0;Sum:=0;forI:=1toN-2doforJ:=I+1toNSum:=Li+ifSum>Bestthen

1dobegin+LJ；Best:=Sum;end顯然，這個(gè)算法的時(shí)間復(fù)雜度為0(N2)。而N在1~xx1之間，時(shí)間復(fù)雜度比較高。于是，我們必定對(duì)這個(gè)算法進(jìn)行優(yōu)化。依舊從極點(diǎn)1開始列舉最優(yōu)路線。若當(dāng)前子路線延伸至極點(diǎn)I時(shí)發(fā)現(xiàn)總分值Sum^0,則應(yīng)放棄當(dāng)前子路線。由于無論LI+1為何值，當(dāng)前子路線延伸至極點(diǎn)I+1后的總分值不會(huì)大于LI+1。因此應(yīng)該從極點(diǎn)I+1開始重新考慮新的一條子路線。經(jīng)過這種優(yōu)化,能夠使得算法的時(shí)間復(fù)雜度降到了0(N)。優(yōu)化后的算法描述以下:Best:=0;Sum:=0;forI:=1toN—1dobeginSum:=Sum+LI;ifSum>BestthenBest:=Sum;ifSum<0thenSum:=0;end程序描述以下：{$R-,S-,Q-}{$M65520,0,655360}programNoi94;constMaxN=xx1;Inp='input.txt';0utp='output.txt';varM,N:Word;Best:Longint;Score:array[1..MaxN]ofShortInt;{旅游街?jǐn)?shù)和林陰道數(shù)}{最正確旅游路線的總分值}{描述每個(gè)段的最大分值procedureInit;}varI,J,K:Integer;Buffer:array[1..40960]ofChar;beginAssign(Input,Inp);Reset(Input);SetTextBuf(Input,Buffer);Readln(M,N);FillChar(Score,Sizeof(Score),$80);forI:=1toMdo{開辟文件緩沖區(qū)}forJ:=1toN-1dobegin{讀入旅游街?jǐn)?shù)和林陰道數(shù)}{初始化各段的最大分值}{計(jì)算1~N-1段的最大分值}

{林陰道數(shù)的上限}{文件緩沖區(qū)}Read(K);ifK>Score[J]thenScore[J]:=K;end;Close(lnput);end;procedureOut;beginAssign(Output,Outp);Rewrite(Output);Writeln(Best);Close(Output);end;procedureMain;varI:Integer;Sum:Longint;{當(dāng)前旅游路線的總分值}begin{最正確旅游路線的總分值和當(dāng)前旅游路線的總分值初始化}Best:=0;Sum:=0;｛序次列舉旅游路線的總分值｝forI:=1toN-1dobegin｛統(tǒng)計(jì)當(dāng)前旅游路線的總分值｝Inc(Sum,Score[I]);｛若當(dāng)前最正確，則記下｝ifSum>BestthenBest:=Sum;ifSum<0thenSum:=0;{若總分值＜0,則考慮一條新路線｝end;end;beginInit;｛輸入數(shù)據(jù)｝Main;｛主過程｝Out;｛輸出｝end.2019-2020年高中信息技術(shù)全國青少年奧林匹克聯(lián)賽教課方案模擬法二課題：模擬法目標(biāo)：知識(shí)目標(biāo)：模擬的的實(shí)現(xiàn)能力目標(biāo)：模擬的實(shí)現(xiàn)重點(diǎn)：模擬的實(shí)現(xiàn)難點(diǎn)：模擬的實(shí)現(xiàn)板書表示：1）模擬的引入（例31）2）模擬的應(yīng)用（例32）授課過程：有些問題很難建立列舉、

遞歸等算法，

甚至建立不了數(shù)學(xué)模型，

但能夠依照問題的描述，

用程序模擬某種現(xiàn)象或規(guī)律，進(jìn)而追蹤出結(jié)果。依照模擬對(duì)象的不同樣特點(diǎn)，能夠把計(jì)算機(jī)模擬分為決定型模擬和隨機(jī)行模擬兩大類。決定型模擬是對(duì)決定性現(xiàn)象進(jìn)行的模擬，其所模擬的事件依照固有則規(guī)律發(fā)生發(fā)展，而且最后有明確的結(jié)果。在這種題目中，由于數(shù)學(xué)模型中各種參數(shù)的變化多半是有規(guī)律的，因此算法設(shè)計(jì)一般不是很困難。隨機(jī)模擬是模擬隨機(jī)現(xiàn)象，由于隨機(jī)現(xiàn)象中最少有一個(gè)不確定的因素，因此在模擬中，必定建立一個(gè)用隨機(jī)值來模擬事件的進(jìn)度，在隨機(jī)模擬過程中，經(jīng)過更正變問題的各種參數(shù)，進(jìn)而觀察改正這些參數(shù)所引起的狀態(tài)變化。一般情況是，題目給出某一概率，設(shè)計(jì)者利用隨機(jī)函數(shù)去設(shè)定在某一范圍的隨機(jī)值，將吻合概率的隨機(jī)值作為參數(shù)。爾后依照這一模擬模型張開算法設(shè)計(jì)。隨機(jī)模擬的重點(diǎn)是在概率已知的條件下，怎樣確定隨機(jī)值產(chǎn)生的范圍。這個(gè)隨機(jī)值設(shè)計(jì)得好，模擬收效就好。本節(jié)僅談?wù)摏Q定性模擬問題。相關(guān)隨機(jī)模擬的問題，大家能夠參照一些相關(guān)書籍。例31：約瑟夫問題N

個(gè)人排成一個(gè)圓圈，爾后把這

N

個(gè)人按逆時(shí)針方向分別編號(hào)為

1、2、、

No

從編號(hào)為

1

的人開始按逆時(shí)針計(jì)數(shù)，當(dāng)某人計(jì)數(shù)為

M

的倍數(shù)是，該人出圈；這樣循環(huán)下去，直到圈中只有一個(gè)人留下。解析：這道題憂如用不上什么算法，只要建立一個(gè)循環(huán)鏈表，爾后依照題目中要求的模擬即可。算法描述以下：forI:=1toNDOP[I]:=I+1;{建立循環(huán)鏈表}P[N]:=1;Now:=N;repeat{模擬出圈過程}Now:=N;forI:=1toM-1doNow:=P[Now];{模擬報(bào)數(shù)}P[Now]:=P[Now[Now]];until編號(hào)為P[Now]的人出圈}{P[Now]=Now;Writeln('Thelast直到圈中只剩下一個(gè)人}{manis',Now);例32:SERNET模擬（NOI98-5）SERNET計(jì)算機(jī)網(wǎng)絡(luò)是現(xiàn)代科技發(fā)展的熱點(diǎn)，流傳性能是計(jì)算機(jī)網(wǎng)絡(luò)的主要性能指標(biāo)。網(wǎng)絡(luò)開發(fā)小組設(shè)計(jì)了一種稱為SERNET勺網(wǎng)絡(luò)，并希望開發(fā)一個(gè)模擬軟件來模擬該網(wǎng)絡(luò)的數(shù)據(jù)傳輸情況，進(jìn)而計(jì)算出網(wǎng)絡(luò)的傳輸性能。SERNET網(wǎng)絡(luò)由服務(wù)器及連接它們的網(wǎng)絡(luò)傳輸線路組成，服務(wù)器用服務(wù)器地址予以表記，網(wǎng)絡(luò)傳輸線路為雙向傳輸線路。網(wǎng)絡(luò)傳輸過程中將各種傳輸數(shù)據(jù)分開為若干個(gè)大小同樣的數(shù)據(jù)包，以數(shù)據(jù)包為單位進(jìn)行傳輸。數(shù)據(jù)包在傳輸線路上傳輸時(shí)需要必然的傳輸時(shí)間，不同樣的傳輸線路的傳輸時(shí)間不同樣。服務(wù)器辦理數(shù)據(jù)的時(shí)間較之于傳輸時(shí)間很小，可忽略不計(jì)。每一個(gè)數(shù)據(jù)包中除了包括詳盡的數(shù)據(jù)信息外，還含有以下表記信息：①數(shù)舉包編號(hào)；②數(shù)據(jù)包源服務(wù)器地址；③數(shù)據(jù)包目的服務(wù)器地址。網(wǎng)絡(luò)傳輸?shù)墓δ芫褪菍⒁粋€(gè)個(gè)數(shù)據(jù)包從源服務(wù)器傳輸?shù)侥康姆?wù)器。對(duì)于每一個(gè)數(shù)據(jù)包，詳盡的網(wǎng)絡(luò)傳輸方案為：①源服務(wù)器將待發(fā)送的數(shù)據(jù)包一律復(fù)制若干份并向與之相連的全部賜予其發(fā)送該數(shù)據(jù)包。②服務(wù)器接收到一個(gè)數(shù)據(jù)包后，若是該數(shù)據(jù)包吻合下面任何一個(gè)條件：數(shù)據(jù)包的源服務(wù)器地址與本服務(wù)器地址同樣數(shù)據(jù)包的目的服務(wù)器地址與本服務(wù)器地址同樣本服務(wù)器已轉(zhuǎn)發(fā)過與該數(shù)據(jù)包編號(hào)同樣的數(shù)據(jù)包則接收該數(shù)據(jù)包；否則，服務(wù)器將其復(fù)制若干份并向它相連的全部服務(wù)器轉(zhuǎn)發(fā)該數(shù)據(jù)包。這里，兩臺(tái)服務(wù)器“相連”的含義是它們之間有網(wǎng)絡(luò)傳輸線路直接相連?，F(xiàn)在需要你編一個(gè)程序來模擬SERNE■網(wǎng)絡(luò)中的數(shù)據(jù)包傳輸情況。輸入數(shù)據(jù)：輸入文件的第一行為一個(gè)正整數(shù)N(N<100),表示SERNET中服務(wù)器的數(shù)目。第二行有N個(gè)互不相等的不高出100的正整數(shù)，表示每個(gè)服務(wù)器的地址。第三行有一個(gè)正整數(shù)

M

表示

SERNET

中傳輸線路的數(shù)目。

接下來的

M

行每行用三個(gè)正整

數(shù)表示一條傳輸線路連接的兩臺(tái)服務(wù)器的地址以及該傳輸線路的傳輸時(shí)間。

線路傳輸時(shí)間為不高出

100

的正整數(shù)。接下來的一行為一個(gè)正整數(shù)

K(K<10000

)，表示

SERNET

中數(shù)據(jù)包的數(shù)目。

以下的

K

行每行表示一個(gè)數(shù)據(jù)包的信息，格式為：數(shù)據(jù)包編號(hào)

初步發(fā)送時(shí)間

源服務(wù)器地址

目的服務(wù)器地址其中數(shù)據(jù)包的編號(hào)為互不同樣的小于

100000

的正整數(shù)，輸入文件的最后一行為一個(gè)正整數(shù)T(T<10000),T為輸出時(shí)刻，輸入文件中同一行相鄰兩項(xiàng)之間用一個(gè)或多個(gè)空格分開。輸出數(shù)據(jù)：輸出文件僅含義個(gè)整數(shù)P,表示T時(shí)刻后還在網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)包數(shù)目(編號(hào)同樣的數(shù)據(jù)包為同一數(shù)據(jù)包)。約定：①本題中全部時(shí)間量的單位均同樣；②每一條傳輸線路上在同一時(shí)刻能傳輸任意多個(gè)數(shù)據(jù)包。輸入輸出示例：SERNET」NSERNET.OUT415742109345742642935421021093102433105710567811429323解析：很顯然，本題是對(duì)平常生活中的網(wǎng)絡(luò)文件傳輸進(jìn)行模擬。對(duì)于模擬的事物，第一是將其抽象成數(shù)學(xué)模型。于是我們將輸入文件給出的網(wǎng)絡(luò)信息變換成一張帶權(quán)無向圖。

網(wǎng)上的服務(wù)器作為極點(diǎn)，服務(wù)器之間的傳輸線路作為無向邊，

傳輸線路的傳輸時(shí)間作為邊上的權(quán)。

這里要注意兩點(diǎn)：①試題中服務(wù)器數(shù)N的上限是給定的（N<100）,能夠按常例采用二維數(shù)組儲(chǔ)藏圖的信息。但問題是，服務(wù)器用服務(wù)器的地址予以表記，而這些地址是無序的。若是采用服務(wù)器地址作為數(shù)組下表，即會(huì)帶來計(jì)算的不便，造成內(nèi)存的無端浪費(fèi)。因此我們改變服務(wù)器的表記方式，用服務(wù)器地址的輸入序次表記服務(wù)器并將這些序號(hào)作為數(shù)組下標(biāo)。比方：服務(wù)器地址57421093服務(wù)器表記（ID）1234②一條傳輸線路上的信息可能會(huì)由于有多種傳輸時(shí)間而重復(fù)輸入多次。我們?nèi)∑渲凶钚鬏敃r(shí)間和最大傳輸時(shí)間作為線路的傳輸時(shí)間范圍。若一條傳輸線路的信息僅輸入一次，則線路的最小傳輸時(shí)間的最大傳輸時(shí)間設(shè)為輸入的傳輸時(shí)間。設(shè)：typeTlink=recordShort，Long:Byte;End;varLinks:array[1..N,1..N]ofTlink;

｛傳輸線路的時(shí)間種類｝｛最短傳輸時(shí)間｝｛最長傳輸時(shí)間｝｛網(wǎng)絡(luò)｝F表列出了樣例中的網(wǎng)絡(luò)信息:服務(wù)器1地址（ID）服務(wù)器J地址（ID）傳輸時(shí)間57（1）42（2）157（1）42（2）357（1）42（2）642（2）93（4）542（2）10（3）210（3）93（4）10Links[1,2].Short=Links[2,1].Short=1Links[1,2].Long=Links[2,1].Long=6Links[2,4].Short=Links[4,2].Short=5Links[2,4].Long=Links[4,2].Long=5Links[2,3].Short=Links[3,2].Short=2Links[2,3].Long=Links[3,2].Long=2Links[3,4].Short=Links[4,3].Short=10Links[3,4].Long=Links[4,3].Long=10見圖2-17圖27網(wǎng)絡(luò)傳輸示例圖由于試題約定“每一條傳輸線路上在同一時(shí)刻能傳輸任意多個(gè)數(shù)據(jù)包”，因此數(shù)據(jù)包的傳輸互不影響。我們能夠一個(gè)一個(gè)的模擬數(shù)據(jù)包的傳輸過程，從中統(tǒng)計(jì)出T時(shí)刻后仍在網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)包數(shù)?，F(xiàn)在的問題是怎樣鑒識(shí)T時(shí)刻后當(dāng)前一個(gè)數(shù)據(jù)包可否還在網(wǎng)絡(luò)中傳輸模擬一個(gè)數(shù)據(jù)包在網(wǎng)絡(luò)中的傳輸情況是算法的基礎(chǔ)。設(shè)：it――當(dāng)前數(shù)據(jù)包序號(hào)；accepted[l]---------服務(wù)器I接受it數(shù)據(jù)包的標(biāo)志(1=I=N)True服務(wù)器i接受it〔False服務(wù)器i未接受it或?qū)⑹盏降膇t轉(zhuǎn)發(fā)給與它相鄰的全部服務(wù)器recevie[I]是服務(wù)器I向與它相連的全部服務(wù)器轉(zhuǎn)發(fā)數(shù)據(jù)包的開始時(shí)刻。由于服務(wù)器處理數(shù)據(jù)的時(shí)間忽略不計(jì)，因此收到數(shù)據(jù)包的時(shí)刻即為轉(zhuǎn)發(fā)時(shí)刻。Recevie[l]=$FFFF時(shí)說明當(dāng)前未確定服務(wù)器I轉(zhuǎn)發(fā)數(shù)據(jù)包的時(shí)刻也許服務(wù)器I已接受了ito顯然，若是receive[I]<>$FFFF且accepted[I]=false，則服務(wù)器I可能立刻收到ito若是依照網(wǎng)絡(luò)的傳輸方案確定服務(wù)器I已接受了it，貝Uaccepted[I]=true。開始時(shí)，it的源服務(wù)器第一將it復(fù)制若干份并同與之相連的全部服務(wù)器發(fā)送，即receive[it的源服務(wù)器]=it的源服務(wù)器的初步發(fā)送時(shí)間，其他服務(wù)器的receive值為$FFFF。此時(shí)，除可確定it的目標(biāo)服務(wù)器(但不能夠與it的服務(wù)器同址)為接受服務(wù)器外，其他服務(wù)器為收到it，即ifit的源服務(wù)器<>it的目標(biāo)服務(wù)器thenbeginaccepted[it的目標(biāo)服務(wù)器]:=true;其他服務(wù)器的accepted值設(shè)為false;end;爾后重復(fù)以下過程：在可接受it的服務(wù)器會(huì)集中搜尋一個(gè)最早收到數(shù)據(jù)包的滿足手下條件的服務(wù)器min{receive[I]|(receive[I]<>$FFFF)and(accepted[I]=false)}服務(wù)器I試圖向與之相連的全部服務(wù)器J(Links[l,J].Short<>0|1wJwN發(fā)送數(shù)據(jù)包。I

):若是服務(wù)器J可收到it(receive[I]+Links[I,J].Short<receive[J])，則將服務(wù)器J的receive值修正為receive[I]+Links[I,J].Short，讓其在該時(shí)刻收到和轉(zhuǎn)發(fā)it；若是其中一個(gè)服務(wù)器J在T時(shí)刻后才能接受來自服務(wù)器I的it(receive[I]+Links[I,J].Long>T),則判斷T時(shí)刻后仍有一個(gè)數(shù)據(jù)包在網(wǎng)絡(luò)中傳輸，算法結(jié)束；若是在T時(shí)刻前與服務(wù)器I相連的全部線路完成傳輸it的任務(wù)，則依照網(wǎng)絡(luò)的傳輸方案確定服務(wù)器I接受了it，accepted[I]True，receive[I]$FFFF。這一過程素來進(jìn)行到全部服務(wù)器都不再轉(zhuǎn)發(fā)數(shù)據(jù)包為止，即全部服務(wù)器的receive值為$FFFF。上述算法由一個(gè)布爾函數(shù)Alive(it)描述。若數(shù)據(jù)包it在T時(shí)刻后還在網(wǎng)絡(luò)中流傳，則該函數(shù)返回True;否則返回False。算法描述以下：functionAlive(it):Boolean;BeginAlive:=True;初始化receive的值為$FFFF;Receive[it的源服務(wù)器]=it的開始發(fā)送時(shí)間初始化Accepted的值為False;Accepted[it的目標(biāo)服務(wù)器]=truerepeat搜尋一個(gè)receive值最小的服務(wù)器I;ifReceive[I]=$FFFFthenBreak;ifAccepted[I]=FalsethenforJ:=1toNdobeginif服務(wù)器I與服務(wù)器J有傳輸線路then修正receive[J]值;if服務(wù)器J在T時(shí)刻后才能接收itthenexit;end;Accepted[I]:=True;Receive[I]:=$FFFF;untilFalse;Alive:=False;end;對(duì)每一個(gè)數(shù)據(jù)包都求一次Alive，Alive函數(shù)值為True的次數(shù)P就是T時(shí)刻后仍在網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)包數(shù)。如下：P:=0;forI:=1to數(shù)據(jù)包數(shù)KdoifAlive(I)thenP:=P+1；Writeln(P)程序以下：{$R-,S-,Q-}programNOI98_5;constInp='sernet.in';Outp='sernet.out';MaxN=99;MaxK=9999;typeTPackage=recordSend:Word;Source:Byte;Target:Byte;end;TLink=recordShort:Byte;Long:Byte;end;varN:Byte;K:Word;T:Word;Index:array[1..MaxN]ofByte;

{輸入文件名串}{輸出文件名串}{服務(wù)器數(shù)的上限}{數(shù)據(jù)包數(shù)的上限}{數(shù)據(jù)包種類}{發(fā)出時(shí)刻}{源服務(wù)器}{目的服務(wù)器}{傳輸線的時(shí)間種類}{最短傳輸時(shí)間}{最長傳輸時(shí)間}{Ind{服務(wù)器數(shù)}e{數(shù)據(jù)包數(shù)}x{[}輸出時(shí)刻P:Word;{輸出時(shí)刻后還在網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)包數(shù)}{I輸入數(shù)據(jù)}]——地址為I的服務(wù)器序號(hào)}Links:array[1..MaxN,1..MaxN]ofTLink;{Links[I,J]——服務(wù)器I的服務(wù)器J的傳輸時(shí)間}Packages:array[1..MaxPackage]ofTPackage;{數(shù)據(jù)包序列}procedureInit;var{傳輸線路數(shù)}I,J:Word;{當(dāng)前傳輸線相連的兩個(gè)服務(wù)器序號(hào)}M:Word;{當(dāng)前傳輸線路的傳輸時(shí)間}S1,S2:Byte;{數(shù)據(jù)包編號(hào)}Time:Word;PackageID:Longint;BeginAssign(Input,Inp);{讀服務(wù)器數(shù)}Reset(Input);表}{度入每個(gè)服務(wù)器地址，計(jì)算IndexReadln(N);forI:=1toNdobeginRead(J);Index[J]:=I;end;Readln(M);{讀傳輸線路輸}FillChar(Links,Sizeof(Links),0);{Links表初始化}forI:=1toMdobegin{輸入每條線路的信息}Readln(S1,S2,Time);{讀相連的兩臺(tái)服務(wù)器地址和傳輸時(shí)間}S1:=Index[S1];{計(jì)算這兩臺(tái)服務(wù)器的序號(hào)}S2:=Index[S2];if{計(jì)(Links[S1,S2].Short=0)or(Links[S1,S2].Short>Time)then算該線路的最短傳輸時(shí)間和最長傳輸時(shí)間Links[S1,S2].Short:=Time;ifLinks[S1,S2].Long<TimethenLinks[S1,S2].Long:=Time;Links[S2,S1]:=Links[S1,S2];end;Readln(K);for{讀數(shù)據(jù)包數(shù)}I:=1toKdo{讀每一個(gè)數(shù)據(jù)包的信息}withPackages[I]doReadln(PackageID,Send,Source,Target);{讀第I個(gè)數(shù)據(jù)包的編號(hào)，初步發(fā)送時(shí)間，源服務(wù)器地址，目的服務(wù)器地址Readln(T);{讀入輸出時(shí)刻}Close(Input);end;functionAlive(It:TPackage):Boolean;{模擬數(shù)據(jù)包It在T時(shí)刻還在網(wǎng)絡(luò)中傳輸，則返回TrueI,J:Byte;Time:Word;Receive:array[1..MaxN]ofWord;{Receive[I]：服務(wù)器I收到下一個(gè)數(shù)據(jù)的時(shí)刻Accepted:array[1..MaxN]ofBoolean;{Accepted[I]：為服務(wù)器I接收It的標(biāo)志}

;否則返回}

False}varbeginAlive:=True;FillChar(Receive,Sizeof(Receive),$FF);{初始時(shí)，全部服務(wù)器未收到任何數(shù)據(jù)包}FillChar(Accepted,Sizeof(Accepted),False);Receive[Index[It.Source]]:=It.Send;{源服務(wù)器在發(fā)送了It后開始接受下一個(gè)數(shù)據(jù)包ifIt.Source<>It.TargetthenAccepted[Index[It.Target]]:=True;

}{

若源服務(wù)器與目的服務(wù)器不同樣，則確定目的服務(wù)器收到數(shù)據(jù)包