完善程序奥赛复习ppt课件

1、完善程序及算法分析完善程序及算法分析l算法复习算法复习l完善程序解题方法完善程序解题方法l运用举例运用举例完善程序题解题方法完善程序题解题方法一、完善程序题解题步骤：一、完善程序题解题步骤：1、仔细阅读文字解释，了解题意和提供的解题思绪、仔细阅读文字解释，了解题意和提供的解题思绪2、根据问题的求解要求，了解输入、输出内容和问、根据问题的求解要求，了解输入、输出内容和问题处置方法题处置方法3、先阅读主程序，了解输出变量和输出要求以及主、先阅读主程序，了解输出变量和输出要求以及主程序中需求调用的过程或函数是哪些。程序中需求调用的过程或函数是哪些。4、阅读过程或函数，了解其完成的功能、阅读过程或函数

2、，了解其完成的功能5、填空方法：普通从主程序最后输出要求，反推主、填空方法：普通从主程序最后输出要求，反推主程序中的变量填写或表达式、语句等的书写程序中的变量填写或表达式、语句等的书写6、根据主程序参数与子程序参数传送关系，填写子程序、根据主程序参数与子程序参数传送关系，填写子程序的变量，根据子程序需求完成的功能，完成子程序填空的变量，根据子程序需求完成的功能，完成子程序填空7、填写终了，再将程序整个阅读、执行一遍，看能否完、填写终了，再将程序整个阅读、执行一遍，看能否完成问题提出的要求。成问题提出的要求。二、例题解答二、例题解答: 1.坐标统计输入坐标统计输入n个整点在平面上的坐标。对于每个

3、整点在平面上的坐标。对于每个点，可以控制一切位于它左下方的点即个点，可以控制一切位于它左下方的点即x、y坐标都坐标都比它小，它可以控制的点的数目称为比它小，它可以控制的点的数目称为“战斗力。依次战斗力。依次输出每个点的战斗力，最后输出战斗力最高的点的编号输出每个点的战斗力，最后输出战斗力最高的点的编号假设假设干个点的战斗力并列最高，输出其中最大的假设假设干个点的战斗力并列最高，输出其中最大的编号。编号。读题，读题， Const SIZE= 100; Var X, y, f:array1.SIZE of integer; N,i,j,max_f,ans: integer; Begin readl

4、n(n); For i:=1 to n do Readln (xi,yi); Max_f :=0; For i:=1 to n do Begin fi:= ； For j:= 1 to n do Begin if (xj xi) and ( ) then ; End; 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 2. 陈列数输入两个正整数陈列数输入两个正整数n，m1n20,1mn，在，在1n中任取中任取

5、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; Begin readln(n,m); fillchar (used,sizeof(used), false); 只能置0、Truefor i:=1 to m

6、 do begin datai:=i; usedi:= true; end; flag:= true; While flag do begin for i:= 1 to m-1 do write(datai, ); writeln(datam); 第一次最小的 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; if flag then begin for k:=i+1 t

7、o 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 3.笛卡尔树 对于一个给定的两两不等的正整数序列，笛卡尔树是这样的一棵二叉树：首先，它是一个最小堆，即除了根结点外，每个结点的权值都大于父节点的权值；其次，它的中序遍历恰好就是给定的序列。例如，对于序列7、2、12、1、10、5、15、3，以下图就是一棵对应的笛卡尔树。 现输入

8、序列的规模n1n maxDeep then begin maxDeep := deep; num := 1; end else if deep = maxDeep then ; 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) ; end; begin readln(n); for i :=

9、 1 to n do read(ai); maxDeep := 0; solve(1, n, 1); writeln(maxDeep, , num); end. solve(j + 1, right, deep + 1) 4. 4. 将将2 n 2 n 个个0 0和和2 n2 n个个1 1，排成一圈。从任一个位置开，排成一圈。从任一个位置开场，每次按逆时针的方向以长度为场，每次按逆时针的方向以长度为n+1n+1的数二进制数。的数二进制数。要求给出一种排法，用上面的方法产生出来的要求给出一种排法，用上面的方法产生出来的2 n+12 n+1个二进制数都不一样。当个二进制数都不一样。当n=2n=2时

10、，即有时，即有2 2 2 2 个个0 0和和2222个个1 1陈列如右下：陈列如右下：比如，从比如，从A A位置开场，逆时针方向取三个数位置开场，逆时针方向取三个数000000，然后，然后再从再从B B位置上开场取三个数位置上开场取三个数001001，接着取，接着取010010可以可以得到得到000000，001001，010010，101101，011011，111111，110110共共8 8个二进个二进制数，并且都不一样。程序阐明：以制数，并且都不一样。程序阐明：以N=4N=4为例，即有为例，即有1616个个0 0、1616个个1 1，数组，数组A A用以记录用以记录3232个个0 0、

