《完善程序奥赛复习2013讲解学习》由会员分享，可在线阅读，更多相关《完善程序奥赛复习2013讲解学习（70页珍藏版）》请在金锄头文库上搜索。
1、1,完善程序及算法分析,算法复习 完善程序解题方法 应用举例,2,完善程序题解题方法 一、完善程序题解题步骤： 1、仔细阅读文字解释，理解题意和提供的解题思路 2、根据问题的求解要求，了解输入、输出内容和问题处理方法 3、先阅读主程序，了解输出变量和输出要求以及主程序中需要调用的过程或函数是哪些。 4、阅读过程或函数，了解其完成的功能 5、填空方法：一般从主程序最后输出要求，反推主程序中的变量填写或表达式、语句等的书写,3,6、根据主程序参数与子程序参数传递关系，填写子程序的变量，根据子程序需要完成的功能，完成子程序填空 7、填写完毕，再将程序整个阅读、执行一遍，看能否完成问题提出的要求。 二
2、、例题解答: 1.（坐标统计）输入n个整点在平面上的坐标。对于每个点，可以控制所有位于它左下方的点（即x、y坐标都比它小），它可以控制的点的数目称为“战斗力”。依次输出每个点的战斗力，最后输出战斗力最高的点的编号（如果若干个点的战斗力并列最高，输出其中最大的编号）。 读题，,4,Const SIZE= 100; Var X, y, f:array1.SIZE of integer; N,i,j,max_f,ans: integer; Begin readln(n); For i:=1 to n do Readln (xi,yi); Max_f :=0; For i:=1 to n do Beg
3、in fi:= ； For j:= 1 to n do Begin if (xj xi) and ( ) then ; End;,6,2. （排列数）输入两个正整数n，m（1n20,1mn），在1n中任取m个数，按字典序从小到大输出所有这样的排列。例如：输入：3 2 （算法未必是传统的）输出: 1 2 1 3 2 1 2 3 3 1 3 2 const SIZE=25; var used: array1. SIZE of boolean; data: array1. SIZE or integer; n,m,i,j,k : integer; flag: boolean;,7,Begin rea
4、dln(n,m); fillchar (used,sizeof(used), false); 只能置0、Truefor i:=1 to m do begin datai:=i; usedi:= true; end; flag:= true; While flag do begin for i:= 1 to m-1 do write(datai, ); writeln(datam); 第一次最小的,8,flag:= ; for i:=m downto 1 do begin ; for j:= datai+1 to n do if usedj= false then begin usedj:= t
5、rue; datai:= ; flag:= true; Break; end;,9,if flag then begin for k:=i+1 to m do for j:=1 to do if usedj= false then begin datak:= j; usedj:= true; Break; end; ; end; end; end; end.,(1) false (2) useddatai:=flase (3) j (4) n (5) break,10,3.笛卡尔树 对于一个给定的两两不等的正整数序列，笛卡尔树是这样的一棵二叉树：首先，它是一个最小堆，即除了根结点外，每个结点的
6、权值都大于父节点的权值；其次，它的中序遍历恰好就是给定的序列。例如，对于序列7、2、12、1、10、5、15、3，下图就是一棵对应的笛卡尔树。 现输入序列的规模n（1n100）和序列的n个元素，试求其对应的笛卡尔树的深度d（根节点深度为1），以及有多少个叶节点的深度为d。,11,Const SIZE = 100; INFINITY = 1000000; var n , maxDeep, num, i : integer; a : array1.SIZE of integer; Procedure solve(left, right, deep : integer); var i, j, min
7、 : integer; begin if deep maxDeep then begin maxDeep := deep; num := 1; end else if deep = maxDeep then,12, ; min := INFINITY; For i := left to right do if min ai then begin min := ai; ; end; if left j then ; if j right then, inc(num) (或num := num + 1) j := i solve(left, j - 1, deep + 1),13, ; end;
8、begin readln(n); for i := 1 to n do read(ai); maxDeep := 0; solve(1, n, 1); writeln(maxDeep, , num); end., solve(j + 1, right, deep + 1),14,4. 将2 n 个0和2 n个1，排成一圈。从任一个位置开始，每次按逆时针的方向以长度为n+1的数二进制数。要求给出一种排法，用上面的方法产生出来的 2 n+1个二进制数都不相同。当n=2时，即有2 2 个0和22个1排列如右下：,15,比如，从A位置开始，逆时针方向取三个数000，然后再从B位置上开始取三个数001，
9、接着取010可以得到000，001，010，101，011，111，110共8个二进制数，并且都不相同。程序说明：以N=4为例，即有16个0、16个1，数组A用以记录32个0、1的排法，数组B统计二进制数是否已出现过。,本题利用二进制加法运算的原理。 A数组存放每位二进制数，B数组用于判断所产生的数是否重复为了减少循环次数，程序中将最后五位置1，前面五位置0,16,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
10、：= 0 ； FOR I：=28 TO 32 DO AI：= 1 ； P：=1； A6：=1； WHILE （P=1） DO BEGIN J：=27；,17,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+4 DO S:=S*2+AK ; END； S：=0 ；,18,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 D
11、O WRITE（AJ）； WRITELN ； END.,AJ:=1 ; AI:=0 ; S:=0 ; BS:=1 ; S=32 进制的理解与应用,19,5、初中，问题： 多项式乘法运算：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 2 1 1 -1 1 1 0 1 0 0 0 0 0,20,P * Q 的结果存入C中。其输出格式是：依次用一对括号内的（系数、指数）分别来表示。如上例的输出结果表示为：（2，3）（1，2）（1，0） 程序
12、清单： 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 ;,21,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 ;,22,READLN(X,Y) ; WHILE X0 DO BEGIN J
13、Q:=JQ+1 ; QJQ,1 :=X ; QJQ,2:=Y ; READLN(X,Y) ; END; JC:=1; CJC,1:= 0; CJC,2:= -1000 ;,23,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,24,FOR L：=JC DOWNTO K DO BEGIN CL+1,1:=CL，1 ; CL+1,2:=CL，2 ; END; CK,1:=X1 ;
14、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 归并算法思想,25,6、 在A，B两个城市之间设有N个路站(如下图中的S1，且N100)，城市与路站之间、路站和路站之间各有若干条路段(各路段数20，且每条路段上的距离均为一个整数)。,26,A，B的一条通路是指：从A出发，可经过任一路段到达S1，再从S1出发经过任一路段，最后到达B。通路上路段
15、距离之和称为通路距离(最大距离1000)。当所有的路段距离给出之后，求出所有不同距离的通路个数(相同距离仅记一次)。 例如：下图所示是当N=1时的情况：,27,从A到B的通路条数为6，但因其中通路5+5=4+6，所以满足条件的不同距离的通路条数为5。 算法说明：本题采用穷举算法。 数据结构： N：记录A，B间路站的个数 数组DI，0记录第I-1到第I路站间路段个数 DI，1，DI，2，记录每个路段距离数组G记录可取到的距离,28,程序清单： 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；,29,BEGINREADLN(N)；FOR I
