信息技術(shù)奧林匹克競(jìng)賽復(fù)習(xí)綱要

1、完善程序題解題方法完善程序題解題方法一、完善程序題解題步驟：一、完善程序題解題步驟：1、仔細(xì)閱讀文字解釋，理解題意和提供的解題思路、仔細(xì)閱讀文字解釋，理解題意和提供的解題思路2、根據(jù)問(wèn)題的求解要求，了解輸入、輸出內(nèi)容和問(wèn)題處、根據(jù)問(wèn)題的求解要求，了解輸入、輸出內(nèi)容和問(wèn)題處理方法理方法3、先閱讀主程序，了解輸出變量和輸出要求以及主程序、先閱讀主程序，了解輸出變量和輸出要求以及主程序中需要調(diào)用的過(guò)程或函數(shù)是哪些。中需要調(diào)用的過(guò)程或函數(shù)是哪些。4、閱讀過(guò)程或函數(shù)，了解其完成的功能、閱讀過(guò)程或函數(shù)，了解其完成的功能5、填空方法：一般從主程序最后輸出要求，反推主程序、填空方法：一般從主程序最后輸出要求，

2、反推主程序中的變量填寫或表達(dá)式、語(yǔ)句等的書寫中的變量填寫或表達(dá)式、語(yǔ)句等的書寫6、根據(jù)主程序參數(shù)與子程序參數(shù)傳遞關(guān)系，填寫子程序、根據(jù)主程序參數(shù)與子程序參數(shù)傳遞關(guān)系，填寫子程序的變量，根據(jù)子程序需要完成的功能，完成子程序填空的變量，根據(jù)子程序需要完成的功能，完成子程序填空7、填寫完畢，再將程序整個(gè)閱讀、執(zhí)行一遍，看能否完、填寫完畢，再將程序整個(gè)閱讀、執(zhí)行一遍，看能否完成問(wèn)題提出的要求。成問(wèn)題提出的要求。二、運(yùn)用求解二、運(yùn)用求解 1 、找出小于、找出小于33的的6個(gè)正整數(shù)，用這些整數(shù)進(jìn)行加法運(yùn)算，個(gè)正整數(shù)，用這些整數(shù)進(jìn)行加法運(yùn)算，使得包括原來(lái)的整數(shù)在內(nèi)能組成盡可能多的不同整數(shù)。使得包括原來(lái)的整數(shù)

3、在內(nèi)能組成盡可能多的不同整數(shù)。 例如：用例如：用2，3，5可以組成可以組成5，7，8，10再加再加2，3可以組成可以組成6個(gè)不同的數(shù)。個(gè)不同的數(shù)。Begin a1:=1 ; t:=0; for I:=2 to 6 do begin _ for j:=1 to I-1 do s:=_ aI := _ end; for I:= 1 to 6 do begin T:= _ Write (aI, ) ;End;Writeln ( t ) ;End. s:=0 ; s:=s+aj ; aI:=s ; t:=t+aI2 2、20002000年問(wèn)題（初中）：年問(wèn)題（初中）：將將2 2 n n 個(gè)個(gè)0 0和和

4、2 2 n n個(gè)個(gè)1 1，排成一圈。從任一個(gè)位置開始，排成一圈。從任一個(gè)位置開始，每次按逆時(shí)針的方向以長(zhǎng)度為每次按逆時(shí)針的方向以長(zhǎng)度為n+1n+1的單位進(jìn)行數(shù)二進(jìn)制的單位進(jìn)行數(shù)二進(jìn)制數(shù)。要求給出一種排法，用上面的方法產(chǎn)生出來(lái)的數(shù)。要求給出一種排法，用上面的方法產(chǎn)生出來(lái)的2 2 n+1n+1個(gè)二進(jìn)制數(shù)都不相同。當(dāng)個(gè)二進(jìn)制數(shù)都不相同。當(dāng)n=2n=2時(shí)，即有時(shí)，即有2 2 2 2 個(gè)個(gè)0 0和和2 22 2個(gè)個(gè)1 1排列如右下：排列如右下：比如，從比如，從A A位置開始，逆時(shí)針?lè)较蛉∪齻€(gè)數(shù)位置開始，逆時(shí)針?lè)较蛉∪齻€(gè)數(shù)000000，然后再?gòu)?，然后再?gòu)腂 B位置上開始取三個(gè)數(shù)位置上開始取三個(gè)數(shù)00100