11、1 1的排法，数的排法，数组组B B统计二进制数能否已出现过。统计二进制数能否已出现过。此题利用二进制加法运算的原理。此题利用二进制加法运算的原理。A数组存放每位二进制数，数组存放每位二进制数，B数组用于判别所产生的数组用于判别所产生的数能否反复为了减少循环次数，程序中将最后五位置数能否反复为了减少循环次数，程序中将最后五位置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 ；

12、 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+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 WRITEAJ； WRIT

13、ELN ；END. AJ:=1 ;AI:=0 ;S:=0 ;BS:=1 ;S=32进制的了解与运用进制的了解与运用5、初中，问题：、初中，问题： 多项式乘法运算：多项式乘法运算：P(X)=2X2- x +1，q(x)=x+1 p(x)*q(x)=(2x2x+1)*(x+1)=2x3 + X2-+1 阐明：多项式的表示：系数、指数阐明：多项式的表示：系数、指数如上例中如上例中PX系数系数 指数指数 QX 系数系数 指数指数 2 2 1 1 -1 1 1 0 1 0 0 0 0 0P * Q 的结果存入的结果存入C中。其输出格式是：依次用一对中。其输出格式是：依次用一对括号内的系数、指数分别来表示

14、。如上例的输出括号内的系数、指数分别来表示。如上例的输出结果表示为：结果表示为：2，31，21，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 ;BEGIN JP: = 0 ; READLN (X,Y) ; WHILE X 0 DO BEGIN JP:=JP+1 ; PJP,1:= X ; PJP,2 :=Y ; READLN(X,Y)

15、; 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 THEN ELSE BEGIN FOR L：=JC DOWNTO K DO BEGIN CL+

16、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 归并算法思想归并算法思想 6、 在在A，B两个城市之间设有两个城市之间设有N个路站个路站(如以下图如以下图中的中的S1，且，且N sum ) (5) bj=k (6) bI：=1;运用进制方法搜索运用进制方法搜索8 8

17、、工厂在每天的消费中、工厂在每天的消费中, ,需求一定数量的零件需求一定数量的零件, ,同时同时也可以知道每天消费一个零件的消费单价。在也可以知道每天消费一个零件的消费单价。在N N天的天的消费中消费中, ,当天消费的零件可以满足当天的需求当天消费的零件可以满足当天的需求, ,假设当假设当天用不完天用不完, ,可以放到下一天去运用可以放到下一天去运用, ,但要收取每个零件但要收取每个零件的保管费的保管费, ,不同的天收取的费用也不一样。不同的天收取的费用也不一样。问题求解问题求解: :求得一个求得一个N N天的消费方案天的消费方案( (即即N N天中每天应消天中每天应消费零件个数费零件个数),

18、),使总的费用最少。穷举算法使总的费用最少。穷举算法输入输入:N(:N(天数天数N=29)N=29)每天的需求量每天的需求量(N(N个整数个整数) )每天消费零件的单价每天消费零件的单价(N(N个整数个整数) )每天保管零件的单价每天保管零件的单价(N(N个整数个整数) )输出输出: :每天的消费零件个数每天的消费零件个数(N(N个整数个整数) )例如例如: :当当N=3N=3时时, ,其需求量与费用如下其需求量与费用如下: : 第一天第一天第二天第二天第三天第三天需求量需求量252515153030消费单价消费单价202030303232保管单价保管单价5 5l0l00 0消费方案的安排可以

19、有许多方案消费方案的安排可以有许多方案, ,如下面的三种如下面的三种: :第一天第一天第二天第二天第三天第三天总的费用总的费用2525151530302525* *2O+152O+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:

20、每天保管零件的单价每天保管零件的单价 , en: , en:消费方案消费方案程序程序: :Program exp5;Program exp5;Var i,j,n, yu , j0, j1, s:integer;Var i,j,n, yu , j0, j1, s:integer; b,c,d,e: array0.30 of integer; b,c,d,e: array0.30 of integer;beginbegin readln(n); readln(n); for i:=1 to n do readln( bi, cI, for i:=1 to n do readln( bi, cI,

21、di ) ; di ) ; 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 dobegin 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, );9、问题描画、问题描画:有有n种根本物质种根本物质(n10),分别

