NOIP备战读程序完善程序.ppt

现代电子技术实验第二部分读程序写结果读程序写结果完善程序完善程序现代电子技术实验阅读程序现写结果方法阅读程序现写结果方法 一、直接推理一、直接推理二、由流程图推断算法二、由流程图推断算法三、动态模拟三、动态模拟 四、由底向上阅读分析四、由底向上阅读分析 现代电子技术实验基本运算题理解理解div、mod、and、or等运算符等运算符的含义并掌握运用的含义并掌握运用注意它们之间的优先级别注意它们之间的优先级别算术运算算术运算关系运算关系运算逻辑运算逻辑运算Andordiv、mod、优先级别相同，按从左至、优先级别相同，按从左至右方向有序运算右方向有序运算现代电子技术实验VarVaru:array0.3ofinteger;u:array0.3ofinteger;I,a,b,c,x,y,z:integer;I,a,b,c,x,y,z:integer;BeginBeginfori:=0to2doui:=i*2+1;fori:=0to2doui:=i*2+1;u3:=u0oru1andu2+1;u3:=u0oru1andu2+1;a:=u0+u1+u2+u3-5;a:=u0+u1+u2+u3-5;b:=u0*(u1-u2divu3+8);b:=u0*(u1-u2divu3+8);c:=u0*u1divu2*u3;c:=u0*u1divu2*u3;x:=(a+b+2)*3-u(c+3)mod4;x:=(a+b+2)*3-u(c+3)mod4;y:=(c*100-13)divadiv(ubmod3*5);y:=(c*100-13)divadiv(ubmod3*5);if(x+y)mod2=0)thenz:=(a+b+c+x+y)div2;if(x+y)mod2=0)thenz:=(a+b+c+x+y)div2;z:=(a+b+c-x-y)*2;z:=(a+b+c-x-y)*2;writeln(x+y-z);writeln(x+y-z);End.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)!)显然，这是求组合数。当输入显然，这是求组合数。当输入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:ifsjpkthenbeginif in-m+1 then goto 10;i:=0;goto30;endelseifk0)thenif(ansi0)thenbeginbeginforj:=idownto0dowrite(ansj)forj:=idownto0dowrite(ansj)；writelnwriteln；breakbreak；endend；thenthenEnd.End.输入输入输入输入输出输出输出输出552020现代电子技术实验update(vara)是将数组是将数组a规整为高精度的十规整为高精度的十进制数组进制数组mult(vara，b)是将高精度的十进是将高精度的十进制数组制数组a乘以整数乘以整数b，积存储在积存储在a中。中。add(x，ob)计算因子表，计算因子表，ob=1,numnum*x；ob=-1，numnum/x。其中其中numi为因子为因子i的个数的个数主程序计算主程序计算catalan数数1/（n+1）*c(2*n,n)。显然显然n=5，则程序输出则程序输出42(1/6*c(10,5)现代电子技术实验完善程序完善程序 填空内容：填空内容：填空内容：填空内容：l l1 1、变量方面的填空、变量方面的填空、变量方面的填空、变量方面的填空l l2 2、循环方面的填空、循环方面的填空、循环方面的填空、循环方面的填空 l l3 3、分支转移方面的填空、分支转移方面的填空、分支转移方面的填空、分支转移方面的填空 l l4 4、主程序和子程序关系方面的填空、主程序和子程序关系方面的填空、主程序和子程序关系方面的填空、主程序和子程序关系方面的填空 l l5 5、输入输出方面的填空、输入输出方面的填空、输入输出方面的填空、输入输出方面的填空 填空方法：填空方法：填空方法：填空方法：按照自顶向下的思维方法阅读程序按照自顶向下的思维方法阅读程序按照自顶向下的思维方法阅读程序按照自顶向下的思维方法阅读程序从主程序开始，从主程序开始，从主程序开始，从主程序开始，沿控制层次向下阅读。在查到某一个子程序沿控制层次向下阅读。在查到某一个子程序沿控制层次向下阅读。在查到某一个子程序沿控制层次向下阅读。在查到某一个子程序(子模块子模块子模块子模块)时，比时，比时，比时，比照题目给出的说明和调用它的照题目给出的说明和调用它的照题目给出的说明和调用它的照题目给出的说明和调用它的“父程序父程序父程序父程序(父模块父模块父模块父模块)”，弄清该，弄清该，弄清该，弄清该子程序子程序子程序子程序(子模块子模块子模块子模块)究竟要达到什么样的子目标，然后查程序，究竟要达到什么样的子目标，然后查程序，究竟要达到什么样的子目标，然后查程序，究竟要达到什么样的子目标，然后查程序，看它是如何实现这个子目标的。如果该子程序看它是如何实现这个子目标的。如果该子程序看它是如何实现这个子目标的。如果该子程序看它是如何实现这个子目标的。如果该子程序(子模块子模块子模块子模块)有空有空有空有空格，则按照算法的逻辑进行填空。依次类推，直至最底层的格，则按照算法的逻辑进行填空。依次类推，直至最底层的格，则按照算法的逻辑进行填空。依次类推，直至最底层的格，则按照算法的逻辑进行填空。依次类推，直至最底层的子程序（子模块）中的空格全部填完为止。子程序（子模块）中的空格全部填完为止。子程序（子模块）中的空格全部填完为止。子程序（子模块）中的空格全部填完为止。现代电子技术实验指导思想指导思想假定假定填写填写验证验证调整调整验证验证现代电子技术实验1 1、背包问题：设有不同价值、不同重量的物品、背包问题：设有不同价值、不同重量的物品、背包问题：设有不同价值、不同重量的物品、背包问题：设有不同价值、不同重量的物品n n件，求从件，求从件，求从件，求从这这这这n n件物品中选取部分物品的方案，使选中物品的总重量件物品中选取部分物品的方案，使选中物品的总重量件物品中选取部分物品的方案，使选中物品的总重量件物品中选取部分物品的方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。不超过指定的限制重量，但选中物品的价值之和最大。不超过指定的限制重量，但选中物品的价值之和最大。不超过指定的限制重量，但选中物品的价值之和最大。算法说明算法说明算法说明算法说明：设：设：设：设n n件物品的重量分别为件物品的重量分别为件物品的重量分别为件物品的重量分别为w1,w2,wnw1,w2,wn；，物；，物；，物；，物品的价值分别为品的价值分别为品的价值分别为品的价值分别为v1,v2,vnv1,v2,vn。采用递归寻找物品的选择。采用递归寻找物品的选择。采用递归寻找物品的选择。采用递归寻找物品的选择方案。设前面已有了多种选择的方案，并保留了其中总价方案。设前面已有了多种选择的方案，并保留了其中总价方案。设前面已有了多种选择的方案，并保留了其中总价方案。设前面已有了多种选择的方案，并保留了其中总价值最大的方案于数组值最大的方案于数组值最大的方案于数组值最大的方案于数组resultresult中，该方案的总价值存于变量中，该方案的总价值存于变量中，该方案的总价值存于变量中，该方案的总价值存于变量maxvmaxv。当前正在考察某一新的方案，其物品选择情况保。当前正在考察某一新的方案，其物品选择情况保。当前正在考察某一新的方案，其物品选择情况保。当前正在考察某一新的方案，其物品选择情况保存于数组存于数组存于数组存于数组optionoption中。假定当前方案已考虑了前中。假定当前方案已考虑了前中。假定当前方案已考虑了前中。假定当前方案已考虑了前i-1i-1件物品，件物品，件物品，件物品，现在要考虑第现在要考虑第现在要考虑第现在要考虑第i i件物品；当前方案已包含的物品的重量之件物品；当前方案已包含的物品的重量之件物品；当前方案已包含的物品的重量之件物品；当前方案已包含的物品的重量之和为和为和为和为twtw；至此，若其余物品都选择是可能的话，本方案能；至此，若其余物品都选择是可能的话，本方案能；至此，若其余物品都选择是可能的话，本方案能；至此，若其余物品都选择是可能的话，本方案能达到的总价值的期望值设为达到的总价值的期望值设为达到的总价值的期望值设为达到的总价值的期望值设为tvtv。算法引入。算法引入。算法引入。算法引入tvtv是当一旦当前是当一旦当前是当一旦当前是当一旦当前方案的总价值的期望值也小于前面方案的总价值方案的总价值的期望值也小于前面方案的总价值方案的总价值的期望值也小于前面方案的总价值方案的总价值的期望值也小于前面方案的总价值maxvmaxv时，时，时，时，继续考察当前方案变成无意义的工作，应终止当前方案，继续考察当前方案变成无意义的工作，应终止当前方案，继续考察当前方案变成无意义的工作，应终止当前方案，继续考察当前方案变成无意义的工作，应终止当前方案，立即去考察下一个方案。因为当方案的总价值不比立即去考察下一个方案。因为当方案的总价值不比立即去考察下一个方案。因为当方案的总价值不比立即去考察下一个方案。因为当方案的总价值不比maxvmaxv大时，该方案不会再被考察。这同时保证后面找到的方案大时，该方案不会再被考察。这同时保证后面找到的方案大时，该方案不会再被考察。这同时保证后面找到的方案大时，该方案不会再被考察。这同时保证后面找到的方案一定会比前面的方案更好。一定会比前面的方案更好。一定会比前面的方案更好。一定会比前面的方案更好。现代电子技术实验programex01;constmaxn=20;vari,n,limitw,maxv,totalv:longint;w,v:array1.maxnoflongint;result,option:array1.maxnofboolean;现代电子技术实验proceduretry(i,tw,tv:longint);proceduretry(i,tw,tv:longint);vark:longint;vark:longint;beginbeginiftw+wi=limitwtheniftw+wi=limitwthenbeginbeginoptioni:=true;optioni:=true;ifinthen_(1)_ifimaxvtheniftv-vimaxvthenifinthen_(3)_ifi0)and(x0)and(y0)and(x0)and(y=n)andbzx,yandbzx,ythenbeginthenbegininc(w);hw,1:=x;hw,2:=y;bzx,y:=false;end;inc(w);hw,1:=x;hw,2:=y;bzx,y:=false;end;end;end;inc(t);inc(t);until_(4)_;until_(4)_;end;end;现代电子技术实验beginfillchar(bz,sizeof(bz),true);num:=0;write(inputfile:);readln(name);assign(int,name);reset(int);readln(int,m,n);fori:=1tomdobeginreadln(int,s);forj:=1tondobeginpici,j:=ord(sj)-ord(0);if_(5)_thenbzi,j:=false;end;end;close(int);fori:=1tomdoforj:=1tondoifbzi,jthendoing(i,j);writeln(NUMBERofcells=,num);readln;end.现代电子技术实验