《noip初赛阅读程序解题方法.ppt》由会员分享，可在线阅读，更多相关《noip初赛阅读程序解题方法.ppt（33页珍藏版）》请在金锄头文库上搜索。
1、NOIP初赛阅读程序解题方法,解题步骤,做阅读程序题，首先要想方设法弄清楚程序的功能，每个题目总有一点“写作目的”。抓住了它，不仅答案变得容易了，而且对自己的结果也比较有信心。 1、从总体上通读程序，大致把握程序的目的和算法。 2、猜测变量的作用，跟踪主要变量值的变化(列表)，找出规律。 3、将程序分段，理清每一小段程序的作用和目的。 4、看清输入，按照输出格式，写出结果。 5、带着到的结果回到程序进行检查。,几大方法,a. 直接模拟 b. 先模拟几次循环后找规律 c. 直接看程序了解算法功能 d. 了解程序本质后换一个方法解决 e. 有时不知道算法可以通过观察猜出来,一、基础题,送分题，主要
2、考查选手的程序设计基础知识和计算能力。细心 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 (
3、x,y); end. *注：本例中，给定的输入数据可以避免分母为 0 或下标越界。 输入：9 3 9 4 输出：,注意事项,1、负数整除、求模 表达式(4 mod (-3)与(-4 mod 3)的值为( ) A.-1,-1 B.1,-1 C.-1,1 D.1,1 (-14) mod (-3)=( ) 模运算的规律：结果与被除数的符号相同。即被除数为正，模为正，否则为负。结果与除数的符号没有关系,B,函数一：算术函数,求绝对值abs：是英文单词absolute（绝对）的缩写，abs(x)表示求x的绝对值 指数函数exp、自然对数函数 ln：exp是英文单词exponent（指数）的缩写，exp(
4、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)的值为
5、-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：判断参数的
6、奇偶性，当参数为偶数时，函数值为FALSE；当参数为奇数时，函数值为TRUE,函数四：字符串函数,字符串过程,特殊运算,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; v
7、ar 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, e B. d, e C. e D. c
8、, d, e E. d, f 为补集符号,A,NOIP2004普及组,75名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已知其中20人这三种东西都玩过，55人至少玩过其中的两种。若每样乘坐一次的费用是5元，游乐场总共收入700，可知有 名儿童没有玩过其中任何一种。,10,二、动态模拟,找不出其中的规律，也看不出明显的算法，便可以尝试进行动态模拟。动态模拟是采用人工模仿机器执行程序的方法计算结果。首先选择比较重要的变量作为工作现场。人工执行程序时，只要按照时间先后一步步记录现场的变化，就能最后得出程序的运算结果。 1、画表，画出程序执行时要用的现场情况表。 2、基本读懂各语句的
9、功能。 3、动态执行程序,program t1； var n，k，s：longint； begin readln(n); k:=0； s:=1； while s = n do begin k:=k+1; n:=n-s; s:=s+6*k end; writeln (k) end. 输入:100 输出:_,解题,列表跟踪变量的变化：,1,99,7,2,92,19,73,3,37,36,4,61,T,T,T,F,VAR P，Q，S，T：INTEGER； BEGIN READLN(P)； FOR Q:=P+1 TO 2*P DO BEGIN T:=0；S:=(P*Q)MOD(Q-P)； IF S=0
10、 THEN BEGIN T:=P+Q+(P*Q)DIV(Q-P)；WRITE(T：4)； END； END； END.,解题,（1）划分程序结构，确定循环执行次数 （2）确定输出： （3）列表追踪变量变化：,程序的运行结果是：181 110 87 76 66 62 61 60,全国青少年信息学奥林匹克联赛模拟训练试卷精选试卷4,Var a,d:array 1100 of integer; n,i,j,k,x,s:integer; begin n:=5;a1:=1;d1:=1; for i:=1 to n do begin s:=i+1;x:=0; for j:=1 to n+1-i do be
11、gin k:=s+x; x:=x+1; aj+1:=aj+k; write(aj, ); end; writeln(); di+1:=di+1; a1:=di+1; end; end.,三、找规律(NOIP2001提高组第四题),4.PROGRAM GAO7_4； VAR X，Y1，Y2，Y3：INTEGER； BEGIN READLN(X)； Y1：=0；Y2：=1；Y3：=1； WHILE Y2=X DO BEGIN Y1：=Y1+1；Y3：=Y3+2；Y2：=Y2+Y3 END； WRITELN(Y1)； END. 输入：23420 输出：,153,本题求y2超过x时y1的值,核心语句：
12、Y1：=Y1+1；Y3：=Y3+2；Y2：=Y2+Y3,关系：y2=(y1+1) 2 Y2超过x可写成(y1+1) 2 超过x，即求解： (y1+1) 2 23420中y1的最小值,例二(全国青少年信息学奥林匹克联赛模拟训练试卷精选),Var n,k,s:longint; begin n:=1000000000; k:=0; s:=1; while s=n do begin k:=k+1; n:=n-s; s:=s+6*k; end; writeln(k); end. 输出：,1000,列表分析,1 23-13 33-23 43-33,N=1000000000-k3 S=(k+1)3-k3 题
13、目要求循环结束条件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 sp110 do begin j:=j+1; p:=true; for i:=2 to j-1 do if (j mod i=0) then p:=fa
14、lse; if p then begin sp1:=sp1+1; asp1:=j; end; end;,j:=2; p:=true; while p do begin s:=1; for i:=1 to j do s:=s*ai; s:=s+1; for i:=2 to s-1 do if s mod i=0 then p:=false; j:=j+1; end; writeln(s); writeln; end. 输出：,30031,分析,前半段求10个素数依次存于数组a中 2 3 5 7 11 13 17 19 23 29 后半段求最小的j，使得前j个素数之积+1为合数 j=2 2*3+1
15、=7 j=3 2*3*5+1=31 j=4 2*3*5*7+1=211 j=5 2*3*5*7*11+1=2311 j=6 2*3*5*7*11*13+1=30031 小技巧：s为integer类型，预示着结果不会超过32767,program ex2; var i,j,n:longint; b:array 031 of 01; begin n=1999; i:=0; while n0 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