22、记为分别记为P1,P2,Pn,用用n种种根本物质构造物品根本物质构造物品,这些物品运用在这些物品运用在k个不同地域个不同地域(k20),每个地域对每个地域对物品提出本人的要求物品提出本人的要求,这些要求用一个这些要求用一个n位的数表示位的数表示:12n,其其中中:i =1表示所需物质中必需有第表示所需物质中必需有第i种根本物质种根本物质=-1表示所需物质中必需不能有第表示所需物质中必需不能有第i种根本物质种根本物质r=0无所谓无所谓问题求解问题求解:当当k个不同地域要求给出之后个不同地域要求给出之后,给出一种方案给出一种方案,指出哪些物指出哪些物质被运用质被运用,哪些物质不被运用。哪些物质不被

23、运用。程序阐明程序阐明:数组数组b1,b2,.,bnJ表示某种物品表示某种物品a1.k,1.n记录记录k个地域对物品的要求个地域对物品的要求,其中其中:aI,j=1表示第表示第i个地域对第个地域对第j种物品是需求的种物品是需求的ai,j=0表示第表示第i个地域对第个地域对第j种物品是无所谓的种物品是无所谓的ai,j=-1表示第表示第i个地域对第个地域对第j种物品是不需求的种物品是不需求的Program gxp2; Var i, j ,k, n :integer; p:boolean; b :array 0.20 of 0.1; a :array1.20,1.10d integer; begin

24、 readln(n,k); for i:=1 to k do begin for j:=1 to n do read(ai,j); readln;end;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 do bI:=0; (3) P and (b0=0) bj:=1 ; p:=false ;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

25、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 10、回形陈列、回形陈列 (5个空个空, 每空每空2分共分共10分分) 【问题描画】【问题描画】 ：给出一个：给出一个N(1N20,得到一个得到一个N*N的回形陈列方阵。的回形陈列方阵。例如：当例如：当 N=5 时，得到的回形陈列方时，得到的回形陈列方阵为：阵为：1 2 3 4 516 17 18 19 61

26、5 24 25 20 714 23 22 21 813 12 11 10 9输入输入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; ； for i:=1 to n1 do begin for j:=i to n-i do begin ； k:=k+1; en

27、d; for j:=i to n-I do begin k:=k+1; end; 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,j:4); writeln; end; end. 回形矩阵回形矩阵(1) K:=1;(2) aI,j:=k ;(3) aj,n-

28、i+1:=k ;(4) an-i+1,j:=k ;(5) odd(n) 数字阵列数字阵列,坐标与元素之间的关系坐标与元素之间的关系 11子矩阵输入一个n1*m1的矩阵a，和n2*m2的矩阵b，问a中能否存在子矩阵和b相等。假设存在，输出一切子矩阵左上角的坐标；假设不存在输出“There is no answerConst SIZE = 50; var n1, m1, n2, m2, i, j, k1, k2 : integer; a, b : array1.SIZE, 1.SIZE of integer; good, haveAns : boolean; begin readln(n1, m1

29、); for i := 1 to n1 do for j := 1 to m1 do read(aij); readln(n2, m2); for i := 1 to n2 do 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, j + k2 - 1 bk1, k2 then good := false; if good then begin write

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

31、te(count, : , n, = , s1 ) ; for k:=2 to I do write( + , sk ) ; writeln ; end ;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:= I-1 ; Sum := (4) ;(1) Sum=n (2) J(3) Sum-sI ;(4) Sum-sI;回溯算法运用回溯算

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

33、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,+); writeln(ak); try(ak,i,k+1) end; end;begin readln(n); try(n,1,1)end. 13、选陈列下面程序的功能是利用递归方法生成从1到n(n10)的n个数中取k(1=k=n)个数的全部能够的陈列不一定按升序输出。例如，当n=3，k=2时，应该输出每行输出5个陈列： 12 13 21 23 32

34、31 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; for do write(ap:1); write( ); t:=ak;ak:=ai;ai:=t; if (count mod 5=0) then writeln; end; exit; end;

35、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. 1313、选陈列、选陈列 j=k 或k=j p:=1 to k perm2(j+1) aj:=ai;ai:=t perm2(1)回溯算法的运用14大整数开方输入一个正整数大整数开方输入一个正整数n1n 0 then ans.len := a.len + b.len else ans.len := a.l

36、en + b.len - 1; end; times := ans; end; 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 := ; ans.numi + 1 := ans.numi + 1

37、+ ans.numi div 10; ans.numi := ans.numi mod 10; end; If ans.numans.len + 1 0 then inc(ans.len); add := ans; end; 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 ans.numans.len = 0 then dec(ans.len); avera