NOIP备战读程序完善程序

第二部分•读程序写结果•完善程序阅读程序现写结果方法一、直接推理二、由流程图推断算法三、动态模拟四、由底向上阅读分析基本运算题•理解div、mod、＊、and、or等运算符的含义并掌握运用•注意它们之间的优先级别•算术运算关系运算逻辑运算•Andor•div、mod、＊优先级别相同，按从左至右方向有序运算•Var•u::array[0..3]ofinteger;•I,a,b,c,x,y,z:integer;•Begin•fori:=0to2dou[i]:=i*2+1;•u[3]:=u[0]oru[1]andu[2]+1;•a:=u[0]+u[1]+u[2]+u[3]-5;•b:=u[0]*(u[1]-u[2]divu[3]+8);•c:=u[0]*u[1]divu[2]*u[3];•x:=(a+b+2)*3-u[(c+3)mod4];•y:=(c*100-13)divadiv(u[bmod3]*5);•if((x+y)mod2=0)thenz:=(a+b+c+x+y)div2;•z:=(a+b+c-x-y)*2;•writeln(x+y-z);•End.可关注递归计算题,如斐波那契数列对于一些语句少、结构简单且可读性较强的程序，不妨通过分析程序流程，直接寻找其间蕴含的计算模型。varm,n,I:integer;t:extended;beginreadln(n,m);t:=1;fori:=1tomdot:=t*(n-i+1)/i;writeln(t:0:0);end.输入105输出：直接推理【分析】由for循环可以看出t=，即i=1时，t=n；i=2时，t=n*(n-1)/2；i=3时，t=n*(n-1)/2*(n-2)/3；………i=m时，t=c(n,m)=n!/(m!*(n-m)!)miiin11显然，这是求组合数。当输入n=10、m=5时，程序应输出252。对于一些易读性不十分好的程序，最好的办法是画流程图。其步骤如下⑴跟着程序画流程图，一句一框；⑵根据上下文的联系合并流程图。若前几句计算值都要代入后一表达式，则合并为一框。接连合并几次，使程序成为一个大功能块；⑶由大功能块推断算法；⑷代入输入值，计算结果。流程图推断法label10,20,30;vars,p:string;i,k,n,j,m:integer;beginreadln(s);n:=length(s);readln(p);m:=length(p);i:=0;10:i:=i+1;j:=i;k:=1;20:ifs[j]p[k]thenbeginifin-m+1thengoto10;i:=0;goto30;endelseifkmthenbeginj:=j+1;k:=k+1;goto20;end;30:writeln(i);end.输入asabcdffdinfdi输出•这个程序的功能是计算s串中与p匹配的子串的首指针。当程序输入•asabcdffdin•fdi•程序应输出8，即s[8]…s[10]=p=‘fdi’。动态模拟方法是采用人工模仿机器执行程序的方法计算结果值。首先选择程序中比较重要的变量作为工作现场。人工执行程序时，只要按照时间先后一步步记录下现场的变化，就能最后得出程序的运算结果。其具体布置如下：⑴画表，画出程序执行时要用的现场情况表；⑵基本读懂各语句的功能⑶走程序，即动态模拟程序。主要根据各语句的功能，按照程序执行路径的先后顺序逐项填写现场情况表，直至得出最后结果；动态模拟方法vari,j:integer;a:array[1..3,1..3]ofinteger;beginfori:=1to3dobeginforj:=1to3dobeginifi=3thena[i,j]:=a[i-1,a[i-1,j]]+1elsea[i,j]:=j;write(a[i,j]);end;writelnend;readlnend.输出：ji123112321233234显然，最后应输出123123234vara,d:array[1..100]ofinteger;n,i,j,k,x,s:integer;beginn:=5;a[1]:=1;d[1]:=1;fori:=1tondobegins:=i+1;x:=0;forj:=1ton+1-idobegink:=s+x;x:=x+1;a[j+1]:=a[j]+k;write(a[j],'');end;writeln('...');d[i+1]:=d[i]+i;a[1]:=d[i+1];end;end.输出：外循环内循环i=S=d[i+1]a[1]=k=x=a[j+1]=输出a[j]1222213123263343106454151056521152344315224295353149464201434774184252138363191345111151127262181256611711最后应输出1361015…25914…4813…712…11…由底向上分析的阅读分析方法就是在剖析了子程序和模块资源的基础上，建立对高层程序结构的理解，从而完成整个程序的阅读分析，即从最底层的子目标开始分析起，看它们做了哪些事情；然后分析上一层的子目标，看这些子目标在下一层子目标实现的基础上实现了哪些功能……。经过自底而上的阅读分析，最后得出计算模型。constlimit=3000；typetdata=array[0..limit]oflongint;varans,num:tdata;i，j，n：longint;Procedureupdate(vara:tdata);varintI;beginfori：=0tolimit-1dobegininc(a[i+1],a[i]div10);a[i]:=a[i]mod10;endend；Proceduremult(vara:tdata;b:integer);vari，j：integer；beginfori:=0tolimitdoa[i]:=a[i]*b;update(a);end；procedureadd(x，ob：longint)；vari：longint；beginfori：=2toxdowhile(xmodi=0)dobegininc(num[i]，ob);x：=xdivi’;end；End;•Begin•read(n)；•fillchar(num，sizeof(num)，0)；•fori：=0tondo•beginadd(i+1，-1)；add(n+n-i，1)；end；{for}•add(n+1，-1);fillchar(ans，sizeof(ans)，0);ans[0]:=1；•fori：=2tolimitdo•forj:=1tonum[i]domult(ans，i)；•fori：=limitdownto0do•if(ans[i]0)then•begin•forj:=idownto0dowrite(ans[j])；•writeln；break；•end；{then}•End.•输入输出•5•20update(vara)是将数组a规整为高精度的十进制数组mult(vara，b)是将高精度的十进制数组a乘以整数b，积存储在a中。add(x，ob)计算因子表，ob=1,num←num*x；ob=-1，num←num/x。其中num[i]为因子i的个数主程序计算catalan数1/（n+1）*c(2*n,n)。显然n=5，则程序输出42(1/6*c(10,5))完善程序•填空内容：–1、变量方面的填空–2、循环方面的填空–3、分支转移方面的填空–4、主程序和子程序关系方面的填空–5、输入输出方面的填空填空方法：按照自顶向下的思维方法阅读程序——从主程序开始，沿控制层次向下阅读。在查到某一个子程序(子模块)时，比照题目给出的说明和调用它的“父程序(父模块)”，弄清该子程序(子模块)究竟要达到什么样的子目标，然后查程序，看它是如何实现这个子目标的。如果该子程序(子模块)有空格，则按照算法的逻辑进行填空。依次类推，直至最底层的子程序（子模块）中的空格全部填完为止。指导思想假定－填写－验证－调整－验证•1、背包问题：设有不同价值、不同重量的物品n件，求从这n件物品中选取部分物品的方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。•[算法说明]：设n件物品的重量分别为w1,w2,…,wn；，物品的价值分别为v1,v2,…,vn。采用递归寻找物品的选择方案。设前面已有了多种选择的方案，并保留了其中总价值最大的方案于数组result中，该方案的总价值存于变量maxv。当前正在考察某一新的方案，其物品选择情况保存于数组option中。假定当前方案已考虑了前i-1件物品，现在要考虑第i件物品；当前方案已包含的物品的重量之和为tw；至此，若其余物品都选择是可能的话，本方案能达到的总价值的期望值设为tv。算法引入tv是当一旦当前方案的总价值的期望值也小于前面方案的总价值maxv时，继续考察当前方案变成无意义的工作，应终止当前方案，立即去考察下一个方案。因为当方案的总价值不比maxv大时，该方案不会再被考察。这同时保证后面找到的方案一定会比前面的方案更好。•programex01;constmaxn=20;vari,n,limitw,maxv,totalv:longint;w,v:array[1..maxn]oflongint;result,option:array[1..maxn]ofboolean;•proceduretry(i,tw,tv:longint);vark:longint;beginiftw+w[i]=limitwthenbeginoption[i]:=true;ifinthen______(1)_____elsebeginfork:=1tondoresult[k]:=option[k];maxv:=tvend;______(2)_______;end;iftv-v[i]maxvthenifinthen_____(3)_____elsebeginfork:=1tondoresult[k]:=option[k];maxv:=tv-v[i]endend;•beginwrite('输入物品种数n:');readln(n);writeln('输入各物品的重量和价值:');totalv:=0;fori:=1tondobeginwrite('Inputw[',i,'],v[',i,']:');readln(w[i],v[i]);___(4)___;end;write('输入限制重量limitw:');readln(limitw);maxv:=0;fori:=1tondooption[i]:=false;try(1,0,totalv);write('选择方案为:');fori:=1tondoif___(5)___thenwrite(i,'');writeln;writeln('总价值为:',maxv)end.•2、一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。如:阵列0234500067103456050020456006710000000089有4个细胞。[算法说明]：1．从文件中读入m*n矩阵阵列，将其转换为boolean矩阵存入bz数组中；2．沿bz数组矩阵从上到下，从左到右，找到遇到的第一个细胞；3．将细胞的位置入队h，并沿其上、下、左、右四个方向上的细胞位置入队，入队后的位置bz数组置为FLASE；4．将h队的队头出队，沿其上、下、左、右四个方向上的细胞位置入队，入队后的位置bz数组置为FLASE；5．重复4，直至h队空为止，则此时找出了一个细胞；6．重复2，直至矩阵找不到细胞；7．输出找到的细胞数•programxibao;constdx:array[1..4]of-1..1=(-1,0,1,0);dy:array[1..4]of-1..1=(0,1,0,