《高中信息学奥林匹克竞赛复习五》由会员分享，可在线阅读，更多相关《高中信息学奥林匹克竞赛复习五（55页珍藏版）》请在金锄头文库上搜索。
1、完善程序题解题方法 一、完善程序题解题步骤： 1、仔细阅读文字解释，理解题意和提供的解题思路 2、根据问题的求解要求，了解输入、输出内容和问题处理方法 3、先阅读主程序，了解输出变量和输出要求以及主程序中需要调用的过程或函数是哪些。 4、阅读过程或函数，了解其完成的功能 5、填空方法：一般从主程序最后输出要求，反推主程序中的变量填写或表达式、语句等的书写,6、根据主程序参数与子程序参数传递关系，填写子程序的变量，根据子程序需要完成的功能，完成子程序填空 7、填写完毕，再将程序整个阅读、执行一遍，看能否完成问题提出的要求。 二、运用求解 1 、找出小于33的6个正整数，用这些整数进行加法运算，使
2、得包括原来的整数在内能组成尽可能多的不同整数。 例如：用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+aI,2、2000年问题（初中）： 将2 n 个0和2 n个1，排成一圈。从任一个位置开始，每次按逆时针的方向
3、以长度为n+1的单位进行数二进制数。要求给出一种排法，用上面的方法产生出来的2 n+1个二进制数都不相同。当n=2时，即有2 2 个0和22个1排列如右下：,比如，从A位置开始，逆时针方向取三个数000，然后再从B位置上开始取三个数001，接着取010可以得到000，001，010，101，011，111，110共8个二进制数，并且都不相同。 程序说明：以N=4为例，即有16个0、16个1，数组A用以记录32个0、1的排法，数组B统计二进制数是否已出现过。,本题利用二进制加法运算的原理。 A数组存放每位二进制数，B数组用于判断所产生的数是否重复 为了减少循环次数，程序中将最后五位置1，前面五位
4、置0,PROGRAM 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 31 DO BI：=0； FOR I：=1 TO 32 DO begin FOR K：=I TO I
5、+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）=2x3 + X2-+1 说明： 多项式的表示：系数、指数 如上例中：P（X）： 系数 指数 Q（X） 系数 指数 2
6、2 1 1 -1 1 1 0 1 0 0 0 0 0,P * Q 的结果存入C中。其输出格式是：依次用一对括号内的（系数、指数）分别来表示。如上例的输出结果表示为：（2，3）（1，2）（1，0） 2程序清单： PROGRAM NO100_7 ; VAR I, J , K , L , JP , JQ , JC , 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 J
7、P:=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,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
8、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; FOR I:=1 TO JC DO IF THEN WRITE （ (,CI,1 , , ,C I,2 , )）； READLN ; END.,X:= PI,1 ; X1:=X*QJ,1; CK,1:=CK,1+X1 ; JC:=JC+1 ; CI,10,2000年 高中问题1 求一棵树的深度和宽度。例如有如下的一棵树：树的深度为从根结点开始到叶结点结束的最大深度，树的
9、宽度为同一层上结点数的最大值。在左图中树的深度为4，宽度为3。 用邻接表来表示树，见如下表（一）,program 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
10、; Tree1,2:=2 ; tree1,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 +
11、1 ; qsp2 ,0 := l; qsp2 , 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.,SP10 ; (4) (QSP2,0) L ; (5) DQI,0 +1 ;,2001年 初
12、中 1、输入n个0到100之间的整数，由小到大排序输出，每行输出8个程序清单：PROGRAM CHU7_5；VAR I，J，K，N，X：INTEGER；B：ARRAY0.100OF INTEGER； BEGINREADLN(N)；FOR I:=0 TO 100 DO BI:=0；,FOR I:=1 TO N DO BEGINREADLN(X)；BX:=END； FOR I:=0 TO 100 DO WHILEDOBEGINWRITE()；K:=K+1；BI:=BI-1；IFTHEN WRITELNEND；READLNEND.,(1) BX:=BX+1; (2) K:=0 ; (3) BI0 (
13、4) I: 4 ; (5) K MOD 8=0,2000年 高中2. 在A，B两个城市之间设有N个路站(如下图中的S1，且N100)，城市与路站之间、路站和路站之间各有若干条路段(各路段数20，且每条路段上的距离均为一个整数)。,A，B的一条通路是指：从A出发，可经过任一路段到达S1，再从S1出发经过任一路段，最后到达B。通路上路段距离之和称为通路距离(最大距离1000)。当所有的路段距离给出之后，求出所有不同距离的通路个数(相同距离仅记一次)。 例如：下图所示是当N=1时的情况：,从A到B的通路条数为6，但因其中通路5+5=4+6，所以满足条件的不同距离的通路条数为5。 算法说明：本题采用穷
14、举算法。 数据结构： N：记录A，B间路站的个数数组DI，0记录第I-1到第I路站间路段的个数DI，1，DI，2，记录每个路段距离数组G记录可取到的距离,程序清单： PROGRAM CHU7_6；VAR 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
15、TO N+1 DO BI:=1；B0:=0；FOR I:=0 TO 1000 DO GI:=0；WHILEDO,BEGINS:=0；FOR I:=1 TO N+1 DOS:=GS:=1；J:=N+1；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）用两个变量分别表示输入的字符串，并求出两个字符串的长度。 （2）利用I,j变量作为扫描两个字符串的指针 （3）扫描两个字符串，当其相等时，将指针指向下一个字符， 当j的值大于 len2,则输出x2在x1中的位置 （4）若子串位置不匹配，则使I的指针回溯，j指针重新指向子串的第一个字符
