完善程序奥赛复习.ppt

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;,5,If then Begin max_f:= fi; ; End; End; For i:= 1 to n do Writeln(fi); Writeln(ans); End.,(1) 0 (2) yj=max_f; (5) ans:=i,6,2. （排列数）输入两个正整数n，m（1n20,1mn），在1n中任取m个数，按字典序从小到大输出所有这样的排列。例如：输入：3 2 （算法未必是传统的）输出: 1 2 1 3 2 1 2 3 3 1 3 2 const S

4、IZE=25; var used: array1. SIZE of boolean; data: array1. SIZE or integer; n,m,i,j,k : integer; flag: boolean;,7,Begin readln(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, ); wr

5、iteln(datam); 第一次最小的,8,flag:= ; for i:=m downto 1 do begin ; for j:= datai+1 to n do if usedj= false then begin usedj:= true; 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

6、.,(1) false (2) useddatai:=flase (3) j (4) n (5) break,10,3.笛卡尔树 对于一个给定的两两不等的正整数序列，笛卡尔树是这样的一棵二叉树：首先，它是一个最小堆，即除了根结点外，每个结点的权值都大于父节点的权值；其次，它的中序遍历恰好就是给定的序列。例如，对于序列7、2、12、1、10、5、15、3，下图就是一棵对应的笛卡尔树。 现输入序列的规模n（1n100）和序列的n个元素，试求其对应的笛卡尔树的深度d（根节点深度为1），以及有多少个叶节点的深度为d。,11,Const SIZE = 100; INFINITY = 1000000; v

7、ar n , maxDeep, num, i : integer; a : array1.SIZE of integer; Procedure solve(left, right, deep : integer); var i, j, min : 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 :

8、= 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; 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，排成一圈。从任一个位置开始，每次按逆时针的方

9、向以长度为n+1的数二进制数。要求给出一种排法，用上面的方法产生出来的 2 n+1个二进制数都不相同。当n=2时，即有2 2 个0和22个1排列如右下：,15,比如，从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，前面五位置

10、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：= 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

11、 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 DO 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）系

12、数 指数 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） 程序清单： 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)

13、 ; 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 JQ:=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

14、,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 ; 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个

15、路站(如下图中的S1，且N100)，城市与路站之间、路站和路站之间各有若干条路段(各路段数20，且每条路段上的距离均为一个整数)。,26,A，B的一条通路是指：从A出发，可经过任一路段到达S1，再从S1出发经过任一路段，最后到达B。通路上路段距离之和称为通路距离(最大距离1000)。当所有的路段距离给出之后，求出所有不同距离的通路个数(相同距离仅记一次)。 例如：下图所示是当N=1时的情况：,27,从A到B的通路条数为6，但因其中通路5+5=4+6，所以满足条件的不同距离的通路条数为5。 算法说明：本题采用穷举算法。 数据结构： N：记录A，B间路站的个数 数组DI，0记录第I-1到第I路站间

16、路段个数 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:=1 TO N+1 DOBEGINREADLN(DI，0)；FOR J:=1 TO DI，0 DO READLN(DI，J)；END；D0，0:=1；FOR I:=1 TO N+1 DO BI:=1；B0:=0；FOR I:=0 TO 1

17、000 DO GI:=0；WHILEDO,30,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 ; 穷举算法的应用,31,7、2002问题描述:将n个整数分成k组(kn,要求每组不能为空),显然这k个部分均可得到一个各自的和s1,s2,sk,定义整数P为: P=(S1-S2)2

