您好,欢迎来到锐游网。
搜索
您的当前位置:首页模拟题解题参考

模拟题解题参考

来源:锐游网
 信息学奥赛复赛模拟题解题参考 第 1 页 共 12 页

信息学奥赛复赛模拟题解题参考

第一题 交通流量测试(traffic) ............................................................................................ 1 第二题 走楼梯(strair) .......................................................................................................... 5 第三题 津津的储蓄计划(save) .............................................................................................. 6 第四题 合唱队形 (chorus) ........................................................................................................ 9 第五题 均分纸牌(card) ......................................................................................................... 10

第一题 交通流量测试(traffic) 【问题描述】

为调查统计车辆流量,在路边设置了一台车辆探测器。探测信号用线路连接到计算机。凡有一辆车通过时,探测器自动传送一个数字信号1给计算机;探测器中有个时钟,统计开始时,启动时钟,此后每一秒钟自动传送一个数字信号2给计算机;统计结束时,探测器向计算机发送一个数字为0的终止信号。编写一个程序,以处理探测器送来的这一系列信息,并输出下列结果:

(1)进行了多长时间的调查统计; (2)记录到的车辆总数;

(3)在车辆之间最长的时间间隔是多少。 【输入文件】

输入文件traffic.in包括一行整数(有且仅有最后一个整数为0),分别表示探测器发送给计算机的数字信号。 【输出文件】

输出文件traffic.out包括三行,每行一个整数,分别表示调查统计的时间、记录到的车辆总数以及车辆间的最长时间间隔。 【样例输入】

1 1 2 2 1 1 1 1 2 1 2 2 2 2 2 1 1 1 1 1 2 0 【样例输出】 9 12 5

[解]这些结果,要等到探测结束时才能统计完成。在程序中要使用到如下变量: 过往车辆数,以标识符unms表示; 时间以seconds表示; 时间间隔以inter表示;

最长时间间隔以longest表示;

探测器信号以sig表示,分别为:1 车辆信号、2 计时信号、0 结束统计信号。

现在,我们开始学习用伪代码描述程序的开发过程。解决所提问题的程序设计过程,可表示如下:

第一步 把任务写成一个“总语句”: program begin

信息学奥赛复赛模拟题解题参考 第 2 页 共 12 页

用车辆探测器统计车辆流量 end.

第二步 把任务分解为几个子任务(功能块): program begin

对有关变量赋以初值,准备开始统计;

当送来的信号不是结束信号时,反复处理探测器送来的信号; 输出统计结果。 end.

信息学奥赛复赛模拟题解题参考 第 3 页 共 12 页

第三步 进一步细化各个子任务: program begin

若干个赋初值的赋值语句和读语句 while送来信号不是结束信号时 do begin

if是车辆信号

then处理车辆信号 else if是计时信号

then处理计时信号;

送下一个信号 end;

输出统计结果的若干写语句。 end.

第四步 到目前这一步,赋初值与输出统计结果这两个子目标,已完全可以具体到

用语句描述了,但while语句的循环体,尚须进一步细化到用语句描述。 program begin

若干赋初值的赋值语句和读语句 {变量初始化} while sig<>0 do begin

if sig=1 then begin

车辆数nums的值增1; if inter>longest

then inter的值取代longest的当前值;

inter置零; end

else if sig=2 then begin

seconds的值增1,inter的值增1; 送下一个信号; end end;

输出统计结果的若干写语句; end.

信息学奥赛复赛模拟题解题参考 第 4 页 共 12 页

第五步 最终程序 program traffic; {

过往车辆数,以标识符unms表示; 时间以seconds表示; 时间间隔以inter表示;

最长时间间隔以longest表示;

探测器信号以sig表示,取值分别为:1 车辆信号、2 计时信号、0 结束统计信号。 } var

unms,secondS,inter,longest,sig:integer; f1,f2:text; begin

assign(f1,'traffic.in'); assign(f2,'traffic.out'); reset(f1); rewrite(f2); unms:=0; secondS:=0; inter:=0; longest:=0; read(f1,sig); while sig<>0 do begin

if sig=1 then begin

unms:=unms+1;

if inter>longest then longest:=inter; inter:=0; end

else if sig=2 then begin

seconds:=seconds+1; inter:=inter+1; end; read(f1,sig); end;

writeln(f2,seconds); writeln(f2,unms); writeln(f2,longest); close(f1); close(f2); end.

信息学奥赛复赛模拟题解题参考 第 5 页 共 12 页

当然细化过程分多少步并无定规,可因问题的简繁或程序员编程技术的熟练程度而异。但不难看出,上述第一步做的是表达用户需求,第二步是进行总体设计(也称初步设计,即划分功能模块,并确定模块之间的组成关系,因此,也就是程序的结构设计)。第三、四步的工作则是模块设计(或称详细设计,是程序模块内的过程设计),第五步就是编码工作。以上“五步”也称“五级”或“五个阶段”,各种称乎意思都大致相同。

