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

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

能力目標：列舉算法的應用！重點：利用列舉算法解決實責問題難點：列舉算法的次數(shù)確定板書表示：1）簡單列舉（例

7、例

8、例

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

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

:

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

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

‘+'

,B,

‘='

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

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

,2,3},2,3}C解變量值的可能取值范圍C?{1,2,3}(A,B,C)?{(1，1，則問題的可能解有27個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)}在上述可能解會集中，滿足題目給定的檢驗條件的解元素，即為問題的解。若是我們無法起初確定解的個數(shù)或各解的值域，則不能夠用列舉，只能采用搜尋等算法求解。由于回溯法在搜尋每個可能解的列舉次數(shù)一般不僅一次，因此，對于同樣規(guī)模的問題，回溯算法要比列舉法時間復雜度稍高。例8給定一個二元一次方程aX+bY=c。從鍵盤輸入a,b,c的數(shù)值，求X在［0,100］,Y在［0,100］范圍內(nèi)的全部整數(shù)解。解析：要求方程的在一個范圍內(nèi)的解，只要對這個范圍內(nèi)的全部整數(shù)點進隊列舉，看這些點可否滿足方程即可。參照程序：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.從上例能夠看出，所謂列舉法，指的是從可能的解會集中一一列舉各元素，用題目給定的檢驗條件判斷哪些是無用的，哪些是適用的?能使命題建立，即為其解。例9巧妙填數(shù)將1?9這九個數(shù)字填入九個空格中。每一橫行的三個數(shù)字組成一個三位數(shù)。若是要使第二行的三位數(shù)是第一行的兩倍，第三行的三位數(shù)是第一行的三倍，應怎樣填數(shù)。如圖6:192384576圖6解析：本題目有9個格子，要求填數(shù)，若是不考慮問題給出的條件，共有9!=362880種方案，在這些方案中吻合問題條件的即為解。因此能夠采用列舉法。但仔細解析問題，顯然第一行的數(shù)不會高出400，實質(zhì)上只要確定第一行的數(shù)就可以依照條件算出其他兩行的數(shù)了。這樣僅需列舉400次。因此設計參照程序：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ù)學競賽中

,A

、B、C、D、E

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

出他們的詳盡名次

,

即誰是第幾名？

條件

1:

你若是認為

A,B,C,D,E

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

,

便大錯。由于

沒猜對任何一個優(yōu)勝者的名次。也沒猜對任何一對名次相鄰的學生。條件2:你若是按D,A,E,C,B來排列五人名次的話,其結果是:說對了其中兩個人的名次。還猜中了兩對名次相鄰的學生的名次序次。解析：本題是一個邏輯判斷題，一般的邏輯判斷題都采用列舉法進行解決。5個人的名次分別能夠有5!=120種排列可能，由于120比較小，因此我們對每種情況進隊列舉,然后依照條件判斷哪些吻合問題的要求。依照已知條件，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沒猜對一個人的名次}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;{他們名次互不重復}{DAECB猜對了兩個人的名次}IfOrd(A=2)+Ord(B=5)+Ord(C=4)+Ord(D=1)+Ord(E=3)<>2ThenContinue;{ABCDE沒猜對一對相鄰名次}If(B=A+1)Or(C=B+1)Or(D=C+1)Or(E=D+1)ThenContinue;{DAECB猜對了兩對相街坊名次}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:來自不同樣國家的四位留學生A,B,C,D在一起講話，他們只會中、英、法、日四種語言中的2種，情況是，沒有人既會日語又會法語;A會日語，但D不會,A和D能互相講話,B不會英語，但A和C講話時卻要B當翻譯,B,C,D三個想互相講話，但找不到共同的語言,只有一種語言3人都會，編程確定A,B,C,D四位留學生各會哪兩種語言。解析：將中、法、日、英四種語言分別定義為CHNFRHJPNENG則四種語言中取兩種共有(CHN,ENG),(CHN,FRH,(CHN,JPN),(ENG,FRH),(ENG,JPN),(FRH,JPN)六種組合，分別定義為1、2、3、4、5、6。據(jù)已知，沒有人既會日語又會法語；因此，組合6不會出現(xiàn)；A會日語，因此A只可能等于3、5；D不會日語，因此D只可能等于1、2、4；B不會英語，因此B只可能等于2、3;見下表。若是我們對ABC、D分別進隊列舉，依照判斷條件，即可找到答案。(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');三個想互相講話，但找不到共同的語言Show(C,C);Show(D,'D');end;beginforA:=3to5doifA<>4thenforB:=2to3doforC:=1to5doforD:=1to4doifD<>3thenbegin{A和D能互相講話}Can1:=No[A]*No[D]<>[];{A和C講話時卻要B當翻譯

}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人都會}Can4:=Ord(Might(CHN))+Ord(Might(ENG))+Ord(Might(FRH))+Ord(Might(JPN))=1;ifCan1andCan2andCan3andCan4thenPrint(A,B,C,D);end;end.例12

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

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

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

，如圖

7

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

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

***的每一個數(shù)字都是素數(shù)

，而且這樣的算式是唯一的。請你也研究

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

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

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

45=1024

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