18、+(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存放最佳方案 程序:,32,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

19、 do read(aI); for I:=0 to n do bI:=1; cmin:=1000000; while (b0=1) do,33,begin for I:=1 to k do for I:=1 to n do sum:=0; For I:=1 to k-1 do for j:= sum:=sum+(sI-sj)*(sI-sj); if then begin cmin:=sum; for I:=1 to n do dI:=bI;,34,end; j:=n; while do j:=j-1; bj:=bj+1; for I:= j+1 to n do end; writeln(cmi

20、n); for I:=1 to n do write(dI:4); writeln; end.,(1) SI：=0; (2) SbI：=sbi+aI; (3) I+1 to k do (4) (cmin sum ) (5) bj=k (6) bI：=1; 应用进制方法搜索,35,8、工厂在每天的生产中,需要一定数量的零件,同时也可以知道每天生产一个零件的生产单价。在N天的生产中,当天生产的零件可以满足当天的需要,若当天用不完,可以放到下一天去使用,但要收取每个零件的保管费,不同的天收取的费用也不相同。 问题求解:求得一个N天的生产计划(即N天中每天应生产零件个数),使总的费用最少。（穷举算法）

21、 输入:N(天数N=29) 每天的需求量(N个整数) 每天生产零件的单价(N个整数) 每天保管零件的单价(N个整数),36,输出:每天的生产零件个数(N个整数) 例如:当N=3时,其需要量与费用如下:,生产计划的安排可以有许多方案,如下面的三种:,37,程序说明: bn:存放每天的需求量, cn:每天生产零件的单价 dn:每天保管零件的单价 , en:生产计划 程序: Program exp5; Var i,j,n, yu , j0, j1, s:integer; b,c,d,e: array0.30 of integer; begin readln(n); for i:=1 to n do

22、readln( bi, cI, di ) ;,38,For i:=1 to n do ei:=0; :=10000; cn+2:=0; bn+1:=0;j0:=1; While (j0=n) do begin yu:=cj0; j1:=j0; s:=bj0; while do begin j1:=j1+1; s:=s+bj1; end; j0:=j1+1; end; For i:=1 to n do readln; end.,(1) cn+1 (2) (yu+dj1)(cj1+1) (3) yu:=yu+dj1; (4) ej0:=s; (5) write(eI, );,39,9、问题描述:有

23、n种基本物质(n10),分别记为P1,P2,Pn,用n种基本物质构造物品,这些物品使用在k个不同地区(k20),每个地区对物品提出自己的要求,这些要求用一个n位的数表示:12n,其中: i =1表示所需物质中必须有第i种基本物质 =-1表示所需物质中必须不能有第i种基本物质r =0无所谓 问题求解:当k个不同地区要求给出之后,给出一种方案,指出哪些物质被使用,哪些物质不被使用。 程序说明:数组b1,b2,.,bnJ表示某种物品 a1.k,1.n记录k个地区对物品的要求,其中: aI,j=1表示第i个地区对第j种物品是需要的 ai,j=0表示第i个地区对第j种物品是无所谓的 ai,j=-1表示第

24、i个地区对第j种物品是不需要的,40,Program gxp2; Var i, j ,k, n :integer; p:boolean; b :array 0.20 of 0.1; a :array1.20,1.10d integer; begin readln(n,k); for i:=1 to k do begin for j:=1 to n do read(ai,j); readln; end;,41,for i:=0 to n d o bi:=0; p:=true; while do begin j:=n; while bj=1 do j:=j-1; for i:=j+1 to n d

25、o bI:=0; (3),P and (b0=0) bj:=1 ; p:=false ;,42,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.,(4) ( aI,j=-1) and ( bj=1 ) (5) p,43,10、回形排列 (5个空, 每空2分共10分) 【问题描

26、述】 ：给出一个N(（1N20）,得到一个N*N的回形排列方阵。,例如：当 N=5 时，得到的回形排列方阵为： 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9,44,输入N，输出N*N的方阵 【程序说明】 A：ARRAY1.20,1.20 OF INTEGER; 存放填入的数 K: INTEGER; 每次填入的数; program cup_7; var i,j,k,n,n1:integer; a:array1.20,1.20 of integer; begin readln(n); n1:=n div 2; ；

27、 for i:=1 to n1 do begin for j:=i to n-i do begin ； k:=k+1; end; for j:=i to n-I do begin k:=k+1; end;,45,for j:=n-i+1 downto i+1 do begin ； k:=k+1; end; for j:=n-i+1 downto i+1 do begin aj,i:=k; k:=k+1; end; end; if then a(n+1) div 2, (n+1) div 2:=k; for i:=1 to n do begin for j:=1 to n do write(ai

28、,j:4); writeln; end; end.,46,回形矩阵,(1) K:=1; (2) aI,j:=k ; (3) aj,n-i+1:=k ; (4) an-i+1,j:=k ; (5) odd(n) 数字阵列,坐标与元素之间的关系,47,11（子矩阵）输入一个n1*m1的矩阵a，和n2*m2的矩阵b，问a中是否存在子矩阵和b相等。若存在，输出所有子矩阵左上角的坐标；若不存在输出“There is no answer” Const SIZE = 50; var n1, m1, n2, m2, i, j, k1, k2 : integer; a, b : array1.SIZE, 1.S

29、IZE of integer; good, haveAns : boolean; begin readln(n1, m1); for i := 1 to n1 do for j := 1 to m1 do read(aij); readln(n2, m2); for i := 1 to n2 do,48,For j := 1 to m2 do ; haveAns := false; For i := 1 to n1 - n2 + 1 do For j := 1 to do begin ; for k1 := 1 to n2 do for k2 := 1 to do if ai + k1 1,

30、j + k2 - 1 bk1, k2 then good := false;,49,if good then begin writeln(i, , j); ; end; end; if not haveAns then writeln(There is no answer); end., read(bij) m1 - m2 + 1 good := true m2 haveAns := true,50,12、自然数拆分： program p_11 ; const m=100 ; var s: array1.m of 0.m ; n , I , j ,sum , count : integer ;

31、 procedure print ; var k: integr ; begin count := count+1 ; write(count, : , n, = , s1 ) ; for k:=2 to I do write( + , sk ) ; writeln ; end ;,51,begin readln(n) ; I:=1; sum :=0 ; j:=0 ; count:=0 ; Repeat J:=j+1 ; Sum:=sum+j ; If (1) then Begin SI:= (2) ; If sum = n then Begin Print ; Sum := (3) ; I:

32、= I-1 ; Sum := (4) ;,(1) Sum=n (2) J (3) Sum-sI ; (4) Sum-sI; 回溯算法应用,52,J:=si ; end End Else begin I:=I+1 ; j:= sI-1-1 ; end Else begin Sum := (5) ; I:= (6) ; sum:= (7) ; J:=sI ; end ; Until i=0 End.,(5) Sum-j (6) I-1 (7) Sum-sI,53,自然数拆分比较好的算法： program p1_5(input,output); Var a,b:array 1.100 of byte

33、; n:integer; procedure try(m, start, k:integer); var i,j:integer; begin for i:=start to (m div 2) do begin ak:=m-i; bk:=i; for j:=1 to k do write(bj,+);,54,writeln(ak); try(ak,i,k+1) end; end; begin readln(n); try(n,1,1) end.,55,13、（选排列）下面程序的功能是利用递归方法生成从1到n(n10)的n个数中取k(1=k=n)个数的全部可能的排列（不一定按升序输出）。例如，

34、当n=3，k=2时，应该输出（每行输出5个排列）： 12 13 21 23 32 31,56,Program ex501; Var i,n,k:integer; a:array1.10 of integer; count:longint; Procedure perm2(j:integer); var i,p,t: integer; begin if then begin for i:=k to n do begin inc(count); t:=ak; ak:=ai; ai:=t;,57,for do write(ap:1); write( ); t:=ak;ak:=ai;ai:=t; if

35、 (count mod 5=0) then writeln; end; exit; end;,58,for i:=j to n do begin t:=aj;aj:=ai;ai:=t; ; t:=aj; ; end end; begin writeln(Entry n,k (k=n):); read(n,k); count:=0; for i:=1 to n do ai:=i; ; end.,59,13、选排列, j=k （或k=j） p:=1 to k perm2(j+1) aj:=ai;ai:=t perm2(1) 回溯算法的应用,60,14（大整数开方）输入一个正整数n（1n10100）

36、，试用二分法计算它的平方根的整数部分。 const SIZE = 200; type hugeint = record len : integer; num : array1.SIZE of integer; end; / len表示大整数的位数；num1表示个位、num2表示十位，以此类推 var s : string; i : integer; target, left, middle, right : hugeint;,61,Function times(a, b : hugeint) : hugeint; /计算a和b积 var i, j : integer; ans : hugein

37、t; begin fillchar(ans, sizeof(ans), 0); for i := 1 to a.len do for j := 1 to b.len do := ans.numi + j - 1 + a.numi * b.numj; for i := 1 to a.len + b.len do begin ans.numi + 1 := ans.numi + 1 + ans.numi div 10; ; if ans.numa.len + b.len 0 then ans.len := a.len + b.len else ans.len := a.len + b.len -

38、1; end; times := ans; end;,62,function add(a, b : hugeint) : hugeint; /计算a和b的和 var i : integer; ans : hugeint; begin fillchar(ans.num, sizeof(ans.num), 0); if a.len b.len then ans.len := a.len else ans.len := b.len; For i := 1 to ans.len do begin ans.numi := ;,63,ans.numi + 1 := ans.numi + 1 + ans.n

39、umi div 10; ans.numi := ans.numi mod 10; end; If ans.numans.len + 1 0 then inc(ans.len); add := ans; end;,64,Function average(a, b : hugeint) : hugeint; /计算大整数a和b的平均数的整数部分 var i : integer; ans : hugeint; begin ans := add(a, b); for i := ans.len downto 2 do begin ans.numi - 1 := ans.numi - 1 + ( ) * 10; ans.numi := ans.numi div 2; end; ans.num1 := ans.num1 div 2; if a