noip初赛阅读程序的解题技巧.ppt

阅读程序题是历年noip初赛的重头戏 比重之大 32 丢分之险 错一题是8分 能否快而准确的完成好阅读程序题将成为通过初赛进入复赛的关键 在阅读程序时 由于疏忽或考虑不周可能对程序的理解出现各式各样的偏差 导致错误的计算结果 正确的阅读方法和分析技巧不仅可以较好保证运算结果的准确性 而且能大大缩短理解程序愿意的时间 一般的解题步骤如下 1 从整体上通读程序 大致把握程序的目的和算法 2 猜测变量的作用 跟踪主要变量值的变化 找出规律 3 将程序分段 理清每一小段的作用和目的 灵感 关键表达式 语句的领会 4 看清输入 按照输出的格式 写出结果 5 带着得到的结果回到程序进行检查 一 基础题 此类题在近几年频频出现 属于送分题 主要考察选手的程序设计基础知识和计算能力 只要细心一些 计算不出错 就能轻松的解决问题 program1 vara b c d sum longint beginread a b c d a amod23 b bmod28 c cmod33 sum a 5544 b 14421 c 1228 d sum sum 21252 sum summod21252 if sum 0 thensum 21252 writeln sum end 输入 28310223320输出 运算过程如下 program2 constu array 1 4 ofinteger 0 5 3 1 v array 1 4 0finteger 0 7 6 5 vara b c d e f x y z integer beginread a b c d e f z f e d c 3 div4 y 5 d u cmod4 if b y thenbeginz z b y 8 div9 x b y 8 div9 9 b y 4 11 e V cmod4 endelsex y b 4 11 e v cmod4 if a x thenz z a x 35 div36 writeln z end 输入 479205647输出 运算过程如下所示 二 找规律题 对于一些语句少 结果简单 可读性强但运算巨大的程序 不妨通过分析程序的流程 初步的模拟程序 直接寻找其间蕴含的规律 PROGRAM3 VARX Y1 Y2 Y3 INTEGER BEGINREADLN X Y1 0 Y2 1 Y3 1 WHILEY2 XDOBEGINY1 Y1 1 Y3 Y3 2 Y2 Y2 Y3END WRITELN Y1 END 输入 23420输出 本题计算的是y2超过x时y1的值 因为输入的x比较大 计算量大 不可能通过完全模拟得出结果 但我们可以模拟前几步试图找出其中的规律 从上表不难看出 y2 y1 1 2 y2超过x可写成 y1 1 2超过x 即求解 y1 1 2 23420中y1的最小值 解之y1为153 program4 varn k s longint beginn 1000000000 k 0 s 1 whiles ndobegink k 1 n n s s s 6 k end writeln k end 输出 推导如下表 从上表我们不难推出 n 1000000000 k 3s k 1 3 k 3程序要输出循环结束条件s n时k值 即求 k 1 3 k 3 1000000000 k 3中k的最小值 解之k为1000 三 算法题 考查选手对一些常用的算法的熟练掌握情况 历年关于素数的判定 排序 高精度 进制转换 几何算法的题比较多 Program5 Vard1 d2 X Min real beginMin 10000 X 3 whileX 15dobegind1 sqrt 9 X 3 X 3 d2 sqrt 36 15 X 15 X if d1 d2 MinthenMin d1 d2 X x 0 001 end writeln Min 10 2 end 输出 分析 典型的平面几何问题 语句d1 sqrt 9 x 3 x 3 即d1 sqrt 0 3 2 x 3 2 可以理解成平面直角坐标系中点 0 x 至点 3 3 的距离 语句d2 sqrt 36 15 x 15 x 即d2 sqrt 6 0 2 15 x 2 可以理解成平面直角坐标系中点 0 x 到点 6 15 的距离 程序是求x在0至15之间d1 d2的最小值 四 子程序题 在阅读包含子程序的程序时 一般先阅读子程序 了解主程序中是如何调用子程序的 在阅读子程序 了解其功能后 再代入到主程序进行计算 处理 PROGRAM6 FUNCTIONACK M N INTEGER INTEGER BEGINIFM 0THENACK N 1ELSEIFN 0THENACK ACK M 1 1 ELSEACK ACK M 1 ACK M N 1 END BEGINWRITELN ACK