可否是都是由素數(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;{它們分別是兩個四位數(shù)，一個五位數(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:時鐘問題（10194-4）在圖8所示的3*3矩陣中有9個時鐘，我們的目標是旋轉時鐘指針，使全部時鐘的指針都指向12點。贊同旋轉時鐘指針的方法有9種，每一種搬動用一個數(shù)字號（1，2，，9）??O?????OOOOOOOOOOOO123?OOoeoooe?OO???ooe?OOoeoooe456OOOOOOOO??OOOOOo????O???o??7呂5圖8九種時鐘狀態(tài)表示。圖2-11示出9個數(shù)字號與相應的受控制的時鐘，這些時鐘在圖中以灰色標出，其指——受控制的時鐘圖9九種被控制方式針將順時針旋轉90度。輸入數(shù)據(jù)：由輸入文件INPUT.TXT讀9個數(shù)碼，這些數(shù)碼給出了9個時鐘時針的初始地址。數(shù)碼與時刻的對應關系為：0――12點1――3點2――63――9

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

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

INPUT.TXT

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

M

和

N,之間用一個空格符分開，

M表示有多少條旅游街（

1

三

MW100

）,

N

表示有多少條林陰道（

1W

腐

xx1

）。接下來的

M

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

每行有

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

OUTPUT.TXT

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

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

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

1dobegin+LJ；Best:=Sum;end顯然，這個算法的時間復雜度為0(N2)。而N在1~xx1之間，時間復雜度比較高。于是，我們必定對這個算法進行優(yōu)化。依舊從極點1開始列舉最優(yōu)路線。若當前子路線延伸至極點I時發(fā)現(xiàn)總分值Sum^0,則應放棄當前子路線。由于無論LI+1為何值，當前子路線延伸至極點I+1后的總分值不會大于LI+1。因此應該從極點I+1開始重新考慮新的一條子路線。經(jīng)過這種優(yōu)化,能夠使得算法的時間復雜度降到了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;{旅游街數(shù)和林陰道數(shù)}{最正確旅游路線的總分值}{描述每個段的最大分值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{讀入旅游街數(shù)和林陰道數(shù)}{初始化各段的最大分值}{計算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;{當前旅游路線的總分值}begin{最正確旅游路線的總分值和當前旅游路線的總分值初始化}Best:=0;Sum:=0;｛序次列舉旅游路線的總分值｝forI:=1toN-1dobegin｛統(tǒng)計當前旅游路線的總分值｝Inc(Sum,Score[I]);｛若當前最正確，則記下｝ifSum>BestthenBest:=Sum;ifSum<0thenSum:=0;{若總分值＜0,則考慮一條新路線｝end;end;beginInit;｛輸入數(shù)據(jù)｝Main;｛主過程｝Out;｛輸出｝end.2019-2020年高中信息技術全國青少年奧林匹克聯(lián)賽教課方案模擬法二課題：模擬法目標：知識目標：模擬的的實現(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)象中最少有一個不確定的因素，因此在模擬中，必定建立一個用隨機值來模擬事件的進度，在隨機模擬過程中，經(jīng)過更正變問題的各種參數(shù)，進而觀察改正這些參數(shù)所引起的狀態(tài)變化。一般情況是，題目給出某一概率，設計者利用隨機函數(shù)去設定在某一范圍的隨機值，將吻合概率的隨機值作為參數(shù)。爾后依照這一模擬模型張開算法設計。隨機模擬的重點是在概率已知的條件下，怎樣確定隨機值產(chǎn)生的范圍。這個隨機值設計得好，模擬收效就好。本節(jié)僅談論決定性模擬問題。相關隨機模擬的問題，大家能夠參照一些相關書籍。例31：約瑟夫問題N

個人排成一個圓圈，爾后把這

N

個人按逆時針方向分別編號為

1、2、、

No

從編號為

1

的人開始按逆時針計數(shù)，當某人計數(shù)為

M

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

M

表示

SERNET

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

接下來的

M

行每行用三個正整

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

線路傳輸時間為不高出

100

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

K(K<10000

)，表示

SERNET

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

以下的

K

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

初步發(fā)送時間

源服務器地址

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

100000

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

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

傳輸線路的傳輸時間作為邊上的權。

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

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

):若是服務器J可收到it(receive[I]+Links[I,J].Short<receive[J])，則將服務器J的receive值修正為receive[I]+Links[I,J].Short，讓其在該時刻收到和轉發(fā)it；若是其中一個服務器J在T時刻后才能接受來自服務器I的it(receive[I]+Links[I,J].Long>T),則判斷T時刻后仍有一個數(shù)據(jù)包在網(wǎng)絡中傳輸，算法結束；若是在T時刻前與服務器I相連的全部線路完成傳輸it的任務，則依照網(wǎng)絡的傳輸方案確定服務器I接受了it，accepted[I]True，receive[I]$FFFF。這一過程素來進行到全部服務器都不再轉發(fā)數(shù)據(jù)包為止，即全部服務器的receive值為$FFFF。上述算法由一個布爾函數(shù)Alive(it)描述。若數(shù)據(jù)包it在T時刻后還在網(wǎng)絡中流傳，則該函數(shù)返回True;否則返回False。算法描述以下：functionAlive(it):Boolean;BeginAlive:=True;初始化receive的值為$FFFF;Receive[it的源服務器]=it的開始發(fā)送時間初始化Accepted的值為False;Accepted[it的目標服務器]=truerepeat搜尋一個receive值最小的服務器I;ifReceive[I]=$FFFFthenBreak;ifAccepted[I]=FalsethenforJ:=1toNdobeginif服務器I與服務器J有傳輸線路then修正receive[J]值;if服務器J在T時刻后才能接收itthenexit;end;Accepted[I]:=True;Receive[I]:=$FFFF;untilFalse;Alive:=False;end;對每一個數(shù)據(jù)包都求一次Alive，Alive函數(shù)值為True的次數(shù)P就是T時刻后仍在網(wǎng)絡中傳輸?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;

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

;否則返回}

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

}{

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