信息技术奥林匹克竞赛复习纲要

1、完善程序题解题方法完善程序题解题方法一、完善程序题解题步骤：一、完善程序题解题步骤：1、仔细阅读文字解释，理解题意和提供的解题思路、仔细阅读文字解释，理解题意和提供的解题思路2、根据问题的求解要求，了解输入、输出内容和问题处、根据问题的求解要求，了解输入、输出内容和问题处理方法理方法3、先阅读主程序，了解输出变量和输出要求以及主程序、先阅读主程序，了解输出变量和输出要求以及主程序中需要调用的过程或函数是哪些。中需要调用的过程或函数是哪些。4、阅读过程或函数，了解其完成的功能、阅读过程或函数，了解其完成的功能5、填空方法：一般从主程序最后输出要求，反推主程序、填空方法：一般从主程序最后输出要求，

2、反推主程序中的变量填写或表达式、语句等的书写中的变量填写或表达式、语句等的书写6、根据主程序参数与子程序参数传递关系，填写子程序、根据主程序参数与子程序参数传递关系，填写子程序的变量，根据子程序需要完成的功能，完成子程序填空的变量，根据子程序需要完成的功能，完成子程序填空7、填写完毕，再将程序整个阅读、执行一遍，看能否完、填写完毕，再将程序整个阅读、执行一遍，看能否完成问题提出的要求。成问题提出的要求。二、运用求解二、运用求解 1 、找出小于、找出小于33的的6个正整数，用这些整数进行加法运算，个正整数，用这些整数进行加法运算，使得包括原来的整数在内能组成尽可能多的不同整数。使得包括原来的整数

3、在内能组成尽可能多的不同整数。 例如：用例如：用2，3，5可以组成可以组成5，7，8，10再加再加2，3可以组成可以组成6个不同的数。个不同的数。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年问题（初中）：年问题（初中）：将将2 2 n n 个个0 0和和

4、2 2 n n个个1 1，排成一圈。从任一个位置开始，排成一圈。从任一个位置开始，每次按逆时针的方向以长度为每次按逆时针的方向以长度为n+1n+1的单位进行数二进制的单位进行数二进制数。要求给出一种排法，用上面的方法产生出来的数。要求给出一种排法，用上面的方法产生出来的2 2 n+1n+1个二进制数都不相同。当个二进制数都不相同。当n=2n=2时，即有时，即有2 2 2 2 个个0 0和和2 22 2个个1 1排列如右下：排列如右下：比如，从比如，从A A位置开始，逆时针方向取三个数位置开始，逆时针方向取三个数000000，然后再从，然后再从B B位置上开始取三个数位置上开始取三个数00100

5、1，接着取，接着取010010可以得到可以得到000000，001001，010010，101101，011011，111111，110110共共8 8个二进制数，并且都个二进制数，并且都不相同。不相同。程序说明：以程序说明：以N=4N=4为例，即有为例，即有1616个个0 0、1616个个1 1，数组，数组A A用以记用以记录录3232个个0 0、1 1的排法，数组的排法，数组B B统计二进制数是否已出现过。统计二进制数是否已出现过。本题利用二进制加法运算的原理。本题利用二进制加法运算的原理。A数组存放每位二进制数，数组存放每位二进制数，B数组用于判断所产生的数是数组用于判断所产生的数是否重

6、复否重复为了减少循环次数，程序中将最后五位置为了减少循环次数，程序中将最后五位置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初中，问题：初中，问题： 多项式乘法运算：多项式乘法运算：P（X）=2X2- x +1，q（x）=x+1 p（x）*q（x）=（2x2x+1）*（x+1）

8、=2x3 + X2-+1 说明：说明：多项式的表示：系数、指数多项式的表示：系数、指数如上例中：如上例中：P（X）：）： 系数系数 指数指数 Q（X） 系数系数 指数指数 2 2 1 1 -1 1 1 0 1 0 0 0 0 0P * Q 的结果存入的结果存入C中。其输出格式是：依次用一对括号中。其输出格式是：依次用一对括号内的（系数、指数）分别来表示。如上例的输出结果表示内的（系数、指数）分别来表示。如上例的输出结果表示为：（为：（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年年 高中问题高中问题1 求一棵树的深度和宽度。例如有如下的一棵树：树的深求一棵树的深度和宽度。例如有如下的一棵树：树的深度为从根结点开始到叶结点结束的最大深度，树的宽度为度为从根结点开始到叶结点结束的最大深度，树的宽度为同一层上结点数的最大值。在左图中树的深度为同一层上结点数的最大值。在左图中树的深度为4，宽度，宽度为为3。用邻接表来表示树，见如下表（一）用邻接表来表示树，见如下表（一）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个个0 0到到100100之间的整数，由小到大排序输出，每之间的整数，由小到大排序输出，每行输出行输出8 8个个程序清单：程序清单：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两个城市之间设有两个城市之间设有N个路站个路站(如下图中的如下图中的S1，且且N100)，城市与路站之间、

