NOIP初赛阅读程序解题方法.ppt

NOIP初赛阅读程序解题 方法 解题步骤 做阅读程序题，首先要想方设法弄清楚程序的 功能，每个题目总有一点“写作目的”。抓住了它 ，不仅答案变得容易了，而且对自己的结果也 比较有信心。 1、从总体上通读程序，大致把握程序的目的和 算法。 2、猜测变量的作用，跟踪主要变量值的变化(列 表)，找出规律。 3、将程序分段，理清每一小段程序的作用和目 的。 4、看清输入，按照输出格式，写出结果。 5、带着到的结果回到程序进行检查。 几大方法 a. 直接模拟 b. 先模拟几次循环后找规律 c. 直接看程序了解算法功能 d. 了解程序本质后换一个方法解决 e. 有时不知道算法可以通过观察猜出来 一、基础题 送分题，主要考查选手的程序设计基础知识和计算能力。细心 Program ex301; var u:array03 of integer; i,a,b,x,y:integer; begin y:=10; for i:=0 to 3 do read(ui); a:=(u0+u1+u2+u3) div 7; b:=u0 div (u1-u2) div u3); x:=(u0+a+2)-u(u3+3) mod 4; if (x10) then y:=y+(b*100-u3) div (uu0 mod 3*5) else y:=y+20+(b*100-u3) div (uu0 mod 3*5); writeln (x,y); end. *注：本例中，给定的输入数据可以避免分母为 0 或下标越界。 输入：9 3 9 4 输出： 注意事项 1、负数整除、求模 表达式(4 mod (-3)与(-4 mod 3)的值为( ) A.-1,-1B.1,-1 C.-1,1 D.1,1 (-14) mod (-3)=( ) 模运算的规律：结果与被除数的符号相同 。即被除数为正，模为正，否则为负。结 果与除数的符号没有关系 B 函数一：算术函数 求绝对值abs：是英文单词absolute（绝对） 的缩写，abs(x)表示求x的绝对值 指数函数exp、自然对数函数 ln：exp是英 文单词exponent（指数）的缩写，exp(x)表示求 以e为底x为指数的函数值 ，即EX；ln是英文单 词logarithm（自然对数）的缩写，ln(x)表示求x 的自然对数，即logeX Pascal中无幂运算，要求XY可以用后面的公式 ：XY=eYLNX =exp(yln(x) (X0) e2.71828 平方函数SQR、正平方根函数SQRT： SQR是英文单词square（平方）的缩写； SQRT是英文单词square root（平方根）的缩写 函数二：类型转换函数 取整数函数trunc：如trunc(7.8)的值为7， trunc(-6.1)的值为-6 四舍五入函数round：如round(7.8)的值为8， round(-6.1)的值为-6 序号函数ord：返回参数的对应的序号；若参 数为字符，则返回其ASCII码（0的ASCII码为 48，A的ASCII码为65，a的ASCII码为97）值 ，如ORD(B)的值为66；若参数为BOOLEAN ，则ORD(TRUE)的值为，ORD(FALSE)的值 为 字符函数chr：返回序号所对应的字符，与ord 互为反函数；如chr(66)的值为B 函数三：顺序函数与判断函数 前趋函数PRED：返回参数的前一个数 据，若参数为第一项，则函数无意义 (predecessor ) 后继函数SUCC：返回参数的后一个数 据，若参数为最后一项，则函数无意义 (successor ) 奇偶判断函数odd：判断参数的奇偶性 ，当参数为偶数时，函数值为FALSE；当 参数为奇数时，函数值为TRUE 函数四：字符串函数 函数名功 能 说说 明 CONCAL(ST1,.,STn ) 将N个字符串连连接 起来 等效于ST1+.+ST2 COPY(S,M,N) 取S中第M个字符 开始的N个字符 若M大于S的长长度， 则则返回空串；否则则 ，若M+N大于s的长长 度，则则截断 LENGTH(S) 求s的动态动态 的长长度 返回值为值为 整数 POS(SUB,S) 在S中找子串SUB 返回值为值为 SUB在S 中的位置，为为byte 型 UPCASE(CH) 将字母CH转换转换 成 大写字母 若CH不为为小写字母 ，则则不转换转换 字符串过程 过过程名功 能 说说 明 INSERT(SOUR,S,M) 在S的第M个字符位置 处处插入子串SOUR 若返回串超过过255，则则 截断 DELETE(S,M,N) 删删除S中第M个字符开 始的N个字符串 若M大于S的长长度，则则 不删删除；否则则，若M+N 大于S的长长度，则删则删 除 到结结尾 STR(X:W:D,S) 将整数或实实数X转换转换 成字符串S W和D是整型表达式，意 义义同带带字宽宽的write语语 句 VAL(S,X,CODE) 将字符串S转换转换 成整 数或实实数X 若S中有非法字符，则则 CODE存放非法字符在S 中的下标标；否则则， CODE为为零,CODE为为整 型 特殊运算 1、数字之间的and or not xor 运算：将数字化为二进制 ，1为true，0为false，逐位运算，结果再化为10进制。 2、移位运算: shl shr x shl y=x * 2y x shr y=x div 2 y 3、地址运算： 4、逻辑运算： 设A=B=True，C=D=False，一下逻辑运算表达式值为 假的有（ ）。 A(AB)(CDA) B (AB)C)D) CA(BCD)D D(A(DC)B 看程序写结果(NOIP2007) program j302; var a,b:integer; var x,y:integer; procedure fun(a,b:integer); var k:integer; begin k:=a; a:=b; b:=k; end; begin a:=3; b:=6; x:=a; y:=b; fun(x,y); writeln(a,b); end. 集合运算 设全集 I = a, b, c, d, e, f, g, h，集合 A = a, b, c, d, e, f，B = c, d, e，C = a, d ，那 么集合 A B C 为（ ）。 (NOIP2005普及) A. c, eB. d, e C. eD. c, d, eE. d, f 为补集符号 A NOIP2004普及组 75名儿童到游乐场去玩。他们可以骑旋转 木马，坐滑行铁道，乘宇宙飞船。已知其 中20人这三种东西都玩过，55人至少玩过 其中的两种。若每样乘坐一次的费用是5 元，游乐场总共收入700，可知有 名儿 童没有玩过其中任何一种。 10 二、动态模拟 找不出其中的规律，也看不出明显的算法，便 可以尝试进行动态模拟。动态模拟是采用人工 模仿机器执行程序的方法计算结果。首先选择 比较重要的变量作为工作现场。人工执行程序 时，只要按照时间先后一步步记录现场的变化 ，就能最后得出程序的运算结果。 1、画表，画出程序执行时要用的现场情况表。 2、基本读懂各语句的功能。 3、动态执行程序 program t1； var n，k，s：longint； begin readln(n); k:=0； s:=1； while s 23420中y1的最小值 例二(全国青少年信息学奥林匹克联 赛模拟训练试卷精选) Var n,k,s:longint; begin n:=1000000000; k:=0; s:=1; while sn时k的值，即求： (k+1)3-k31000000000-k3中k的最小值 四、算法题 考查选手对一些常用的算法的熟练掌 握情况，关于素数的判定、排序、高 精度、进制转换、几何等算法题比较 多。 program Gxp2; var i , j , s ,sp1 : integer ; p : boolean ; a : array110 of integer ; begin sp1:=1; a1:=2; j:=2; while sp10 do begin bi:=n mod 2; i:=i+1; n:=n div 2 end; for j:=i-1 downto 0 do write(bj); end. 很明显，是把十进制整数转换成二进制数，所 以输出11111001111 五、子程序 NOIP1998 提高2 CONST N=10; VAR S,I:INTEGER; FUNCTION CO(I1:INTEGER):INTEGER; VAR J1,S1:INTEGER; BEGIN S1:=N; FOR J1:=(N-1) DOWNTO (N-I1+1) DO S1:=S1*J1 DIV (N- J1+1); CO:=S1; END; BEGIN S:=N+1; FOR I:=2 TO N DO S:=S+CO(I); WRITELN(S=,S); END. 分析 主程序是累加算法： s=10+1+CO(1)+CO(2)+CO(3)+CO(10) 函数CO的作用： 程序是累乘算法，找一个具体值作为参数代入计 算，例如执行CO(6)， CO(6)=10*(9*8*7*6*5)/2/3/4/5/6=(10*9*8*7*6*5) /(2*3*4*5*6)=10!/(10-6)!*6!)= 可见CO(i)的作用是求组合数 代入， 复习：排列组合公式 1. 2. NOIP2001提高1 PROGRAM GAO7_1： FUNCTION ACK(M，N：INTEGER)：INTEGER； BEGIN IF M=0 THEN ACK：=N+1 ELSE IF N=0 THEN ACK:=