模拟题解题参考

《模拟题解题参考》由会员分享，可在线阅读，更多相关《模拟题解题参考（9页珍藏版）》请在装配图网上搜索。

1、信息学奥赛复赛模拟题解题参考第一题交通流量测试(traffic)1第二题走楼梯(strair)5第三题津津的储蓄计划(save)6第四题合唱队形(chorus)9第五题均分纸牌(card)10第一题交通流量测试(traffic)【问题描述】为调查统计车辆流量，在路边设置了一台车辆探测器。探测信号用线路连接到计算机。凡有一辆车通过时，探测器自动传送一个数字信号1给计算机；探测器中有个2给计算机；统个程序，以处理探2给计算机；统个程序，以处理探时钟，统计开始时，启动时钟，此后每一秒钟自动传送一个数字信号计结束时，探测器向计算机发送一个数字为0的终止信号。编写测器送来的这一系列信息，并输出下列结果：

2、(1) 进行了多长时间的调查统计；(2) 记录到的车辆总数；(3) 在车辆之间最长的时间间隔是多少。【输入文件】输入文件traffic,in输入文件traffic,in包括一行整数(有且仅有最后一个整数为0),分别表示探测器发送给计算机的数字信口号。【输出文件】输出文件traffic,out包括三行，每行一个整数，分别表示调查统计的时间、记录到的车辆总数以及车辆间的最长时间间隔。【样例输入】1122111121222221111120【样例输出】9125解这些结果，要等到探测结束时才能统计完成。在程序中要使用到如下变量：过往车辆数，以标识符unms表示；时间以seconds表示；时间间隔以in

3、ter表示；最长时间间隔以longest表示；探测器信号以sig表示，分别为：1车辆信号、2计时信号、0结束统计信号。现在，我们开始学习用伪代码描述程序的开发过程。解决所提问题的程序设计过程，可表示如下：第一步把任务写成一个“总语句”：programbegin用车辆探测器统计车辆流量end.第二步把任务分解为几个子任务（功能块）:programbegin对有关变量赋以初值，准备开始统计；当送来的信号不是结束信号时，反复处理探测器送来的信号输出统计结果。end.第三步进一步细化各个子任务：programbegin若干个赋初值的赋值语句和读语句while送来信号不是结束信号时dobeginif是车

4、辆信号then处理车辆信号elseif是计时信号then处理计时信号；送下一个信号end；输出统计结果的若千写语句。end.具体第四步到目前这一步，赋初值与输出统计结果这两个子目标，已完全可以到用语句描述了，但while语句的循环体，尚须进一步细化到用语句描述。programbegin若干赋初值的赋值语句和读语句变量初始化whilesigOOdobeginifsig=lthenbegin车辆数nums的值增1;ifinterlongesttheninter的值取代longest的当前值；inter置零；endelseifsig=2thenbeginseconds的值增1,inter的值增1;送

5、下一个信号；endend；输出统计结果的若千写语句；end.第五步最终程序programtraffic;过往车辆数，以标识符unms表示；时间以seconds表示；时间间隔以inter表示；最长时间间隔以longest表示；探测器信号以sig表示，取值分别为：1车辆信号、2计时信号、0结束统计信号varunms,seconds,inter,longest,sig:integer;fl,f2:text;beginassign(fl,traffic.in，);assign(f2,traffic.out，);reset(fl);rewrite(f2);unms:二0;seconds:=0;inter

6、:=0;longest:=0;read(fl,sig);whilesigOOdobeginifsig=lthenbeginunms:=unms+l;ifinterlongestthenlongest:=inter;inter:=0;endelseifsig=2thenbeginseconds:二seconds+1;inter:=inter+l;end;read(fl,sig);end;writein(f2,seconds);writein(f2,unms);writein(f2,longest);close(fl);close(f2);end.当然细化过程分多少步并无定规，可因问题的简繁或程序

7、员编程技术的熟练程度而异。但不难看出，上述第一步做的是表达用户需求，第二步是进行总体设计(也称初步设计，即划分功能模块，并确定模块之间的组成关系，因此，也就是程序的结构设计)。第三、四步的工作则是模块设计(或称详细设计，是程序模块内的过程设计)，第五步就是编码工作。以上“五步”也称“五级”或“五个阶段”，各种称乎意思都大致相同。回头看一看，想一想之后，你可能提出异议：“编写这样几十行的短小程序，完全可以一气呵成。还要分四步、五步，进行什么分解、求精，不是多此一举吗？”是的，你的意见有一定道理，但你别忘记我们是在进行“方法学习”。是把小型程序当作大型程序的雏形。这样“小题大作”，目的是通过小型程