5、1，接著取，接著取010010可以得到可以得到000000，001001，010010，101101，011011，111111，110110共共8 8個(gè)二進(jìn)制數(shù)，并且都個(gè)二進(jìn)制數(shù)，并且都不相同。不相同。程序說(shuō)明：以程序說(shuō)明：以N=4N=4為例，即有為例，即有1616個(gè)個(gè)0 0、1616個(gè)個(gè)1 1，數(shù)組，數(shù)組A A用以記用以記錄錄3232個(gè)個(gè)0 0、1 1的排法，數(shù)組的排法，數(shù)組B B統(tǒng)計(jì)二進(jìn)制數(shù)是否已出現(xiàn)過(guò)。統(tǒng)計(jì)二進(jìn)制數(shù)是否已出現(xiàn)過(guò)。本題利用二進(jìn)制加法運(yùn)算的原理。本題利用二進(jìn)制加法運(yùn)算的原理。A數(shù)組存放每位二進(jìn)制數(shù)，數(shù)組存放每位二進(jìn)制數(shù)，B數(shù)組用于判斷所產(chǎn)生的數(shù)是數(shù)組用于判斷所產(chǎn)生的數(shù)是否重

6、復(fù)否重復(fù)為了減少循環(huán)次數(shù)，程序中將最后五位置為了減少循環(huán)次數(shù)，程序中將最后五位置1，前面五位置，前面五位置0PROGRAM NO100 ； VAR A： ARRAY 1.36 OF 0.1； B： ARRAY 0.31 OF INTEGER ； I，J，K，S，P： INTEGER ； BEGIN FOR I：=1 TO 36 DO AI：= 0 ； FOR I：=28 TO 32 DO AI：= 1 ； P：=1； A6：=1； WHILE （P=1） DO BEGIN J：=27；WHILE AJ=1 DO J：= J 1； FOR I：=J+1 TO 27 DO FOR I：=0 TO

7、31 DO BI：=0； FOR I：=1 TO 32 DO begin FOR K：=I TO I+4 DO S：=S*2+AK ； END； S：=0 ； FOR I：=0 TO 31 DO S：=S+BI ； IF THEN P：=0 ； END； FOR I：=1 TO 32 DO FOR J：=I TO I+4 DO WRITE（AJ）；）； WRITELN ；END. AJ:=1 ;AI:=0 ;S:=0 ;BS:=1 ;S=32初中，問(wèn)題：初中，問(wèn)題： 多項(xiàng)式乘法運(yùn)算：多項(xiàng)式乘法運(yùn)算：P（X）=2X2- x +1，q（x）=x+1 p（x）*q（x）=（2x2x+1）*（x+1）

8、=2x3 + X2-+1 說(shuō)明：說(shuō)明：多項(xiàng)式的表示：系數(shù)、指數(shù)多項(xiàng)式的表示：系數(shù)、指數(shù)如上例中：如上例中：P（X）：）： 系數(shù)系數(shù) 指數(shù)指數(shù) Q（X） 系數(shù)系數(shù) 指數(shù)指數(shù) 2 2 1 1 -1 1 1 0 1 0 0 0 0 0P * Q 的結(jié)果存入的結(jié)果存入C中。其輸出格式是：依次用一對(duì)括號(hào)中。其輸出格式是：依次用一對(duì)括號(hào)內(nèi)的（系數(shù)、指數(shù)）分別來(lái)表示。如上例的輸出結(jié)果表示內(nèi)的（系數(shù)、指數(shù)）分別來(lái)表示。如上例的輸出結(jié)果表示為：（為：（2，3）（）（1，2）（）（1，0）2程序清單：程序清單： PROGRAM NO100_7 ; VAR I, J , K , L , JP , JQ , JC ,

