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

第二部分 读程序写结果完善程序 阅读程序现写结果方法 一 直接推理 二 由流程图推断算法 三 动态模拟 四 由底向上阅读分析 基本运算题 理解div mod and or等运算符的含义并掌握运用注意它们之间的优先级别算术运算 关系运算 逻辑运算And ordiv mod 优先级别相同 按从左至右方向有序运算 Varu array 0 3 ofinteger I a b c x y z integer Beginfori 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 显然 这是求组合数 当输入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 thenbeginifi n m 1thengoto10 i 0 goto30 endelseifk mthenbeginj j 1 k k 1 goto20 end 30 writeln i end 输入asabcdffdinfdi输出 这个程序的功能是计算s串中与p匹配的子串的首指针 当程序输入asabcdffdinfdi程序应输出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 输出 显然 最后应输出123123234 vara 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 输出 最后应输出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 Beginread n fillchar num sizeof num 0 fori 0tondobeginadd i 1 1 add n n i 1 end for add n 1 1 fillchar ans sizeof ans 0 ans 0 1 fori 2tolimitdoforj 1tonum i domult ans i fori limitdownto0doif ans i 0 thenbeginforj idownto0dowrite ans j writeln break end then End 输入输出520 update 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 maxvthenifi nthen 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 1 varint text name s string pic array 1 50 1 79 ofbyte bz array 1 50 1 79 ofboolean m n i j num integer h array 1 4000 1 2 ofbyte proceduredoing p q integer vari t w x y integer begininc num 1 t 1 w 1 h 1 1 2 h 1 2 3 repeatfori 1to4dobeginx h t 1 dx i y h t 2 dy i if x 0 and x0 and y n andbz x y thenbegininc w h w 1 x h w 2 y bz x y false end end inc t until 4 end beginfillchar bz sizeof bz true num 0 write i