回头看一看,想一想之后,你可能提出异议:“编写这样几十行的短小程序,完全可以一气呵成。还要分四步、五步,进行什么分解、求精,不是多此一举吗?”是的,你的意见有一定道理,但你别忘记我们是在进行“方法学习”。是把小型程序当作大型程序的雏形。这样“小题大作”,目的是通过小型程序的设计,模拟大型程序系统的开发步骤、原理、方法。 著名计算机科学家格里斯(D.Gries)说过:“只有学会有效地编写小程序的人,才能学习有效地编写大程序。”其中的道理显而易见,不用多作解释。连小文章都写不好的人,难以设想他居然能完成优秀的宏篇巨著。

第二题 走楼梯(strair) 【问题描述】

某个楼梯共有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,也可以一步上3阶,编一程序计算共有多少种不同的走法。 【输入文件】

输入文件strair.in包括一个整数n,分别楼梯的台阶级数。 【输出文件】

输出文件strair.out包括一个整数,表述走台阶的方法总数。 【样例输入】 3

【样例输出】 4

[解]首先模拟一下走楼梯的方法,如图所示: n=1时,方法f(n)=1; 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);

信息学奥赛复赛模拟题解题参考 第 6 页 共 12 页

有了这个通项公式(递推表达式),可以很容易设计递归的方式解决问题。参考代码如下: program strair; var

n:integer; f1,f2:text;

function f(n:integer):integer; begin

if n=1 then f:=1; if n=2 then f:=2; if n=3 then f:=4;

if n>=4 then f:=f(n-1)+f(n-2)+f(n-3); end;

begin

assign(f1,'strair.in'); assign(f2,'strair.out'); reset(f1); rewrite(f2); read(f1,n);

writeln(f2,f(n)); close(f1); close(f2); end.

第三题 津津的储蓄计划(save) 【问题描述】

津津的零花钱一直都是自己管理。每个月的月初妈妈给津津300元钱,津津会预算这个月的花销,并且总能做到实际花销和预算的相同。

为了让津津学习如何储蓄,妈妈提出,津津可以随时把整百的钱存在她那里,到了年末她会加上20%还给津津。因此津津制定了一个储蓄计划:每个月的月

信息学奥赛复赛模拟题解题参考 第 7 页 共 12 页

初,在得到妈妈给的零花钱后,如果她预计到这个月的月末手中还会有多于100元或恰好100元,她就会把整百的钱存在妈妈那里,剩余的钱留在自己手中。

例如11月初津津手中还有83元,妈妈给了津津300元。津津预计11月的花销是180元,那么她就会在妈妈那里存200元,自己留下183元。到了11月月末,津津手中会剩下3元钱。

津津发现这个储蓄计划的主要风险是,存在妈妈那里的钱在年末之前不能取出。有可能在某个月的月初,津津手中的钱加上这个月妈妈给的钱,不够这个月的原定预算。如果出现这种情况,津津将不得不在这个月省吃俭用,压缩预算。

现在请你根据2007年1月到12月每个月津津的预算,判断会不会出现这种情况。如果不会,计算到2007年年末,妈妈将津津平常存的钱加上20%还给津津之后,津津手中会有多少钱。 【输入文件】

输入文件save.in包括12行数据,每行包含一个小于350的非负整数,分别表示1月到12月津津的预算。 【输出文件】

输出文件save.out包括一行,这一行只包含一个整数。如果储蓄计划实施过程中出现某个月钱不够用的情况,输出-X,X表示出现这种情况的第一个月;否则输出到2007年年末津津手中会有多少钱。 【样例输入1】 290 230 280 200 300 170 340 50 90 80 200 60

【样例输出1】 -7

【样例输入2】 290 230 280 200 300 170 330 50 90 80

信息学奥赛复赛模拟题解题参考 第 8 页 共 12 页

200 60

【样例输出2】 1580

[解]这是近年分区联赛当中最简单的题,算法也很简单:模拟法。 每个月把津津手上的钱加上妈妈给的300元,再减去预算,得到当前手中的钱,假如这个钱的值是负数(出现亏损),那么就输出负的月数,接着算出存入的钱,并且将手中的钱减去。如此往复,直到最后按要求输出结果或者中间已经停止。参考代码如下: program save; var

a:array[1..12] of integer; have,s,x,temp,i:integer; f1,f2:text; b:Boolean; begin

assign(f1,'save.in'); assign(f2,'save.out'); reset(f1); rewrite(f2);

for i:=1 to 12 do read(f1,a[i]); b:=True; x:=0; have:=0; s:=0;

for i:=1 to 12 do begin

temp:=have+300-a[i]; if temp<0 then begin x:=i; b:=false; end else begin

s:=s+temp div 100*100; have:=temp mod 100; end; end;

if not b then writeln(f2,-x) else writeln(f2,trunc(s*1.2)+have); close(f1); close(f2); end.

信息学奥赛复赛模拟题解题参考 第 9 页 共 12 页

第四题 合唱队形 (chorus) 【问题描述】

N位同学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩下的K位同学排成合唱队形。