9、 X, Y ,X1, Y1 : INTEGER ; P, Q : ARRAY 1.10,1.2 OF INTEGER ; C: ARRAY1.20 , 1.2 OF INTEGER ;BEGIN JP: = 0 ; READLN (X,Y) ; WHILE X 0 DO BEGIN JP:=JP+1 ; PJP,1:= X ; PJP,2 :=Y ; READLN(X,Y) ; END ; JQ:=0 ; READLN(X,Y) ; WHILE X0 DO BEGIN JQ:=JQ+1 ; QJQ,1 :=X ; QJQ,2:=Y ; READLN(X,Y) ; END; JC:=1; CJC

10、,1:= 0; CJC,2:= -1000 ; FOR I:=1 TO JP DO BEGIN Y：=PI,2 ; FOR J:=1 TO JQ DO BEGIN ； Y1：=Y+QJ，2 ； K:=1 ; WHILE Y1CK,2 DO K:=K+1 ; IF Y1 = CK,2 THEN ELSE BEGIN FOR L：=JC DOWNTO K DO BEGIN CL+1，1：=CL，1 ；CL+1，2：=CL，2 ； END; CK,1:=X1 ; CK,2:=Y1; END； END; END;END; FOR I:=1 TO JC DO IF THEN WRITE （ (,CI,1

11、 , , ,C I,2 , )）；）； READLN ; END. X:= PI,1 ;X1:=X*QJ,1;CK,1:=CK,1+X1 ;JC:=JC+1 ;CI,10 2000年年 高中問(wèn)題高中問(wèn)題1 求一棵樹的深度和寬度。例如有如下的一棵樹：樹的深求一棵樹的深度和寬度。例如有如下的一棵樹：樹的深度為從根結(jié)點(diǎn)開始到葉結(jié)點(diǎn)結(jié)束的最大深度，樹的寬度為度為從根結(jié)點(diǎn)開始到葉結(jié)點(diǎn)結(jié)束的最大深度，樹的寬度為同一層上結(jié)點(diǎn)數(shù)的最大值。在左圖中樹的深度為同一層上結(jié)點(diǎn)數(shù)的最大值。在左圖中樹的深度為4，寬度，寬度為為3。用鄰接表來(lái)表示樹，見如下表（一）用鄰接表來(lái)表示樹，見如下表（一）12340020000035

12、0000460000500000670000700000program no100_6; var i , j , sp1, sp2 , L , max : integer ; tree : array 1.20 , 1.6 of integer ; q : array 1.100 , 0.6 of integer ; d : array 0.20 of integer ; BEGIN For I:=1 to 14 do for j:=1 to 6 do tree I, j := 0 ; For j:=1 to 14 do tree j ,1 := j ; Tree1,2:=2 ; tree1,

13、3:=3 ; tree 1,4 :=4 ; tree2,2:=5 ; Tree2,3:=6 ; tree3,2:=7 ; tree3,3 :=8 ; tree4,2:=9 ; Tree4,3:=10; tree4,4:=11;tree7,2:=12 ; tree7,3:=13 ; tree13,2:=14 ; Sp1 := 1 ; sp2:=1 ; For i:=1 to 6 do q 1, i :=tree 1, i ; Q1,0: =1 ; While do begin L:= ； j:=2 ; while do begin sp2 :=sp2 +1 ; qsp2 ,0 := l; qsp

14、2 , 1 :=qsp1 , j ; for i:=2 to 6 do qsp2 , i := treeqsp1,j , i ; j:=j+1 ; end ; sp1:=sp1 +1 ; end ;writeln ； for i:=0 to 20 do di:=0 ; for i:= 1 to sp2 do dqi,0 := max:= d1 ; for i:=2 to 20 do if dimax then max:= di ; readln ;end.end. SP1=SP2 ; (2) QSP1,0+1 ;(3) QSP1,J0 ; (4) (QSP2,0) L ;(5) DQI,0 +