8、序的设计，模拟大型程序系统的开发步骤、原理、方法。著名计算机科学家格里斯(D.Gries)说过：“只有学会有效地编写小程序的人，才能学习有效地编写大程序。”其中的道理显而易见，不用多作解释。连小文章都写不好的人，难以设想他居然能完成优秀的宏篇巨著。第二题走楼梯(strair)【问题描述】某个楼梯共有n阶台阶，上楼可以一步上1阶，也可以一步上2阶，也可以一步上3阶，编一程序计算共有多少种不同的走法。【输入文件】输入文件strair.in包括一个整数n,分别楼梯的台阶级数。【输出文件】输出文件strair.out包括一个整数，表述走台阶的方法总数。【样例输入】3【样例输出】4解首先模拟一下走楼梯的

9、方法，如图所示：n=l时，方法f(n)=l；n=2时，方法f(n)=2；n=3时，方法f(n)=4；n=4时，方法f(n)=f(3)+f(2)+f(1)=7；同理可以推导出通项公式f(n)=f(n-1)+f(n-2)+f(n-3)LEEBSFFAHFHFIFTARIHffJTr一勻r有了这个通项公式(递推表达式)，可以很容易设计递归的方式解决问题。参考代码如下：programstrair;varn:integer;fl,f2:text;functionf(n:integer):integer;beginifn=lthenf:=1;ifn=2thenf:=2;ifn=3thenf:=4;ifn=