合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1,2„,K,他们的身高分别为T1,T2,„,TK, 则他们的身高满足T1<...Ti+1>…>TK(1<=i<=K)。

你的任务是,已知所有N位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。 【输入文件】

输入文件chorus.in的第一行是一个整数N(2<=N<=100),表示同学的总数。第一行有n个整数,用空格分隔,第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。 【输出文件】

输出文件chorus.out包括一行,这一行只包含一个整数,就是最少需要几位同学出列。 【样例输入】 8

186 186 150 200 160 130 197 220 【样例输出】 4

【数据规模】

对于50%的数据,保证有n<=20; 对于全部的数据,保证有n<=100。

[解]假设每个人为中间身高最高的人(可以用循环枚举),要使出列的人数最小,即这个人的左边和右边都有尽可能多的人。此人左右两边分别满足严格上升和下降的关系,且人数最多。

首先求出最长连续序列,从左向右看升序的数目,左边升序的最大值记做up[i];同样循环枚举,右边降序的最大值记做down [i]。

然后,枚举每个人i,有 ki=up[i]+down[i]-1,记录下最大的k值,minans=n-maxki 就是出列的最小数目。

参考代码如下: program chorus; var

t:array[0..101] of longint;

up,down:array[0..101] of longint; n,i,j,k,max:integer; f1,f2:text; begin

assign(f1,'chorus.in'); assign(f2,'chorus.out'); reset(f1);

信息学奥赛复赛模拟题解题参考 第 10 页 共 12 页

rewrite(f2); readln(f1,n); //读入升身高数据

for i:=1 to n do read(f1,t[i]); t[0]:=0; t[n+1]:=0;

for i:=0 to n+1 do up[i]:=0; for i:=0 to n+1 do down[i]:=0; //左侧升序最大 for i:=1 to n do begin

max:=1;

for j:=0 to i-1 do

if (t[j]//左侧降序最大

for i:=n downto 1 do begin

max:=1;

for j:=n+1 downto i+1 do

if (t[j]//求出满足条件的最大k k:=0;

for i:=1 to n do

if k第五题 均分纸牌(card) 【问题描述】

有 N 堆纸牌,编号分别为 1,2,„, N。每堆上有若干张,但纸牌总数必为 N 的倍数。可以在任一堆上取若于张纸牌,然后移动。

移牌规则为:在编号为 1 堆上取的纸牌,只能移到编号为 2 的堆上;在编号为 N 的堆上取的纸牌,只能移到编号为 N-1 的堆上;其他堆上取的纸牌,可以移到相邻左边或右边的堆上。

现在要求找出一种移动方法,用最少的移动次数使每堆上纸牌数都一样多。 例如 N=4,4 堆纸牌数分别为:

信息学奥赛复赛模拟题解题参考 第 11 页 共 12 页

① 9 ② 8 ③ 17 ④ 6 移动3次可达到目的:从 ③ 取 4 张牌放到 ④ (9 8 13 10)—> 从 ③ 取 3 张牌放到 ②(9 11 10 10)—> 从 ② 取 1 张牌放到①(10 10 10 10)。 【输入文件】

输入文件card.in 包含两行正整数,第一行只有一个正整数N表示纸牌堆数(1<=N<=100),第二行包含N个用空格隔开的正整数(在1到10000之间),分别表示每堆纸牌的初始张数。 【输入文件】

输出文件card.out 包含一个正整数,表示所有堆均达到相等时的最少移动次数。

【输入样例】 4

9 8 17 6 【输出样例】

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堆)中去,各堆牌张数变为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堆已经变为0了,可节省1步,余下继续。

本题有三点比较关键:一是善于将每堆牌数减去平均数,简化了问题;二是要过滤掉0(不是所有的0,如-2,3,0,-1中的0是不能过滤的);三是负数张牌也可以移动,这是辩证法思维。 参考代码如下: program card; const maxn=100; var

i,j,n,step:integer; ave:longint;

a:array[1..maxn]of integer; f1,f2:text;

信息学奥赛复赛模拟题解题参考 第 12 页 共 12 页

begin

assign(f1,'card.in'); assign(f2,'card.out'); reset(f1); rewrite(f2); readln(f1,n); ave:=0; step:=0;

for i:=1 to n do begin

read(f1,a[i]); inc(ave,a[i]); end;

ave:=ave div n;

for i:=1 to n do a[i]:=a[i]-ave; i:=1; j:=n;

while a[i]=0 do inc(i);{过滤左边的0} while a[j]=0 do dec(j);{过滤右边的0} while (iinc(a[i+1],a[i]);{将第i堆牌移到第i+1堆中去} a[i]:=0;{第i堆牌移走后变为0} inc(step);{移牌步数计数}

inc(i);{对下一堆牌进行循环操作}

while a[i]=0 do inc(i);{过滤移牌过程中产生的0} end;

writeln(f2,step); close(f1); close(f2); end.

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- ryyc.cn 版权所有 湘ICP备2023022495号-3

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务