15、1 ;20012001年年 初中初中 1 1、輸入、輸入n n個(gè)個(gè)0 0到到100100之間的整數(shù)，由小到大排序輸出，每之間的整數(shù)，由小到大排序輸出，每行輸出行輸出8 8個(gè)個(gè)程序清單：程序清單：PROGRAM CHU7_5PROGRAM CHU7_5；VAR IVAR I，J J，K K，N N，X X：INTEGERINTEGER；B B：ARRAY0.100OF INTEGERARRAY0.100OF INTEGER； BEGINBEGINREADLN(N)READLN(N)；FOR I:=0 TO 100 DO BI:=0FOR I:=0 TO 100 DO BI:=0；FOR I:=1

16、 TO N DO FOR I:=1 TO N DO BEGINBEGINREADLN(X)READLN(X)；BX:=BX:=ENDEND； FOR I:=0 TO 100 DO FOR I:=0 TO 100 DOWHILEDOBEGINWRITE()；K:=K+1；BI:=BI-1；IFTHEN WRITELNEND；READLNEND. (1) BX:=BX+1;(2) K:=0 ;(3) BI0 (4) I: 4 ;(5) K MOD 8=0 2000年年 高中高中2. 在在A，B兩個(gè)城市之間設(shè)有兩個(gè)城市之間設(shè)有N個(gè)路站個(gè)路站(如下圖中的如下圖中的S1，且且N100)，城市與路站之間、

17、路站和路站之城市與路站之間、路站和路站之間各有若干條路段間各有若干條路段(各路段數(shù)各路段數(shù)20，且每條路段上的，且每條路段上的距離均為一個(gè)整數(shù)距離均為一個(gè)整數(shù))。 A，B的一條通路是指：從的一條通路是指：從A出發(fā)，可經(jīng)過(guò)任一路出發(fā)，可經(jīng)過(guò)任一路段到達(dá)段到達(dá)S1，再?gòu)脑購(gòu)腟1出發(fā)經(jīng)過(guò)任一路段，出發(fā)經(jīng)過(guò)任一路段，最后到達(dá)最后到達(dá)B。通路上路段距離之和稱為通路距離通路上路段距離之和稱為通路距離(最大距離最大距離1000)。當(dāng)。當(dāng)所有的路段距離給出之后，求出所有不同距離的通路個(gè)所有的路段距離給出之后，求出所有不同距離的通路個(gè)數(shù)數(shù)(相同距離僅記一次相同距離僅記一次)。例如：下圖所示是當(dāng)例如：下圖所示是當(dāng)

18、N=1時(shí)的情況：時(shí)的情況：從從A A到到B B的通路條數(shù)為的通路條數(shù)為6 6，但因其中通路，但因其中通路5+5=4+65+5=4+6，所以滿，所以滿足條件的不同距離的通路條數(shù)為足條件的不同距離的通路條數(shù)為5 5。算法說(shuō)明：本題采用窮舉算法。算法說(shuō)明：本題采用窮舉算法。數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)： N N：記錄記錄A A，B B間路站的個(gè)數(shù)間路站的個(gè)數(shù)數(shù)組數(shù)組DIDI，00記錄第記錄第I-1I-1到第到第I I路站間路段的個(gè)數(shù)路站間路段的個(gè)數(shù)DIDI，11，DIDI，22，記錄每個(gè)路段距離記錄每個(gè)路段距離數(shù)組數(shù)組G G記錄可取到的距離記錄可取到的距離程序清單：程序清單： PROGRAM CHU7_6；V

19、AR I，J，N，S：INTEGER； B：ARRAY0.100OF INTEGER； D：ARRAY0.100，0.20 OF INTEGER； G ：ARRAY0.1000 OF 0.1；BEGINREADLN(N)；FOR I:=1 TO N+1 DOBEGINREADLN(DI，0)；FOR J:=1 TO DI，0DO READLN(DI，J)；END；D0，0:=1；FOR I:=1 TO N+1 DO BI:=1；B0:=0；FOR I:=0 TO 1000 DO GI:=0；WHILEDOBEGINS:=0；FOR I:=1 TO N+1 DO S:=GS:=1；J:=N+1；

