《最新完善程序奥赛复习ppt课件》由会员分享，可在线阅读，更多相关《最新完善程序奥赛复习ppt课件（71页珍藏版）》请在金锄头文库上搜索。
1、进入夏天，少不了一个热字当头，电扇空调陆续登场，每逢此时，总会想起进入夏天，少不了一个热字当头，电扇空调陆续登场，每逢此时，总会想起那一把蒲扇。蒲扇，是记忆中的农村，夏季经常用的一件物品。记忆中的故那一把蒲扇。蒲扇，是记忆中的农村，夏季经常用的一件物品。记忆中的故乡，每逢进入夏天，集市上最常见的便是蒲扇、凉席，不论男女老少，个个手持乡，每逢进入夏天，集市上最常见的便是蒲扇、凉席，不论男女老少，个个手持一把，忽闪忽闪个不停，嘴里叨叨着一把，忽闪忽闪个不停，嘴里叨叨着“怎么这么热怎么这么热”，于是三五成群，聚在大树，于是三五成群，聚在大树下，或站着，或随即坐在石头上，手持那把扇子，边唠嗑边乘凉。孩
2、子们却在周下，或站着，或随即坐在石头上，手持那把扇子，边唠嗑边乘凉。孩子们却在周围跑跑跳跳，热得满头大汗，不时听到围跑跑跳跳，热得满头大汗，不时听到“强子，别跑了，快来我给你扇扇强子，别跑了，快来我给你扇扇”。孩。孩子们才不听这一套，跑个没完，直到累气喘吁吁，这才一跑一踮地围过了，这时子们才不听这一套，跑个没完，直到累气喘吁吁，这才一跑一踮地围过了，这时母亲总是，好似生气的样子，边扇边训，母亲总是，好似生气的样子，边扇边训，“你看热的，跑什么？你看热的，跑什么？”此时这把蒲扇，此时这把蒲扇，是那么凉快，那么的温馨幸福，有母亲的味道！蒲扇是中国传统工艺品，在是那么凉快，那么的温馨幸福，有母亲的味
3、道！蒲扇是中国传统工艺品，在我国已有三千年多年的历史。取材于棕榈树，制作简单，方便携带，且蒲扇的表我国已有三千年多年的历史。取材于棕榈树，制作简单，方便携带，且蒲扇的表面光滑，因而，古人常会在上面作画。古有棕扇、葵扇、蒲扇、蕉扇诸名，实即面光滑，因而，古人常会在上面作画。古有棕扇、葵扇、蒲扇、蕉扇诸名，实即今日的蒲扇，江浙称之为芭蕉扇。六七十年代，人们最常用的就是这种，似圆非今日的蒲扇，江浙称之为芭蕉扇。六七十年代，人们最常用的就是这种，似圆非圆，轻巧又便宜的蒲扇。蒲扇流传至今，我的记忆中，它跨越了半个世纪，圆，轻巧又便宜的蒲扇。蒲扇流传至今，我的记忆中，它跨越了半个世纪，也走过了我们的半个人
4、生的轨迹，携带着特有的念想，一年年，一天天，流向长也走过了我们的半个人生的轨迹，携带着特有的念想，一年年，一天天，流向长长的时间隧道，袅长的时间隧道，袅完善程序奥赛复习2013完善程序题解题方法完善程序题解题方法一、完善程序题解题步骤：一、完善程序题解题步骤：1、仔细阅读文字解释，理解题意和提供的解题思路、仔细阅读文字解释，理解题意和提供的解题思路2、根据问题的求解要求，了解输入、输出内容和问、根据问题的求解要求，了解输入、输出内容和问题处理方法题处理方法3、先阅读主程序，了解输出变量和输出要求以及主、先阅读主程序，了解输出变量和输出要求以及主程序中需要调用的过程或函数是哪些。程序中需要调用的
5、过程或函数是哪些。4、阅读过程或函数，了解其完成的功能、阅读过程或函数，了解其完成的功能5、填空方法：一般从主程序最后输出要求，反推主、填空方法：一般从主程序最后输出要求，反推主程序中的变量填写或表达式、语句等的书写程序中的变量填写或表达式、语句等的书写2 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(
6、4)n(5)break9 3.笛卡尔树笛卡尔树对于一个给定的两两不等的正整数序列，笛卡尔树是这样对于一个给定的两两不等的正整数序列，笛卡尔树是这样的一棵二叉树：首先，它是一个最小堆，即除了根结点外，的一棵二叉树：首先，它是一个最小堆，即除了根结点外，每个结点的权值都大于父节点的权值；其次，它的中序遍历每个结点的权值都大于父节点的权值；其次，它的中序遍历恰好就是给定的序列。例如，对于序列恰好就是给定的序列。例如，对于序列7、2、12、1、10、5、15、3，下图就是一棵对应的笛卡尔树。，下图就是一棵对应的笛卡尔树。现输入序列的规模现输入序列的规模n（1n maxDeep then begin m
7、axDeep := deep; num := 1; end else if deep = maxDeep then 11 ; 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:=isolve(left,j-1,deep+1)12 ; end; begin readln(n); for i := 1 to n do read(ai); maxDeep := 0; solv
8、e(1, n, 1); writeln(maxDeep, , num); end. solve(j+1,right,deep+1)13 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排列如右下：排列如右下：14比
9、比如如，从从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、1 1的的排排法法，数数组组B B统统计二进制数是否已出现过。计二进制数是否已出现过。本题利用二进制加法运
10、算的原理。本题利用二进制加法运算的原理。A数组存放每位二进制数，数组存放每位二进制数，B数组用于判断所产生的数数组用于判断所产生的数是否重复为了减少循环次数，程序中将最后五位置是否重复为了减少循环次数，程序中将最后五位置1，前面五位置，前面五位置015PROGRAMNO100；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；16WHILEAJ=1DOJ：=J1；FORI：
11、=J+1TO27DOFORI：=0TO31DOBI：=0；FORI：=1TO32DObeginFORK:=ITOI+4DOS:=S*2+AK;END；S：=0； 17 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进制的理解与应用进制的理解与应用185、初中，问题：、初中，问题：多项式乘法运算：多项式乘法运算：P(X)=2X2-x+1，q(x)=x+1p(x)*q(x)=(2x2x+1
12、)*(x+1)=2x3+X2-+1说明：多项式的表示：系数、指数说明：多项式的表示：系数、指数如上例中如上例中P（X）系数系数指数指数Q（X）系数系数指数指数2211-111010000019P*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;
13、C:ARRAY1.20,1.2OFINTEGER;20BEGINJP:=0;READLN(X,Y);WHILEX0DOBEGINJP:=JP+1;PJP,1:=X;PJP,2:=Y;READLN(X,Y);END;JQ:=0; 21 READLN(X,Y);WHILEX0DOBEGINJQ:=JQ+1;QJQ,1:=X;QJQ,2:=Y;READLN(X,Y);END;JC:=1;CJC,1:=0;CJC,2:=-1000;22FORI:=1TOJPDOBEGIN Y：=PI,2;FORJ:=1TOJQDOBEGIN;Y1：=Y+QJ，2；K:=1;WHILEY1CK,2DOK:=K+1;IF
14、Y1=CK,2THENELSEBEGIN23FORL：=JCDOWNTOKDOBEGINCL+1,1:=CL，1;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归并算法思想归并算法思想246、在在A，B两个城市之间设有两个城市之间设有N个路站个路站(如下图如下图中的中的S1，且且Nsum)(5)bj=k(6)bI
15、：=1;应用进制方法搜索应用进制方法搜索348 8、工工厂厂在在每每天天的的生生产产中中, ,需需要要一一定定数数量量的的零零件件, ,同同时时也也可可以以知知道道每每天天生生产产一一个个零零件件的的生生产产单单价价。在在N N天天的的生生产产中中, ,当当天天生生产产的的零零件件可可以以满满足足当当天天的的需需要要, ,若若当当天天用用不不完完, ,可可以以放放到到下下一一天天去去使使用用, ,但但要要收收取取每每个个零零件件的的保管费保管费, ,不同的天收取的费用也不相同。不同的天收取的费用也不相同。问问题题求求解解: :求求得得一一个个N N天天的的生生产产计计划划( (即即N N天天中
16、中每每天天应应生生产零件个数产零件个数),),使总的费用最少。使总的费用最少。（穷举算法）（穷举算法）输入输入: :N(N(天数天数N=29)N=29)每天的需求量每天的需求量( (N N个整数个整数) )每天生产零件的单价每天生产零件的单价( (N N个整数个整数) )每天保管零件的单价每天保管零件的单价( (N N个整数个整数) )35输出输出: :每天的生产零件个数每天的生产零件个数( (N N个整数个整数) )例如例如:当当N=3时时,其需要量与费用如下其需要量与费用如下:第一天第一天第二天第二天第三天第三天需要量需要量252515153030生产单价生产单价202030303232保
17、管单价保管单价5 5l0l00 0生产计划的安排可以有许多方案生产计划的安排可以有许多方案, ,如下面的三种如下面的三种: :第一天第一天第二天第二天第三天第三天总的费用总的费用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=192536程序说明程序说明: :bn:bn:存放每天的需求量存放每天的需求量, , cn:cn:每天生产零
18、件的单价每天生产零件的单价dn:dn:每天保管零件的单价每天保管零件的单价 , , en:en:生产计划生产计划程序程序: :Programexp5;Vari,j,n,yu,j0,j1,s:integer;b,c,d,e:array0.30ofinteger;beginreadln(n);fori:=1tondoreadln(bi,cI,di);37Fori:=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
19、:=j1+1;end;Fori:=1tondoreadln;end.(1)cn+1(2)(yu+dj1)(cj1+1)(3)yu:=yu+dj1;(4)ej0:=s;(5)write(eI,);389、问题描述、问题描述:有有n种基本物质种基本物质(n10),分别记为分别记为P1,P2,Pn,用用n种种基本物质构造物品基本物质构造物品,这些物品使用在这些物品使用在k个不同地区个不同地区(k20),每个地区对每个地区对物品提出自己的要求物品提出自己的要求,这些要求用一个这些要求用一个n位的数表示位的数表示:12n,其其中中:i=1表示所需物质中必须有第表示所需物质中必须有第i种基本物质种基本物质
20、=-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表示第表示第i个
21、地区对第个地区对第j种物品是不需要的种物品是不需要的39Programgxp2;Vari,j,k,n:integer;p:boolean;b:array0.20of0.1;a:array1.20,1.10dinteger;beginreadln(n,k);fori:=1tokdobeginforj:=1tondoread(ai,j);readln;end;40fori:=0tondobi:=0;p:=true;whiledobeginj:=n;whilebj=1doj:=j-1;fori:=j+1tondobI:=0;(3)(1)Pand(b0=0)(2)bj:=1;(3)p:=false;4
22、1fori:=1tokdoForj:=1tondoif(ai,j=1)and(bj=0)orthenp:=true;end;ifthenwriteln(找不到找不到!)elsefori:=1tondoif(bi=1)thenwriteln(物质物质,I,需要需要)elsewriteln(物质物质,i,不需要不需要);end.(4)(aI,j=-1)and(bj=1)(5)p4210、回形排列、回形排列(5个空个空,每空每空2分共分共10分分)【问题描述问题描述】：给出一个：给出一个N(（1N20）,得到一个得到一个N*N的回形排列方阵。的回形排列方阵。例例如如：当当N=5时时，得得到到的的回回
23、形形排排列列方方阵为：阵为：1234516171819615242520714232221813121110943输入输入N，输出，输出N*N的方阵的方阵【程序说明程序说明】A：ARRAY1.20,1.20OFINTEGER;存放存放填入的数填入的数K:INTEGER;每次填入的数每次填入的数;programcup_7;vari,j,k,n,n1:integer;a:array1.20,1.20ofinteger;beginreadln(n);n1:=ndiv2;；fori:=1ton1dobeginforj:=iton-idobegin；k:=k+1;end;forj:=iton-Idobe
24、gink:=k+1;end;44forj:=n-i+1downtoi+1dobegin；k:=k+1;end;forj:=n-i+1downtoi+1dobeginaj,i:=k;k:=k+1;end;end;ifthena(n+1)div2,(n+1)div2:=k;fori:=1tondobeginforj:=1tondowrite(ai,j:4);writeln;end;end.45回形矩阵回形矩阵(1)K:=1;(2)aI,j:=k;(3)aj,n-i+1:=k;(4)an-i+1,j:=k;(5)odd(n)数字阵列数字阵列,坐标与元素之间的关系坐标与元素之间的关系46 11（子矩阵
25、）输入一个（子矩阵）输入一个n1*m1的矩阵的矩阵a，和，和n2*m2的矩的矩阵阵b，问，问a中是否存在子矩阵和中是否存在子矩阵和b相等。若存在，输出所有子相等。若存在，输出所有子矩阵左上角的坐标；若不存在输出矩阵左上角的坐标；若不存在输出“Thereisnoanswer”Const 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); for i := 1 to n1
26、 do for j := 1 to m1 do read(aij); readln(n2, m2); for i := 1 to n2 do 47Forj:=1tom2do;haveAns:=false;Fori:=1ton1-n2+1doForj:=1todobegin;fork1:=1ton2dofork2:=1todoifai+k11,j+k2-1bk1,k2thengood:=false;48if good then begin writeln(i, , j); ; end; end; if not haveAns then writeln(There is no answer); e
27、nd. read(bij)m1-m2+1good:=truem2haveAns:=true4912、自然数拆分：、自然数拆分：programp_11;constm=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;50beginreadln(n);I:=1;sum:=0;j:=0;count:=0;RepeatJ:=j+1;Sum:=sum+j
28、;If(1)thenBeginSI:=(2);Ifsum=nthenBeginPrint;Sum:=(3);I:=I-1;Sum:=(4);(1)Sum=n(2)J(3)Sum-sI;(4)Sum-sI;回溯算法应用回溯算法应用51J:=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-sI52自然数拆分比较好的算法：自然数拆分比较好的算法：programp1_5(input,output);Vara,b:array
29、1.100ofbyte;n:integer;proceduretry(m,start,k:integer);vari,j:integer;beginfori:=startto(mdiv2)dobeginak:=m-i;bk:=i;forj:=1tokdowrite(bj,+);53writeln(ak);try(ak,i,k+1)end;end;beginreadln(n);try(n,1,1)end.54 13、（选排列）下面程序的功能是利用递归方法、（选排列）下面程序的功能是利用递归方法生成从生成从1到到n(n10)的的n个数中取个数中取k(1=k=n)个数的个数的全部可能的排列（不一定按
30、升序输出）。例如，当全部可能的排列（不一定按升序输出）。例如，当n=3，k=2时，应该输出（每行输出时，应该输出（每行输出5个排列）：个排列）：12132123323155Programex501;Vari,n,k:integer;a:array1.10ofinteger;count:longint;Procedureperm2(j:integer);vari,p,t:integer;beginifthenbeginfori:=ktondobegininc(count);t:=ak;ak:=ai;ai:=t;56 for do write(ap:1); write( ); t:=ak;ak:=
31、ai;ai:=t; if (count mod 5=0) then writeln; end; exit; end; 57fori:=jtondobegint:=aj;aj:=ai;ai:=t;t:=aj;endend;beginwriteln(Entryn,k(k=n):);read(n,k);count:=0;fori:=1tondoai:=i;end.5813、选排列、选排列 j=k （或k=j） p:=1 to k perm2(j+1) aj:=ai;ai:=t perm2(1)回溯算法的应用回溯算法的应用5914（大整数开方）输入一个正整数（大整数开方）输入一个正整数n（1n 0 t
32、hen ans.len := a.len + b.len else ans.len := a.len + b.len - 1; end; times := ans; end; 61function 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
33、 begin ans.numi := ; 62 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; 63Function average(a, b : hugeint) : hugeint; /计算大整数a和b的平均数的整数部分 var i : integer; ans : hugeint; begin ans := add(a, b); for i := ans.
34、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); average := ans; end; 64Function plustwo(a : hugeint) : hugeint; /计算大整数a加2后的结果 var i : integer; ans : hugeint; begin ans := a; ans.num1
35、:= ans.num1 + 2; 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;65 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 :=
36、 false; exit; end; if a.len b.len then begin over := true; exit; end; 66For i := a.len downto 1 do begin if a.numi b.numi then begin over := true; exit; end; end; over := false; end; 67begin readln(s); fillchar(target.num, sizeof(target.num), 0); target.len := length(s); For i := 1 to target.len do
37、target.numi := ord(starget.len - i + 1) - ; fillchar(left.num, sizeof(left.num), 0); left.len := 1; left.num1 := 1; right := target; 68 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. 69 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 70结束语结束语谢谢大家聆听！谢谢大家聆听！71