10、4thenf:=f(nT)+f(n-2)+f(n-3);end;beginassign(fl,strair.inJassign(f2,strair.out);reset(fl);rewrite(f2);read(fl,n);writein(f2,f(n);close(fl);close(f2);end.第三题津津的储蓄计划(save)【问题描述】津津的零花钱一直都是自己管理。每个月的月初妈妈给津津300元钱，津津会预算这个月的花销，并且总能做到实际花销和预算的相同。为了让津津学习如何储蓄，妈妈提出，津津可以随时把整百的钱存在她那里，到了年末她会加上20%还给津津。因此津津制定了一个储蓄计划：每

11、个月的月初，在得到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于100元或恰好100元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。例如11月初津津手中还有83元，妈妈给了津津300元。津津预计11月的花销是180元，那么她就会在妈妈那里存200元，自己留下183元。到了11月月末，津津手中会剩下3元钱。津津发现这个储蓄计划的主要风险是，存在妈妈那里的钱在年末之前不能取出。有可能在某个月的月初，津津手中的钱加上这个月妈妈给的钱，不够这个月的原定预算。如果出现这种情况，津津将不得不在这个月省吃俭用，压缩预算。现在请你根据2007年1月到12月每个月津津的预算，判断会不会出现这种

12、情况。如果不会，计算到2007年年末，妈妈将津津平常存的钱加上20%还给津津之后，津津手中会有多少钱。【输入文件】输入文件save,in包括12行数据，每行包含一个小于350的非负整数，分别表示1月到12月津津的预算。【输出文件】输出文件save,out包括一行，这一行只包含一个整数。如果储蓄计划实施过程中出现某个月钱不够用的情况，输出-X,X表示出现这种情况的第一个月；否则输出到2007年年末津津手中会有多少钱。【样例输入1】29023028020030017034050908020060【样例输出117【样例输入2】29023028020030017033050908020060【样例输出

13、2】1580解这是近年分区联赛当中最简单的题，算法也很简单：模拟法。每个月把津津手上的钱加上妈妈给的300元，再减去预算，得到当前手中的钱，假如这个钱的值是负数(出现亏损)，那么就输出负的月数，接着算出存入的钱，并且将手中的钱减去。如此往复，直到最后按要求输出结果或者中间已经停止。参考代码如下：programsave;vara:array1.12ofinteger;have,s,x,temp,i:integer;fl,f2:text;b:Boolean;beginassign(fl,save,in);assign(f2,save,out);reset(fl);rewrite(f2);fori:

14、=1to12doread(fl,ai);b:=True;x:=0;have:=0;s:=0;fori:=1to12dobegintemp:=have+300-ai;iftemp0thenbeginx:=i;b:=false;endelsebegins:=s+tempdiv100*100;have:=tempmod100;end;end;ifnotbthenwritein(f2,-x)elsewritein(f2,truncCsU2)+have);close(fl);close(f2);end.第四题合唱队形(chorus)【问题描述】N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使

15、得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1,2，K,他们的身高分别为Tl,T2，TK,则他们的身高满足Tlv.Ti+l.TK(lv=iv=K)o你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。【输入文件】输入文件chorus.in的第一行是一个整数N(2=N=100),表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(130=Ti=230)是第i位同学的身高(厘米)。【输出文件】输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。【样例输入】81861861

16、50200160130197220【样例输出】4【数据规模】对于50%的数据，保证有n=20；对于全部的数据，保证有n=100o解假设每个人为中间身高最高的人(可以用循环枚举)，要使出列的人数最小，即这个人的左边和右边都有尽可能多的人。此人左右两边分别满足严格上升和下降的关系，且人数最多。首先求出最长连续序列，从左向右看升序的数目，左边升序的最大值记做upi；同样循环枚举，右边降序的最大值记做downi然后，枚举每个人i,有kj=upi+downi-l,记录下最大的k值，minans=n-maxki就是出列的最小数目。参考代码如下：programchorus;vart:array0.,101o

17、flongint;up,down:array0.101oflongint;n,i,j,k,max:integer;fl,f2:text;beginassign(fl,chorus.in，);assign(f2,chorus.out，);reset(fl);rewrite(f2);readln(fl,n);读入升身高数据fori:=ltondoread(fl,ti);t0:二0;tn+1:=0;fori:=0ton+1doupi:=0;fori:=0ton+1dodowni:=0;/左侧升序最大fori:=ltondobeginmax:=l;forj:=0toildoif(tjti)and(ma

18、xupj+l)thenmax:=upj+l;upi:=max;end;/左侧降序最大fori:=ndownto1dobeginmax:=l;forj:二n+1downtoi+1doif(tjti)and(maxdownj+l)thenmax:=downj+l;downi:=max;end;/求出满足条件的最大kk:=0;fori:=ltondoifk从取3张牌放到(9111010)从取1张牌放到(10101010)。【输入文件】输入文件card.in包含两行正整数，第一行只有一个正整数N表示纸牌堆数(l=N=100),第二行包含N个用空格隔开的正整数(在1到10000之间)，分别表示每堆纸牌的

19、初始张数。【输入文件】输出文件card.out包含一个正整数，表示所有堆均达到相等时的最少移动次数。【输入样例】498176【输出样例】3解如果你想到把每堆牌的张数减去平均张数，题目就变成移动正数，加到负数中，使大家都变成0,那就意味着成功了一半！因为这样可以简化思考难度。例题中，平均张数为(9+8+17+6)/4=10,原张数9,8,17,6,变为-1,-2,7,-4,其中没有为0的数。我们从左边出发：要使第1堆的牌数-1变为0,只须将-1张牌移到它的右边(第2堆)-2中；结果是-1变为0,-2变为-3,各堆牌张数变为0,-3,7,-4；同理：要使第2堆变为0,只需将-3移到它的右边(第3堆

20、)中去，各堆牌张数变为0,0,4,-4；要使第3堆变为0,只需将第3堆中的4移到它的右边(第4堆)中去，结果为0,0,0,0,完成任务。每移动1次牌，步数加1。也许你要问，负数张牌怎么移，不违反题意吗？其实从第i堆移动-m张牌到第i+1堆，等价于从第i+1堆移动m张牌到第i堆，尽管方向不一样，但是步数是一样的。如果张数中本来就有为0的，怎么办呢？如0,-1,-5,6,还是从左算起(从右算起也完全一样)，第1堆是0,则无需移牌，余下与上相同；再比如-1,-2,3,10,-4,-6,从左算起，第1次移动的结果为0,-3,3,10,-4,-6；第2次移动的结果为0,0,0,10,-4,-6,现在第3

21、堆已经变为0了，可节省1步，余下继续。本题有三点比较关键：一是善于将每堆牌数减去平均数，简化了问题；二是要过滤掉0(不是所有的0,如-2,3,0,-1中的0是不能过滤的)；三是负数张牌也可以移动，这是辩证法思维。参考代码如下：programcard;constmaxn=100;vari,j,n,step:integer;ave:longint;a:array1.maxnofinteger;fl,f2:text;beginassign(fl,card.in，);assign(f2,card.out);reset(fl);rewrite(f2);readln(fl,n);ave:=0;step:=

22、0;fori:=ltondobeginread(fl,ai);inc(ave,ai);end;ave:=avedivn;fori:=1tondoai:=ai-ave;j：=n;whileai=0doinc(i);whileaj=0dodec(j);while(ij)do过滤左边的0过滤右边的0begininc(ai+l,ai);将第i堆牌移到第i+1堆中去ai：=0；第i堆牌移走后变为0inc(step);移牌步数计数inc(i);对下一堆牌进行循环操作whileai=0doinc(i);过滤移牌过程中产生的0end;writein(f2,step);close(fl);close(f2);end.