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

NOIP初赛阅读程序解题方法,解题步骤,做阅读程序题，首先要想方设法弄清楚程序的功能，每个题目总有一点“写作目的”。抓住了它，不仅答案变得容易了，而且对自己的结果也比较有信心。1、从总体上通读程序，大致把握程序的目的和算法。2、猜测变量的作用，跟踪主要变量值的变化(列表)，找出规律。3、将程序分段，理清每一小段程序的作用和目的。4、看清输入，按照输出格式，写出结果。5、带着到的结果回到程序进行检查。,几大方法,a.直接模拟b.先模拟几次循环后找规律c.直接看程序了解算法功能d.了解程序本质后换一个方法解决e.有时不知道算法可以通过观察猜出来,一、基础题,送分题，主要考查选手的程序设计基础知识和计算能力。细心Program ex301;varu:array0.3 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的自然对数，即logeXPascal中无幂运算，要求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,函数四：字符串函数,字符串过程,特殊运算,1、数字之间的and or not xor 运算：将数字化为二进制，1为true，0为false，逐位运算，结果再化为10进制。2、移位运算:shl shr x shl y=x*2y x shr y=x div 2 y3、地址运算：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;begink:=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,eC.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=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；BEGINREADLN(P)；FOR Q:=P+1 TO 2*P DOBEGINT:=0；S:=(P*Q)MOD(Q-P)；IF S=0 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 1.100 of integer;n,i,j,k,x,s:integer;begin n:=5;a1:=1;d1:=1;for i:=1 to n dobegin s:=i+1;x:=0;for j:=1 to n+1-i do begin 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；BEGINREADLN(X)；Y1：=0；Y2：=1；Y3：=1；WHILE Y2=X DOBEGINY1：=Y1+1；Y3：=Y3+2；Y2：=Y2+Y3 END；WRITELN(Y1)；END.输入：23420输出：,153,本题求y2超过x时y1的值,核心语句：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,列表分析,123-1333-2343-33,N=1000000000-k3S=(k+1)3-k3题目要求循环结束条件sn时k的值，即求：(k+1)3-k31000000000-k3中k的最小值,四、算法题,考查选手对一些常用的算法的熟练掌握情况，关于素数的判定、排序、高精度、进制转换、几何等算法题比较多。program Gxp2;var i,j,s,sp1:integer;p:boolean;a:array1.10 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:=false;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=7j=3 2*3*5+1=31j=4 2*3*5*7+1=211j=5 2*3*5*7*11+1=2311j=6 2*3*5*7*11*13+1=30031小技巧：s为integer类型，预示着结果不会超过32767,program ex2;var i,j,n:longint;b:array 0.31 of 0.1;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.,很明显，是把十进制整数转换成二进制数，所以输出,五、子程序,NOIP1998 提高2CONST 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；BEGINIF M=0 THEN ACK：=N+1ELSE IF N=0 THEN ACK:=ACK(M-1，1)ELSE ACK:=ACK(M-1，ACK(M，N-1)END；BEGIN WRITELN(ACK(3，4)；READLN；END.输出,分析,若直接利用递归定义自顶向下计算，展开的式子将非常长，且非常容易出错。可通过表格自底向上进行计算。,n+1n+22*n+32(n+3)-3,