《完善程序奥赛复习2013》由会员分享，可在线阅读，更多相关《完善程序奥赛复习2013（70页珍藏版）》请在金锄头文库上搜索。
1、完善程序奥赛复习2013Stillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望2完善程序题解题方法完善程序题解题方法一、完善程序题解题步骤：一、完善程序题解题步骤：1、仔细阅读文字解释，理解题意和提供的解题思路、仔细阅读文字解释，理解题意和提供的解题思路2、根据问题的求解要求，了解输入、输出内容和问、根据问题的求解要求，了解输入、输出内容和问题处理方法题处理方法3、先阅读主程序，了解输出变量和输出要求以及主、先阅读主程序，了解输出变量和输出要求以及主程序中需要调用的过程或函数是哪些。程序中
2、需要调用的过程或函数是哪些。4、阅读过程或函数，了解其完成的功能、阅读过程或函数，了解其完成的功能5、填空方法：一般从主程序最后输出要求，反推主、填空方法：一般从主程序最后输出要求，反推主程序中的变量填写或表达式、语句等的书写程序中的变量填写或表达式、语句等的书写36、根据主程序参数与子程序参数传递关系，填写子程序、根据主程序参数与子程序参数传递关系，填写子程序的变量，根据子程序需要完成的功能，完成子程序填空的变量，根据子程序需要完成的功能，完成子程序填空7、填写完毕，再将程序整个阅读、执行一遍，看能否完、填写完毕，再将程序整个阅读、执行一遍，看能否完成问题提出的要求。成问题提出的要求。二、例
3、题解答二、例题解答: 1.（坐标统计）输入（坐标统计）输入n个整点在平面上的坐标。对于每个整点在平面上的坐标。对于每个点，可以控制所有位于它左下方的点（即个点，可以控制所有位于它左下方的点（即x、y坐标都坐标都比它小），它可以控制的点的数目称为比它小），它可以控制的点的数目称为“战斗力战斗力”。依。依次输出每个点的战斗力，最后输出战斗力最高的点的编次输出每个点的战斗力，最后输出战斗力最高的点的编号（如果若干个点的战斗力并列最高，输出其中最大的号（如果若干个点的战斗力并列最高，输出其中最大的编号）。编号）。读题，读题， 4 Const SIZE= 100; Var X, y, f:array1.
4、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 Begin 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、5) ans:=i 62. （排列数）输入两个正整数（排列数）输入两个正整数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; 7Begin readl
6、n(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:= true
7、; 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) break10 3.笛卡尔树笛卡尔树 对于一个给定的两两不等的正整数序列，笛卡尔树是这样对于一个给定的两两不等的正整数序列，笛卡尔树是这样的一棵二叉树
8、：首先，它是一个最小堆，即除了根结点外，的一棵二叉树：首先，它是一个最小堆，即除了根结点外，每个结点的权值都大于父节点的权值；其次，它的中序遍历每个结点的权值都大于父节点的权值；其次，它的中序遍历恰好就是给定的序列。例如，对于序列恰好就是给定的序列。例如，对于序列7、2、12、1、10、5、15、3，下图就是一棵对应的笛卡尔树。，下图就是一棵对应的笛卡尔树。 现输入序列的规模现输入序列的规模n（1n maxDeep then begin maxDeep := deep; num := 1; end else if deep = maxDeep then 12 ; min := INFINITY
9、; 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; 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, d
10、eep + 1)14 4. 4. 将将2 2 n n 个个0 0和和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排列如右下：排列如右下：15比比如如，从从A A位位置置开开始始，逆逆时时针针方方向向取取三三个个数数000000，然然后后再再从从B B位位置
11、置上上开开始始取取三三个个数数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、1 1的的排排法法，数数组组B B统统计二进制数是否已出现过。计二进制数是否已出现过。本题利用二进制加法运算的原理。本题利用二进制加法运算的原理。A数组存放每位二进制数，数组存放每位二进制数，B数组用于判断所产生的数数组
12、用于判断所产生的数是否重复为了减少循环次数，程序中将最后五位置是否重复为了减少循环次数，程序中将最后五位置1，前面五位置，前面五位置016PROGRAMNO100；VARA：ARRAY1.36OF0.1；B：ARRAY0.31OFINTEGER；I，J，K，S，P：INTEGER；BEGINFORI：=1TO36DOAI：=0；FORI：=28TO32DOAI：=1；P：=1；A6：=1；WHILE（P=1）DOBEGINJ：=27；17WHILEAJ=1DOJ：=J1；FORI：=J+1TO27DOFORI：=0TO31DOBI：=0；FORI：=1TO32DObeginFORK:=ITOI
13、+4DOS:=S*2+AK;END；S：=0； 18 FORI：=0TO31DOS：=S+BI；IFTHENP：=0；END；FORI：=1TO32DOFORJ：=ITOI+4DOWRITE（AJ）；）；WRITELN；END.(1)AJ:=1;(2)AI:=0;(3)S:=0;(4)BS:=1;(5)S=32进制的理解与应用进制的理解与应用195、初中，问题：、初中，问题：多项式乘法运算：多项式乘法运算：P(X)=2X2-x+1，q(x)=x+1p(x)*q(x)=(2x2x+1)*(x+1)=2x3+X2-+1说明：多项式的表示：系数、指数说明：多项式的表示：系数、指数如上例中如上例中P（
14、X）系数系数指数指数Q（X）系数系数指数指数2211-111010000020P*Q的的结结果果存存入入C中中。其其输输出出格格式式是是：依依次次用用一一对对括括号号内内的的（系系数数、指指数数）分分别别来来表表示示。如如上上例例的的输输出出结果表示为：（结果表示为：（2，3）（）（1，2）（）（1，0）程序清单：程序清单：PROGRAMNO100_7;VARI,J,K,L,JP,JQ,JC,X,Y,X1,Y1:INTEGER;P,Q:ARRAY1.10,1.2OFINTEGER;C:ARRAY1.20,1.2OFINTEGER;21BEGINJP:=0;READLN(X,Y);WHILEX0
15、DOBEGINJP:=JP+1;PJP,1:=X;PJP,2:=Y;READLN(X,Y);END;JQ:=0; 22 READLN(X,Y);WHILEX0DOBEGINJQ:=JQ+1;QJQ,1:=X;QJQ,2:=Y;READLN(X,Y);END;JC:=1;CJC,1:=0;CJC,2:=-1000;23FORI:=1TOJPDOBEGIN Y：=PI,2;FORJ:=1TOJQDOBEGIN;Y1：=Y+QJ，2；K:=1;WHILEY1CK,2DOK:=K+1;IFY1=CK,2THENELSEBEGIN24FORL：=JCDOWNTOKDOBEGINCL+1,1:=CL，1;
16、CL+1,2:=CL，2;END;CK,1:=X1;CK,2:=Y1;END；END; END;END; FORI:=1TOJCDOIFTHENWRITE(,CI,1,CI,2,) )；READLN;END.(1)X:=PI,1;(2)X1:=X*QJ,1;(3)CK,1:=CK,1+X1;(4)JC:=JC+1;(5)CI,10归并算法思想归并算法思想256、在在A，B两个城市之间设有两个城市之间设有N个路站个路站(如下图如下图中的中的S1，且且Nsum)(5)bj=k(6)bI：=1;应用进制方法搜索应用进制方法搜索358 8、工工厂厂在在每每天天的的生生产产中中, ,需需要要一一定定数数
17、量量的的零零件件, ,同同时时也也可可以以知知道道每每天天生生产产一一个个零零件件的的生生产产单单价价。在在N N天天的的生生产产中中, ,当当天天生生产产的的零零件件可可以以满满足足当当天天的的需需要要, ,若若当当天天用用不不完完, ,可可以以放放到到下下一一天天去去使使用用, ,但但要要收收取取每每个个零零件件的的保管费保管费, ,不同的天收取的费用也不相同。不同的天收取的费用也不相同。问问题题求求解解: :求求得得一一个个N N天天的的生生产产计计划划( (即即N N天天中中每每天天应应生生产零件个数产零件个数),),使总的费用最少。使总的费用最少。（穷举算法）（穷举算法）输入输入:
18、:N(N(天数天数N=29)N=29)每天的需求量每天的需求量( (N N个整数个整数) )每天生产零件的单价每天生产零件的单价( (N N个整数个整数) )每天保管零件的单价每天保管零件的单价( (N N个整数个整数) )36输出输出: :每天的生产零件个数每天的生产零件个数( (N N个整数个整数) )例如例如:当当N=3时时,其需要量与费用如下其需要量与费用如下:第一天第一天第二天第二天第三天第三天需要量需要量252515153030生产单价生产单价202030303232保管单价保管单价5 5l0l00 0生产计划的安排可以有许多方案生产计划的安排可以有许多方案, ,如下面的三种如下面
19、的三种: :第一天第一天第二天第二天第三天第三天总的费用总的费用25251515303025*225*2O+15*30+30*32=1910O+15*30+30*32=191040400 0303040*20+15*5+30*32=183540*20+15*5+30*32=183570700 00 070*20+45*5+30*10=192570*20+45*5+30*10=192537程序说明程序说明: :bn:bn:存放每天的需求量存放每天的需求量, , cn:cn:每天生产零件的单价每天生产零件的单价dn:dn:每天保管零件的单价每天保管零件的单价 , , en:en:生产计划生产计划程
20、序程序: :Programexp5;Vari,j,n,yu,j0,j1,s:integer;b,c,d,e:array0.30ofinteger;beginreadln(n);fori:=1tondoreadln(bi,cI,di);38Fori:=1tondoei:=0;:=10000;cn+2:=0;bn+1:=0;j0:=1;While(j0=n)dobeginyu:=cj0;j1:=j0;s:=bj0;whiledobeginj1:=j1+1;s:=s+bj1;end;j0:=j1+1;end;Fori:=1tondoreadln;end.(1)cn+1(2)(yu+dj1)(cj1+
21、1)(3)yu:=yu+dj1;(4)ej0:=s;(5)write(eI,);399、问题描述、问题描述:有有n种基本物质种基本物质(n10),分别记为分别记为P1,P2,Pn,用用n种种基本物质构造物品基本物质构造物品,这些物品使用在这些物品使用在k个不同地区个不同地区(k20),每个地区对每个地区对物品提出自己的要求物品提出自己的要求,这些要求用一个这些要求用一个n位的数表示位的数表示:12n,其其中中:i =1表示所需物质中必须有第表示所需物质中必须有第i种基本物质种基本物质=-1表示所需物质中必须不能有第表示所需物质中必须不能有第i种基本物质种基本物质r=0无所谓无所谓问题求解问题求
22、解:当当k个不同地区要求给出之后个不同地区要求给出之后,给出一种方案给出一种方案,指出哪些物质指出哪些物质被使用被使用,哪些物质不被使用。哪些物质不被使用。程序说明程序说明:数组数组b1,b2,.,bnJ表示某种物品表示某种物品a1.k,1.n记录记录k个地区对物品的要求个地区对物品的要求,其中其中:aI,j=1表示第表示第i个地区对第个地区对第j种物品是需要的种物品是需要的ai,j=0表示第表示第i个地区对第个地区对第j种物品是无所谓的种物品是无所谓的ai,j=-1表示第表示第i个地区对第个地区对第j种物品是不需要的种物品是不需要的40Program gxp2; Var i, j ,k, n
23、 :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;41for 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)(1) P and (b0=0)(2) bj:=1 ;(3) p:=fals
24、e ;42for 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 4310、回形排列、回形排列 (5个空个空, 每空每空2分共分共10分分) 【问题描述问题描述】 ：给出一个：给出一个N(（1N2
25、0）,得到一个得到一个N*N的回形排列方阵。的回形排列方阵。例例如如：当当N=5时时，得得到到的的回回形形排排列列方方阵为：阵为：1234516171819615242520714232221813121110944输入输入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 di
26、v 2; ； 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 wri
27、te(ai,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 = 5
28、0; 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); for i := 1 to n1 do for j := 1 to m1 do read(aij); readln(n2, m2); for i := 1 to n2 do 48For j := 1 to m2 do ; haveAns := false; For i := 1 to n1 - n2 + 1 do For j :=
29、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; 49if 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 5012、自然数拆分：、自然数拆分：programp_11;cons
30、tm=100;vars:array1.mof0.m;n,I,j,sum,count:integer;procedureprint;vark:integr;begincount:=count+1;write(count,:,n,=,s1);fork:=2toIdowrite(+,sk);writeln;end;51beginreadln(n);I:=1;sum:=0;j:=0;count:=0;RepeatJ:=j+1;Sum:=sum+j;If(1)thenBeginSI:=(2);Ifsum=nthenBeginPrint;Sum:=(3);I:=I-1;Sum:=(4);(1)Sum=n(
31、2)J(3)Sum-sI;(4)Sum-sI;回溯算法应用回溯算法应用52J:=si;endEndElsebeginI:=I+1;j:=sI-1-1;endElsebeginSum:=(5);I:=(6);sum:=(7);J:=sI;end;Untili=0End.(5)Sum-j(6)I-1(7)Sum-sI53自然数拆分比较好的算法：自然数拆分比较好的算法：programp1_5(input,output);Vara,b:array1.100ofbyte;n:integer;proceduretry(m,start,k:integer);vari,j:integer;beginfori:
32、=startto(mdiv2)dobeginak:=m-i;bk:=i;forj:=1tokdowrite(bj,+);54writeln(ak);try(ak,i,k+1)end;end;beginreadln(n);try(n,1,1)end.55 13、（选排列）下面程序的功能是利用递归方法、（选排列）下面程序的功能是利用递归方法生成从生成从1到到n(n10)的的n个数中取个数中取k(1=k=n)个数的个数的全部可能的排列（不一定按升序输出）。例如，当全部可能的排列（不一定按升序输出）。例如，当n=3，k=2时，应该输出（每行输出时，应该输出（每行输出5个排列）：个排列）： 12 13
33、21 23 32 31 56Program 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 (count mod 5=0) then writeln; en
34、d; exit; end; 58for 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. 5913、选排列、选排列 j=k （或k=j） p:=1 to k perm2(j+1) aj:=ai;ai:=t perm2(1)回溯算法的应用回溯算法的应用6014（大整数开方）输入一个正整数（大整数开方）输入一个正整数n（1n 0 then ans.len := a
35、.len + b.len else ans.len := a.len + b.len - 1; end; times := ans; end; 62function 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
36、:= ; 63 ans.numi + 1 := ans.numi + 1 + ans.numi div 10; ans.numi := ans.numi mod 10; end; If ans.numans.len + 1 0 then inc(ans.len); add := ans; end; 64Function average(a, b : hugeint) : hugeint; /计算大整数a和b的平均数的整数部分 var i : integer; ans : hugeint; begin ans := add(a, b); for i := ans.len downto 2 do
37、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); average := ans; end; 65Function plustwo(a : hugeint) : hugeint; /计算大整数a加2后的结果 var i : integer; ans : hugeint; begin ans := a; ans.num1 := ans.num1 + 2;
38、 i := 1; while (i = 10) do begin ans.numi + 1 := ans.numi + 1 + ans.numi div 10; ans.numi := ans.numi mod 10; inc(i); end;66 if ans.numans.len + 1 0 then ; plustwo := ans; end; Function over(a, b : hugeint) : boolean; /若大整数ab则返回1，否则返回0 var i : integer; begin if ( ) then begin over := false; exit; en
39、d; if a.len b.len then begin over := true; exit; end; 67For i := a.len downto 1 do begin if a.numi b.numi then begin over := true; exit; end; end; over := false; end; 68begin readln(s); fillchar(target.num, sizeof(target.num), 0); target.len := length(s); For i := 1 to target.len do target.numi := o
40、rd(starget.len - i + 1) - ; fillchar(left.num, sizeof(left.num), 0); left.len := 1; left.num1 := 1; right := target; 69 repeat middle := average(left, right); if over( ) then right := middle else left := middle; until over(plustwo(left), right); For i := left.len downto 1 do write(left.numi); writeln; end. 70 ans.numi + j - 1 ans.numi := ans.numi mod 10; ans.numi + a.numi + b.numi; ans.numi mod 2 (或 ans.numi and 1) inc(ans.len) （或 ans.len := ans.len + 1） a.len b.len ord(0) (或48） times(middle, middle), target
