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

NOIP初赛阅读程序解题方法,解题步骤,做阅读程序题，首先要想方设法弄清楚程序的功能，每个题目总有一点“写作目的”。抓住了它，不仅答案变得容易了，而且对自己的结果也比较有信心。1、从总体上通读程序，大致把握程序的目的和算法。2、猜测变量的作用，跟踪主要变量值的变化(列表)，找出规律。3、将程序分段，理清每一小段程序的作用和目的。4、看清输入，按照输出格式，写出结果。5、带着到的结果回到程序进行检查。,几大方法,a.直接模拟b.先模拟几次循环后找规律c.直接看程序了解算法功能d.了解程序本质后换一个方法解决e.有时不知道算法可以通过观察猜出来,一、基础题,送分题，主要考查选手的程序设计基础知识和计算能力。细心Programex301;varu:array0.3ofinteger;i,a,b,x,y:integer;beginy:=10;fori:=0to3doread(ui);a:=(u0+u1+u2+u3)div7;b:=u0div(u1-u2)divu3);x:=(u0+a+2)-u(u3+3)mod4;if(x10)theny:=y+(b*100-u3)div(uu0mod3*5)elsey:=y+20+(b*100-u3)div(uu0mod3*5);writeln(x,y);end.*注：本例中，给定的输入数据可以避免分母为0或下标越界。输入：9394输出：,注意事项,1、负数整除、求模表达式(4mod(-3)与(-4mod3)的值为()A.-1,-1B.1,-1C.-1,1D.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是英文单词squareroot（平方根）的缩写,函数二：类型转换函数,取整数函数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、数字之间的andornotxor运算：将数字化为二进制，1为true，0为false，逐位运算，结果再化为10进制。2、移位运算:shlshrxshly=x*2yxshry=xdiv2y3、地址运算：4、逻辑运算：设A=B=True，C=D=False，一下逻辑运算表达式值为假的有（）。A(AB)(CDA)B(AB)C)D)CA(BCD)DD(A(DC)B,看程序写结果(NOIP2007),programj302;vara,b:integer;varx,y:integer;procedurefun(a,b:integer);vark:integer;begink:=a;a:=b;b:=k;end;begina:=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，那么集合ABC为（）。(NOIP2005普及)A.c,eB.d,eC.eD.c,d,eE.d,f为补集符号,A,NOIP2004普及组,75名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已知其中20人这三种东西都玩过，55人至少玩过其中的两种。若每样乘坐一次的费用是5元，游乐场总共收入700，可知有名儿童没有玩过其中任何一种。,10,二、动态模拟,找不出其中的规律，也看不出明显的算法，便可以尝试进行动态模拟。动态模拟是采用人工模仿机器执行程序的方法计算结果。首先选择比较重要的变量作为工作现场。人工执行程序时，只要按照时间先后一步步记录现场的变化，就能最后得出程序的运算结果。1、画表，画出程序执行时要用的现场情况表。2、基本读懂各语句的功能。3、动态执行程序,programt1；varn，k，s：longint；beginreadln(n);k:=0；s:=1；whiles1000000000-k3中k的最小值,四、算法题,考查选手对一些常用的算法的熟练掌握情况，关于素数的判定、排序、高精度、进制转换、几何等算法题比较多。programGxp2;vari,j,s,sp1:integer;p:boolean;a:array1.10ofinteger;beginsp1:=1;a1:=2;j:=2;whilesp110dobeginj:=j+1;p:=true;fori:=2toj-1doif(jmodi=0)thenp:=false;ifpthenbeginsp1:=sp1+1;asp1:=j;end;end;,j:=2;p:=true;whilepdobegins:=1;fori:=1tojdos:=s*ai;s:=s+1;fori:=2tos-1doifsmodi=0thenp:=false;j:=j+1;end;writeln(s);writeln;end.输出：,30031,分析,前半段求10个素数依次存于数组a中2357111317192329后半段求最小的j，使得前j个素数之积+1为合数j=22*3+1=7j=32*3*5+1=31j=42*3*5*7+1=211j=52*3*5*7*11+1=2311j=62*3*5*7*11*13+1=30031小技巧：s为integer类型，预示着结果不会超过32767,programex2;vari,j,n:longint;b:array0.31of0.1;beginn=1999;i:=0;whilen0dobeginbi:=nmod2;i:=i+1;n:=ndiv2end;forj:=i-1downto0dowrite(bj);end.,很明显，是把十进制整数转换成二进制数，所以输出11111001111,五、子程序,NOIP1998提高2CONSTN=10;VARS,I:INTEGER;FUNCTIONCO(I1:INTEGER):INTEGER;VARJ1,S1:INTEGER;BEGINS1:=N;FORJ1:=(N-1)DOWNTO(N-I1+1)DOS1:=S1*J1DIV(N-J1+1);CO:=S1;END;BEGINS:=N+1;FORI:=2TONDOS:=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,PROGRAMGAO7_1：FUNCTIONACK(M，N：INTEGER)：INTEGER；BEGIN