20、WHILE DO J:=J-1；BJ:=BJ+1；FOR I:=J+1 TO N+1 DO BI:=1；END； S:=0； FOR I:=1 TO 1000 DO；WRITELN(S)；READLN；END. B0=0 ;S+DI,BI ;BJ=DJ,0 ;S:=S+GI ;補(bǔ)充：補(bǔ)充： 1、求子串位置。從鍵盤輸入兩個(gè)字符串、求子串位置。從鍵盤輸入兩個(gè)字符串x1,x2，要求查要求查找出找出x2在在x1字符串中的位置（起始位置）。字符串中的位置（起始位置）。算法說(shuō)明：算法說(shuō)明： （1）用兩個(gè)變量分別表示輸入的字符串，并求出兩個(gè)字）用兩個(gè)變量分別表示輸入的字符串，并求出兩個(gè)字符串的長(zhǎng)度。符串的長(zhǎng)

21、度。 （2）利用）利用I,j變量作為掃描兩個(gè)字符串的指針變量作為掃描兩個(gè)字符串的指針 （3）掃描兩個(gè)字符串，當(dāng)其相等時(shí)，將指針指向下一個(gè)）掃描兩個(gè)字符串，當(dāng)其相等時(shí)，將指針指向下一個(gè)字符，字符， 當(dāng)當(dāng)j的值大于的值大于 len2,則輸出則輸出x2在在x1中的位置中的位置 （4）若子串位置不匹配，則使）若子串位置不匹配，則使I的指針回溯，的指針回溯，j指針重新指針重新指向子串的第一個(gè)字符。指向子串的第一個(gè)字符。program exp4_1; var x1,x2 :string; i, j, len1, len2, ps :integer ; function pos1( r1,r2 : stri

22、ng; L1,L2:integer) :integer ; var i,j : integer ; begin i:=1; j:=1 ; while (i=L1) and (jL2 then else ; end; begin readln(x1); readln(x2); writeln(x1) ; writeln(x2); len1:= ; len2:= ; ps:=pos1(x1,x2,len1,len2); writeln(ps:5); end.(3)I:=I+1 ;(4)J:=J+1 ;(5)I:=I-J+2 ;(6)J:=1 ; (7) POS1:=I-(J-1) ;(8) POS

23、1:=0 ;2.問(wèn)題描述問(wèn)題描述:將將n個(gè)整數(shù)分成個(gè)整數(shù)分成k組組(kn,要求每組不能為空要求每組不能為空),顯顯然這然這k個(gè)部分均可得到一個(gè)各自的和個(gè)部分均可得到一個(gè)各自的和s1,s2,sk,定義整數(shù)定義整數(shù)P為為:P=(S1-S2)2+(S1-S3)2+(S1-Sk)2+(s2-s3)2+(Sk-1-Sk)2問(wèn)題求解問(wèn)題求解:求出一種分法求出一種分法,使使P為最小為最小(若有多種方案僅記一若有多種方案僅記一種種程序說(shuō)明程序說(shuō)明:數(shù)組數(shù)組:a1,a2,.AN存放原數(shù)存放原數(shù)s1,s2,.,sK存放每個(gè)部分的和存放每個(gè)部分的和b1,b2,.,bN窮舉用臨時(shí)空間窮舉用臨時(shí)空間d1,d2,.,dN

24、存放最佳方案存放最佳方案程序程序:program exp4;Var i,j,n,k : integer;a :array 1.100 of integer;b,d:array 0.100 of integer;s :array1.30 of integer;begin readln(n,k);for I:=1 to n do read(aI);for I:=0 to n do bI:=1;cmin:=1000000;while (b0=1) dobegin for I:=1 to k do for I:=1 to n do sum:=0;For I:=1 to k-1 dofor j:= su

25、m:=sum+(sI-sj)*(sI-sj); if then begincmin:=sum;for I:=1 to n do dI:=bI; (1) SI：=0; (2) SbI：=sbi+aI; (3) I+1 to k do (4) (cmin sum ) (5) bj=k (6) bI：=1;end;j:=n;while do j:=j-1;bj:=bj+1;for I:=j+1 to n do end;writeln(cmin);for I:=1 to n do write(dI:40);writeln;end.3. 3. 問(wèn)題描述問(wèn)題描述: :工廠在每天的生產(chǎn)中工廠在每天的生產(chǎn)中,

26、 ,需要一定數(shù)量的零件需要一定數(shù)量的零件, ,同時(shí)也可以知道每天生產(chǎn)一個(gè)零件的生產(chǎn)單價(jià)。在同時(shí)也可以知道每天生產(chǎn)一個(gè)零件的生產(chǎn)單價(jià)。在N N天的天的生產(chǎn)中生產(chǎn)中, ,當(dāng)天生產(chǎn)的零件可以滿足當(dāng)天的需要當(dāng)天生產(chǎn)的零件可以滿足當(dāng)天的需要, ,若當(dāng)天用不若當(dāng)天用不完完, ,可以放到下一天去使用可以放到下一天去使用, ,但要收取每個(gè)零件的保管費(fèi)但要收取每個(gè)零件的保管費(fèi), ,不同的天收取的費(fèi)用也不相同。不同的天收取的費(fèi)用也不相同。問(wèn)題求解問(wèn)題求解: :求得一個(gè)求得一個(gè)N N天的生產(chǎn)計(jì)劃天的生產(chǎn)計(jì)劃( (即即N N天中每天應(yīng)生產(chǎn)零天中每天應(yīng)生產(chǎn)零件個(gè)數(shù)件個(gè)數(shù)),),使總的費(fèi)用最少。使總的費(fèi)用最少。輸入輸入:

27、 :N(N(天數(shù)天數(shù)N=29)N=29)每天的需求量每天的需求量( (N N個(gè)整數(shù)個(gè)整數(shù)) )每天生產(chǎn)零件的單價(jià)每天生產(chǎn)零件的單價(jià)( (N N個(gè)整數(shù)個(gè)整數(shù)) )每天保管零件的單價(jià)每天保管零件的單價(jià)( (N N個(gè)整數(shù)個(gè)整數(shù)) )輸出輸出: :每天的生產(chǎn)零件個(gè)數(shù)每天的生產(chǎn)零件個(gè)數(shù)( (N N個(gè)整數(shù)個(gè)整數(shù)) )例如例如:當(dāng)當(dāng)N=3時(shí)時(shí),其需要量與費(fèi)用如下其需要量與費(fèi)用如下:第一天第一天第二天第二天第三天第三天需要量需要量252515153030生產(chǎn)單價(jià)生產(chǎn)單價(jià)202030303232保管單價(jià)保管單價(jià)5 5l0l00 0生產(chǎn)計(jì)劃的安排可以有許多方案生產(chǎn)計(jì)劃的安排可以有許多方案, ,如下面的三種如下面的

28、三種: :第一天第一天第二天第二天第三天第三天總的費(fèi)用總的費(fèi)用2525151530302525* *2 2O+15O+15* *30+3030+30* *32=191032=191040400 030304040* *20+1520+15* *5+305+30* *32=183532=183570700 00 07070* *20+4520+45* *5+305+30* *10=192510=1925程序說(shuō)明程序說(shuō)明: :bn:bn:存放每天的需求量存放每天的需求量, , cn:cn:每天生產(chǎn)零件的單價(jià)每天生產(chǎn)零件的單價(jià)dn:dn:每天保管零件的單價(jià)每天保管零件的單價(jià) , , en:en:生產(chǎn)

29、計(jì)劃生產(chǎn)計(jì)劃程序程序: :Program exp5;Program exp5;VarVari,j,n,yu,j0,j1,s:integer;i,j,n,yu,j0,j1,s:integer;b,c,d,e: array0.30of integer;b,c,d,e: array0.30of integer;beginbeginreadln(n);readln(n);for i:=1 to n do readln(bi,cI,di; fori:=1 to n do ei:=0; :=10000; cn+2:=0; bn+1:=0;j0:=1;While (j0=n) dobeginyu:=cj0;

30、 j1:=j0; s:=bj0;while dobegin j1:=j1+1; s:=s+bj1; end; j0:=j1+1;end;For i:=1 to n do readln; end. 1、 cn+12、 (yu+dj1cj1+1)3、 yu:=yu+dj1;4、 ej0:=s;5、 write(eI:4); 4. 4.問(wèn)題描述問(wèn)題描述: :有有n n種基本物質(zhì)種基本物質(zhì)( (n10),n10),分別記為分別記為P1,P2,Pn,P1,P2,Pn,用用n n種基本物質(zhì)構(gòu)造物品種基本物質(zhì)構(gòu)造物品, ,這些物品使用在這些物品使用在k k個(gè)不同地區(qū)個(gè)不同地區(qū)( (k20),k20),每個(gè)地

31、區(qū)對(duì)物品提出自己的要求每個(gè)地區(qū)對(duì)物品提出自己的要求, ,這這些要求用一個(gè)些要求用一個(gè)n n位的數(shù)表示位的數(shù)表示: :1 12 2n,n,其中其中: : ai=1 ai=1表示所需物質(zhì)中必須有第表示所需物質(zhì)中必須有第i i種基本物質(zhì)種基本物質(zhì) = -1 = -1表示所需物質(zhì)中必須不能有第表示所需物質(zhì)中必須不能有第i i種基本物質(zhì)種基本物質(zhì)r r =0 =0無(wú)所謂無(wú)所謂問(wèn)題求解問(wèn)題求解:當(dāng)當(dāng)k個(gè)不同地區(qū)要求給出之后個(gè)不同地區(qū)要求給出之后,給出一種方案給出一種方案,指指出哪些物質(zhì)被使用出哪些物質(zhì)被使用,哪些物質(zhì)不被使用。哪些物質(zhì)不被使用。 程序說(shuō)明程序說(shuō)明: :數(shù)組數(shù)組b1,b2,.,bnJb1,b

32、2,.,bnJ表示某種物品表示某種物品a1.k,1.na1.k,1.n記錄記錄k k個(gè)地區(qū)對(duì)物品的要求個(gè)地區(qū)對(duì)物品的要求, ,其中其中: :aI,j=1aI,j=1表示第表示第i i個(gè)地區(qū)對(duì)第個(gè)地區(qū)對(duì)第j j種物品是需要的種物品是需要的ai,j=0ai,j=0表示第表示第i i個(gè)地區(qū)對(duì)第個(gè)地區(qū)對(duì)第j j種物品是無(wú)所謂的種物品是無(wú)所謂的ai,j=-1ai,j=-1表示第表示第i i個(gè)地區(qū)對(duì)第個(gè)地區(qū)對(duì)第j j種物品是不需要的種物品是不需要的程序程序: :program gxp2;program gxp2;Var i, j ,k, n :integer;Var i, j ,k, n :integer

33、;p:boolean;p:boolean;b : array 0.20 of 0.1; b : array 0.20 of 0.1; a : array1.20,1.10d integer; beginreadln(n,k);for i:=1 to k do beginfor j:=1 to n do read(ai,j);readln; end;for i:=0 to n do bi:=0;p:=true; while do begin j:=n; while bj=1 do j:=j-1; (1) P AND (B0=0)(2) BJ：=1；(3) P：=FALSE；(4)(AI，J=1）

34、AND（BJ=1）(5) Pfor i:=j+1 to n do bI:=0;for i:=1 to k do for j :=1 to n do If ( ai,j=1 ) and (bj=0) or then p:=true;end; if then writeln(找不到找不到!) else for i:=1 to n do if (bi=1) then writeln(物質(zhì)物質(zhì),I,需要需要) else writeln(物質(zhì)物質(zhì),i,不需要不需要);end. 10.10.存儲(chǔ)空間的回收算法。設(shè)在內(nèi)存中已經(jīng)存放了若干存儲(chǔ)空間的回收算法。設(shè)在內(nèi)存中已經(jīng)存放了若干個(gè)作業(yè)個(gè)作業(yè)A A，B B，

35、C C，D D。其余的空間為可用的其余的空間為可用的( (如圖一中如圖一中( (a)a)。此時(shí)，可用空間可用一個(gè)二維數(shù)組此時(shí)，可用空間可用一個(gè)二維數(shù)組dk1.100dk1.100，1.2 1.2 表示，表示，( (如下表一中如下表一中( (a)a)，其中：其中：dkidki，11對(duì)應(yīng)第對(duì)應(yīng)第i i個(gè)可用個(gè)可用空間首址，空間首址，dkidki，22對(duì)應(yīng)第對(duì)應(yīng)第i i個(gè)可用空間長(zhǎng)度如上圖中，個(gè)可用空間長(zhǎng)度如上圖中，dkdk：現(xiàn)某個(gè)作業(yè)釋放一個(gè)區(qū)域，其首址為現(xiàn)某個(gè)作業(yè)釋放一個(gè)區(qū)域，其首址為d d，長(zhǎng)度為長(zhǎng)度為L(zhǎng) L，此時(shí)將釋放區(qū)此時(shí)將釋放區(qū)域加入到可用空間表中。要求在加入時(shí)，若可用空間相鄰時(shí)，則必域

36、加入到可用空間表中。要求在加入時(shí)，若可用空間相鄰時(shí)，則必須進(jìn)行合并。因此出現(xiàn)下面的須進(jìn)行合并。因此出現(xiàn)下面的4 4種情況種情況( (如上圖一如上圖一( (b)b)所示所示) )。(1)(1)下靠，即回收區(qū)域和下面可用空間相鄰，例如，下靠，即回收區(qū)域和下面可用空間相鄰，例如，d=80d=80，L=20L=20，此時(shí)成為表二中的此時(shí)成為表二中的( (a)a)。(2)上靠，例如，上靠，例如，d=600，L=50，此時(shí)表成為表二中的此時(shí)表成為表二中的(b)。 100 100 50 50 300 300 100 100 50 50 100 100 0 0 0 0 100 100 50 50 300 30

37、0 100 100 500 500 100 100 10000 10000 0 0 表一表一( (a) a) 表一表一( (b) b) (3)(3)上、下靠，例如，上、下靠，例如，d=150d=150，L=150L=150，此時(shí)表成為表二中的此時(shí)表成為表二中的( (c)c)。(4)(4)上、下不靠，例如，上、下不靠，例如，d=430d=430，L=20L=20，此時(shí)表成為表二中的此時(shí)表成為表二中的( (d)d)。80807070300300100100505010010010010050503003001001005005001501501001003003005005001001001001

38、0050503003001001004304302020500500100100表二表二( (a)(a)(下靠下靠) ) 表二表二( (b)(b)(上上靠靠) ) 表二表二( (c)(c)(上，上，下靠下靠) ) 表二表二( (d)(d)(上，上，下不靠下不靠) ) 程序說(shuō)明：對(duì)數(shù)組程序說(shuō)明：對(duì)數(shù)組dk預(yù)置預(yù)置2個(gè)標(biāo)志，即頭和尾標(biāo)志，成為表二中個(gè)標(biāo)志，即頭和尾標(biāo)志，成為表二中(b)，這樣可使算法簡(jiǎn)單，這樣可使算法簡(jiǎn)單，sp為為dk表末地址。表末地址。 PROGRAM GAO7_5；VAR I，J，SP，D，L：INTEGER；DK ：ARRAY0.100，1.2 OF INTEGER；BEGI

39、NREADLN(SP)；FOR I:=1 TO SP DO READLN(DKI，1，DKI，2)；DK0，1:=0；DK0，2:=0；DKSP，1:=10000；DKSP，2:=0；READLN(D，L)；I:=1；WHILE DKI，1D DO I:=I+1；IF (DKI，1+DKI，2=D) THENIF (D+L=DKI+1，1) THENBEGINDKI，2:=；FOR J:=I+1 TO SP-1 DODKJ:=DKJ+1；SP：=SP-1； END ELSE DKI，2:=DKI，2+L ELSE IF(D+L=DKI+1，1) THENBEGINDKI+1，1:=；DKI+1，2:=DKI+1，2+L;END ELSE BEGIN FOR J:=SP DOWNTO I+1 DO DKJ+1:=DKJ； :=D； DKI+1，2:=L；SP:=SP+1；END；FOR I:=1 TO SP-1 DO WRITELN(DKI，1:4，DKI，2:4)； READLN；END. SP SP：=SP+1=SP+1 I I：=I -1=I -1 DKI DKI，2+L+DKI+12+L+DKI+1，22 D D DKI+1 DKI+1，1111.11.求關(guān)