17、路站和路站之城市与路站之间、路站和路站之间各有若干条路段间各有若干条路段(各路段数各路段数20，且每条路段上的，且每条路段上的距离均为一个整数距离均为一个整数)。 A，B的一条通路是指：从的一条通路是指：从A出发，可经过任一路出发，可经过任一路段到达段到达S1，再从再从S1出发经过任一路段，出发经过任一路段，最后到达最后到达B。通路上路段距离之和称为通路距离通路上路段距离之和称为通路距离(最大距离最大距离1000)。当。当所有的路段距离给出之后，求出所有不同距离的通路个所有的路段距离给出之后，求出所有不同距离的通路个数数(相同距离仅记一次相同距离仅记一次)。例如：下图所示是当例如：下图所示是当

18、N=1时的情况：时的情况：从从A A到到B B的通路条数为的通路条数为6 6，但因其中通路，但因其中通路5+5=4+65+5=4+6，所以满，所以满足条件的不同距离的通路条数为足条件的不同距离的通路条数为5 5。算法说明：本题采用穷举算法。算法说明：本题采用穷举算法。数据结构：数据结构： N N：记录记录A A，B B间路站的个数间路站的个数数组数组DIDI，00记录第记录第I-1I-1到第到第I I路站间路段的个数路站间路段的个数DIDI，11，DIDI，22，记录每个路段距离记录每个路段距离数组数组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 ;补充：补充： 1、求子串位置。从键盘输入两个字符串、求子串位置。从键盘输入两个字符串x1,x2，要求查要求查找出找出x2在在x1字符串中的位置（起始位置）。字符串中的位置（起始位置）。算法说明：算法说明： （1）用两个变量分别表示输入的字符串，并求出两个字）用两个变量分别表示输入的字符串，并求出两个字符串的长度。符串的长

