NOIP初赛阅读程序解题方法

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输出：,10,10,关键语句,b:=u0div(u1-u2)divu3);y:=y+20+(b*100-u3)div(uu0mod3*5);变量值：Y=10u0=9u1=3u2=9u3=4A=3b=-9x=10y=10,注意事项,1、负数整除、求模表达式(4mod(-3)与(-4mod3)的值为()A.-1,-1B.1,-1C.-1,1D.1,1(-14)mod(-3)=()模运算的规律：结果与被除数的符号相同。即被除数为正，模为正，否则为负。结果与除数的符号没有关系,B,programs401;varp,q:array0.5ofinteger;i,x,y:integer;beginy:=20;fori:=0to4doread(p);readln;q0:=(p0+p1)+(p2+p3+p4)div7;q1:=p0+p1div(p2+p3)divp4);q2:=p0*p1divp2;q3:=q0*q1;q4:=q1+q2+q3;x:=(q0+q4+2)-p(q3+3)mod4;If(x10)Theny:=y+(q1*100-q3)div(pp4mod3*5)Elsey:=y+20+(q2*100-q3)div(pp4mod3*5);writeln(x,y);end.输入：66553输出：,129,43,Programex401;varu,v:array0.3ofinteger;i,x,y:integer;beginx:=10;y:=10;fori:=0to3doread(ui);v0:=(u0+u1+u2+u3)div7;v1:=u0div(u1-u2)divu3);v2:=u0*u1divu2*u3;v3:=v0*v1;x:=(v0+v1+2)-u(v3+3)mod4;if(x10)theny:=y+(v2*100-v3)div(uu0mod3*5)elsey:=y+20+(v2*100-v3)div(uv0mod3*5);writeln(x,y);end.*注：本例中，给定的输入数据可以避免分母为0或下标越界。输入：9394输出：,-13，57,函数一：算术函数,求绝对值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),programs402;vara,b:integer;x,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);write(No.1:,a,b,);fun(a,b);writeln(No.2:,a,b);end.,No.1:3,6No.2:3,6,集合运算,设全集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;whilesp10)thenbeginn2:=nmod10;write(n2:2);if(m1)thendigit(ndiv10,mdiv10);n2:=nmod10;write(n2:2);end;end;beginwriteln(Inputanumber:);readln(x);x2:=1;while(x2x)dox2:=x2*10;x2:=x2div10;digit(x,x2);writeln;end.输入：9734526输出：,Inputanumber:62543799734526,programS403;vara1:array1.50ofinteger;vari,j,t,t2,n,n2:integer;beginn:=50;fori:=1tondoa1:=0;n2:=round(sqrt(n);fori:=2ton2doIf(a1=0)Thenbegint2:=ndivi;forj:=2tot2doa1i*j:=1;end;t:=0;fori:=2tondoIf(a1=0)Thenbeginwrite(i:4);inc(t);if(tmod10=0)thenwriteln;end;writeln;end.输出：,五、子程序,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：f