信息学竞赛辅导初赛之完善程序

初赛之完善程序,变量方面的填空（定义类型、设定初值、变量赋值等） 循环方面的填空（定义变量、设定循环的初值和终值、在循环中如何引用） 分支转移方面的填空（定义布尔表达式、确定程序的走向） 主程序和子程序关系方面的填空（值参、变参、调用格式） 输入输出方面的填空,不含子程序,例一、求元素之和最大的子方阵：在m*n的正整数数字方阵中，找出一个p*q的子阵，使得其元素之和最大。,程序清单,Var a:array1.20,1.20 of integer; m,n,p,q,i,j,max,p1,q1,s,i1,j1:integer; Begin for i:=1 to 20 do for j:=1 to 20 do ai,j:=0; readln(m,n); for i:=1 to m do begin for j:=1 to n do read(ai,j);readln end; readln(p,q); max:=0;,程序清单（续）,For i:=1 to m-p+1 do for j:=1 to n-q+1do begin _(1)_; for i1:=i to p+i-1 do for j1:=j to q+j-1 do _(2)_; if smax then begin _(3)_; p1:=i;q1:=j;end; end; For i:=p1 to _(4)_ do Begin for j:=q1 to _(5)_do write(ai,j:3);writeln;end;readln; end.,本题的关键是找出所有的pq子阵，并逐一比较。 因此，程序的第二段对给出的m,n及p,q，用二重循环控制pq子阵左上角元素的下标i,j。 再用二重循环控制以i,j为左上角元素下标的pq子阵元素ai1,j1，并累加求和。 因此（2）处语句为s:=s+ ai1,j1。 为了避免重复求和，s的初值应为0，其位置应在累加之前，因此（1）处为s:=0。 填空（3），根据判断条件smax可知，是要记录当前元素之和最大的值，因此填q+q1-1。 最后一段是输出pq子阵，根据上面if then子句可知，p1,q1记录了当前元素之和最大子阵的左上角位置。 该子阵的行从p1到p+p1-1，列从q1到q+q1-1，因此（4）处为p+p1-1，（5）处为q+q1-1。,完善含有子程序的程序,例、 输入任意一个正整数n，输出组成n的互不相同的菲波那契数。 算法说明： （1）寻找小于等于n的最大菲波那契数a，并以a作为组成n的一个数； （2）若na，则以n-a作为n的新值，重复步骤（1）；若a=n，则结束。 Var n:integer; first:boolean; Function find(n:integer):integer; Var a,b,c:integer; Begin a:=1;b:=1; repeat c:=_(1)_;a:=b;b:=c; until b=n; if b=n then find:=_(2)_ else find:=_(3)_ End;,c=a+b,n或c,a,例（续）,Procedure p(n:integer); Var a:integer; begin a:=find(n); if first then begin write(a:4);first:=false;end else write(+,a:4); if an then p_(4)_; End; begin readln(n);first:=true;write(n:5,=);p(n);writeln; readln end.,关键在于正确理解函数find与过程P的功能。 寻找小于等于n的最大菲波那契数由find函数实现，求出并输出组成n的互不相同的菲波那契数由过程P来完成。 过程P是一个递归算法。 由题意说明（2）若na，则n-a作为n的新值，重复步骤（1） （4）为过程p的参数项，即n-a。,完善程序题1,下面程序的功能是利用递归方法生成从1到n(n10)的n个数的全部可能的排列（不一定按升序输出）。例如，输入3，则应该输出（每行输出5个排列）： 123 132 213 231 321 312,解题分析,1.回忆一般递归程序的结构 2.常规的用递归式穷举产生序列的算法 3.观察子程序序列产生部分，发现不属于常规的生成算法（因为有数字交换语句），而是先生成一个顺序序列，然后通过不断的交换不同位置上的数字来产生序列。 4.转而结合程序特点来分析算法并及时验证。,主程序,begin writeln(Entry n:); read(n); count:=0; for i:=1 to n do ai:=i; ; end.,由于程序通过递归求解，所以这里必定是语句perm(?),子程序第1段,Procedure perm(k:integer); var j,p,t:integer; begin if then begin inc(count); for p:=1 to k do write(ap:1); write( ); if ( ) then writeln; exit; end;,下面循环在输出一个排列，循环终值必定是n，再结合一般递归结束条件，这里必定是n=k,结合试题中count的作用且每行5个输出，所以这里必定是count mod 5=0,子程序第2段,for j:=k to n do begin t:=ak; ak:=aj; aj:=t; ; t:=ak; ; end,按照递归结构，这里是现场恢复语句，所以就是ak和aj值交换回来。,首先确定是递归调用语句；结合前面n=k递归结束条件以及一般递归参数变化规律，这里填perm(k+1)；同时可以初步确定空格5填perm(1)。,验证,1.第一个序列产生：首先是a1和a1交换、a2和a2交换，然后输出123（假定n=3）。 2.第二个序列产生：递归回来后，首先是a2和a3交换，然数输出132。 3.第3个序列产生：输出132后，递归返回，a1和a2交换（一开始的1和2），输出序列213。 ,解题关键,1.递归：递归一般程序结构、递归调用的本质。 2.适当的猜想假定，结合全局的系统验证。,阅读程序题2,由键盘输入一个奇数 P (P100,000,000)，其个位数字不是5，求一个整数 S，使 PS = 1111.1 ( 在给定的条件下，解 S 必存在)。要求在屏幕上依次输出以下结果: （1）S 的全部数字。除最后一行外，每行输出 50 位数字。 （2） 乘积的数字位数。 例1：输入p=13，由于13*8547=111111，则应输出（1）8547，（2）6 例2：输入p=147，则输出结果应为（1）755857898715041572184429327286470143613 （2）42，即等式的右端有42个1。,输入部分代码,while (true) do begin writeln (Input p, the last digit is 1 or 3 or 7 or 9:); readln(p); if (p mod 20)and(p mod 50) then ; 如果输入的数符合要求，结束循环 end;,根据题意，该部分用来输入正确性的判断，输入不正确继续重新输入，否则中断循环。填写break。,a:=0; n:=0; while (ap) do begin a:=a*10+1; inc(n); end; t:=0; repeat b:=a div p; write(b:1); inc(t); if ( ) then writeln; c:= ; a:= inc(n); until c=0; dec(n); writeln; writeln(n=, );,先产生一个比p大的数a，全部由1组成。N表位数,变量t在统计s的位数，按照题意的分行输出，这里条件为t mod 50=0,最后要输出位数，而n表示位数，这里应填写n,算法分析,1.通过穷举p*s来尝试，首先产生一个刚好比p大的p*s，然后尝试用p去整除。 2.整除时每产生一个整除商b就输出，同时位数n增加1。 3.按照除法的原理，接下来用本次除法的余数c来产生新一轮的p*s（c*10+1）,然后重复执行第2步。 4.重复执行23步直到某次能整除为止（c=0）。,a:=0; n:=0; while (ap) do begin a:=a*10+1; inc(n); end; t:=0; repeat b:=a div p; write(b:1); inc(t); if ( ) then writeln; c:= ; a:= inc(n); until c=0; dec(n); writeln; writeln(n=, );,求得余数c，为下一次整除作准备，所以填写a-p*b,产生新的被除数a，因为都是由1构成，所以增加1位后的a应为c*10+1,解题关键,1、穷举法思想 2、结合产生规则的穷举法 3、基于数组实现的高精度除法,【问题描述】 有甲、乙、丙三个人和A、B、C三项不同的工作，每人一天只能干一项工作，且一项工作每天必须一个人干。下表表示的是甲、乙、丙三个人在A、B、C三个不同的工作岗位上工作一天所能创造的价值： 说明：甲在A岗位上干一天所创造的价值为30，在B岗位上干一天所创造的价值为50，在C岗位上干一天所创造的价值为25。 请编程确定如何分配工作（甲、乙、丙三人在什么工作岗位），三人一天共同创造的价值最多。 【程序清单】 program test43; var i,j,a,b,c,ma,mb,mc,s,m:integer; v:array 1.3,1.3 of integer;,begin m:=0; for i:= 1 to 3 do for i:= 1 to 3 do read(vi,j); for a:= 1 to 3 do for b:= 1 to 3 do begin c:= ; if a*b*c=6 then begin s:= ; if sm then begin ; ma:=a; mb:=b; mc:=c end; end; end; writeln(Jia:,CHR(64+ma),Yi:10,CHR(64+mb),Bing:10,CHR(64+mc); writeln(,M=,m) end.,6-a-b,v1,a+v2,b+v3,c,m:=s,