21、度。 （2）利用）利用I,j变量作为扫描两个字符串的指针变量作为扫描两个字符串的指针 （3）扫描两个字符串，当其相等时，将指针指向下一个）扫描两个字符串，当其相等时，将指针指向下一个字符，字符， 当当j的值大于的值大于 len2,则输出则输出x2在在x1中的位置中的位置 （4）若子串位置不匹配，则使）若子串位置不匹配，则使I的指针回溯，的指针回溯，j指针重新指针重新指向子串的第一个字符。指向子串的第一个字符。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.问题描述问题描述:将将n个整数分成个整数分成k组组(kn,要求每组不能为空要求每组不能为空),显显然这然这k个部分均可得到一个各自的和个部分均可得到一个各自的和s1,s2,sk,定义整数定义整数P为为:P=(S1-S2)2+(S1-S3)2+(S1-Sk)2+(s2-s3)2+(Sk-1-Sk)2问题求解问题求解:求出一种分法求出一种分法,使使P为最小为最小(若有多种方案仅记一若有多种方案仅记一种种程序说明程序说明:数组数组:a1,a2,.AN存放原数存放原数s1,s2,.,sK存放每个部分的和存放每个部分的和b1,b2,.,bN穷举用临时空间穷举用临时空间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. 问题描述问题描述: :工厂在每天的生产中工厂在每天的生产中,

26、 ,需要一定数量的零件需要一定数量的零件, ,同时也可以知道每天生产一个零件的生产单价。在同时也可以知道每天生产一个零件的生产单价。在N N天的天的生产中生产中, ,当天生产的零件可以满足当天的需要当天生产的零件可以满足当天的需要, ,若当天用不若当天用不完完, ,可以放到下一天去使用可以放到下一天去使用, ,但要收取每个零件的保管费但要收取每个零件的保管费, ,不同的天收取的费用也不相同。不同的天收取的费用也不相同。问题求解问题求解: :求得一个求得一个N N天的生产计划天的生产计划( (即即N N天中每天应生产零天中每天应生产零件个数件个数),),使总的费用最少。使总的费用最少。输入输入:

27、 :N(N(天数天数N=29)N=29)每天的需求量每天的需求量( (N N个整数个整数) )每天生产零件的单价每天生产零件的单价( (N N个整数个整数) )每天保管零件的单价每天保管零件的单价( (N N个整数个整数) )输出输出: :每天的生产零件个数每天的生产零件个数( (N N个整数个整数) )例如例如:当当N=3时时,其需要量与费用如下其需要量与费用如下:第一天第一天第二天第二天第三天第三天需要量需要量252515153030生产单价生产单价202030303232保管单价保管单价5 5l0l00 0生产计划的安排可以有许多方案生产计划的安排可以有许多方案, ,如下面的三种如下面的

28、三种: :第一天第一天第二天第二天第三天第三天总的费用总的费用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程序说明程序说明: :bn:bn:存放每天的需求量存放每天的需求量, , cn:cn:每天生产零件的单价每天生产零件的单价dn:dn:每天保管零件的单价每天保管零件的单价 , , en:en:生产

29、计划生产计划程序程序: :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.问题描述问题描述: :有有n n种基本物质种基本物质( (n10),n10),分别记为分别记为P1,P2,Pn,P1,P2,Pn,用用n n种基本物质构造物品种基本物质构造物品, ,这些物品使用在这些物品使用在k k个不同地区个不同地区( (k20),k20),每个地

31、区对物品提出自己的要求每个地区对物品提出自己的要求, ,这这些要求用一个些要求用一个n n位的数表示位的数表示: :1 12 2n,n,其中其中: : ai=1 ai=1表示所需物质中必须有第表示所需物质中必须有第i i种基本物质种基本物质 = -1 = -1表示所需物质中必须不能有第表示所需物质中必须不能有第i i种基本物质种基本物质r r =0 =0无所谓无所谓问题求解问题求解:当当k个不同地区要求给出之后个不同地区要求给出之后,给出一种方案给出一种方案,指指出哪些物质被使用出哪些物质被使用,哪些物质不被使用。哪些物质不被使用。 程序说明程序说明: :数组数组b1,b2,.,bnJb1,b

32、2,.,bnJ表示某种物品表示某种物品a1.k,1.na1.k,1.n记录记录k k个地区对物品的要求个地区对物品的要求, ,其中其中: :aI,j=1aI,j=1表示第表示第i i个地区对第个地区对第j j种物品是需要的种物品是需要的ai,j=0ai,j=0表示第表示第i i个地区对第个地区对第j j种物品是无所谓的种物品是无所谓的ai,j=-1ai,j=-1表示第表示第i i个地区对第个地区对第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(物质物质,I,需要需要) else writeln(物质物质,i,不需要不需要);end. 10.10.存储空间的回收算法。设在内存中已经存放了若干存储空间的回收算法。设在内存中已经存放了若干个作业个作业A A，B B，

35、C C，D D。其余的空间为可用的其余的空间为可用的( (如图一中如图一中( (a)a)。此时，可用空间可用一个二维数组此时，可用空间可用一个二维数组dk1.100dk1.100，1.2 1.2 表示，表示，( (如下表一中如下表一中( (a)a)，其中：其中：dkidki，11对应第对应第i i个可用个可用空间首址，空间首址，dkidki，22对应第对应第i i个可用空间长度如上图中，个可用空间长度如上图中，dkdk：现某个作业释放一个区域，其首址为现某个作业释放一个区域，其首址为d d，长度为长度为L L，此时将释放区此时将释放区域加入到可用空间表中。要求在加入时，若可用空间相邻时，则必域

36、加入到可用空间表中。要求在加入时，若可用空间相邻时，则必须进行合并。因此出现下面的须进行合并。因此出现下面的4 4种情况种情况( (如上图一如上图一( (b)b)所示所示) )。(1)(1)下靠，即回收区域和下面可用空间相邻，例如，下靠，即回收区域和下面可用空间相邻，例如，d=80d=80，L=20L=20，此时成为表二中的此时成为表二中的( (a)a)。(2)上靠，例如，上靠，例如，d=600，L=50，此时表成为表二中的此时表成为表二中的(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，此时表成为表二中的此时表成为表二中的( (c)c)。(4)(4)上、下不靠，例如，上、下不靠，例如，d=430d=430，L=20L=20，此时表成为表二中的此时表成为表二中的( (d)d)。80807070300300100100505010010010010050503003001001005005001501501001003003005005001001001001

38、0050503003001001004304302020500500100100表二表二( (a)(a)(下靠下靠) ) 表二表二( (b)(b)(上上靠靠) ) 表二表二( (c)(c)(上，上，下靠下靠) ) 表二表二( (d)(d)(上，上，下不靠下不靠) ) 程序说明：对数组程序说明：对数组dk预置预置2个标志，即头和尾标志，成为表二中个标志，即头和尾标志，成为表二中(b)，这样可使算法简单，这样可使算法简单，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.求关