设为首页 | 加入收藏夹

1996年美国计算机程序设计选拔赛试题

2012/6/2 18:17:59 作者:计算机基础知识试题 录入:应序康 访问:6761 次 被顶:1 次 字号:【
摘要:第一题: 给奶牛挤奶 三个农夫每天早晨五点起床,去牛圈给三头奶牛挤奶。第一个农夫挤奶的时间是从300 到 1000 (从五点开始用秒来作单位) ,第二个农夫的时间是从 700 到 1200,第三个农夫的时间是从 1500 到 2100。由上...
第一题: 给奶牛挤奶
    三个农夫每天早晨五点起床,去牛圈给三头奶牛挤奶。第一个农夫挤奶的时间是从
300 到 1000 (从五点开始用秒来作单位) ,第二个农夫的时间是从 700 到 1200,第三个农
夫的时间是从 1500 到 2100。
由上可知,至少有一个农夫在挤奶的最长连续时间段为 900 秒(从 300 到 1200 ) ,从
开始挤奶到结束,没有农夫在挤奶的最长连续时间段为 300 秒(从 1200 到 1500)。
你的任务是写出一个程序,对于给出的 n 个农夫给 n 头奶牛挤奶的起始时间和最后
时间(以秒为单位) ,计算:
① 至少有一个农夫在挤奶的最长连续时间段;
② 没有农夫在挤奶的最长连续时间段。
程序必须从输入文件: INPUT .C1 中读入数据,并将结果输出到屏幕上。输入文件
的第一行是一个整数 n 代表农夫数( n≤32000 ) ,以下 n行包含起始时间和结束时间(从五
点开始用秒来作单位) ,这些数值是 0 到 32000 的整数。
输入举例:
3
300     1000
700 1200
1500 2100
输出举例:
Longest continuous time = 900
Longest idle time = 300
第二题: 谷仓迷宫
对于一个非常奇怪的谷仓,它包含 p个厩( stall ) ,其中 p 是小于 2500 的质数,每个厩
有一个 ID 号码。例如,一个有 11 个厩的谷仓,它们对应的号码为 0~10。一个人按下列
移动规则在这些厩间走动:
北( stall) = (4 * stall + 7) MOD 11
南( stall) = (3 * stall + 1) MOD 11
东( stall) = (5 * stall + 10 ) MOD 11
西( stall) = (9 * stall + 9) MOD 11
如果他在号码为 7 的厩中则他能移动:
( n: 2)向北到 2 号厩( s:0 )向南到 0 号厩,
( e: 1 )向东到 1 号厩( w: 6 )向西到 6 号厩。
0, 1, 2 和 6 号厩中的每一个与 7 号厩的距离都是 1。有的时候两个或多个门会通向
· 4 3 ·同一个房间。可喜的是,如果一个人向北从 7 到 2 号厩,则他向南从 2 会回到 7 号厩。
给出厩的数目和上面的公式,找出一个中心厩。一个中心厩到达其他厩的最短距离
的平均值最小(注意上面的例子)。
输出: 中心厩的号码和平均距离的长度(保留 4 位小数)。
你的程序在 Pentium/ 90 上运行时间应不超过 30 秒。
每组数据是由 9 个数字组成的文本文件,质数 p 和公式的8 个对应参数(b * stall + c)
MOD p(北 南 东 西) ,下面是上面例子的输入数据:
11 4 7 3 1 5 10 9 9
下面是这 11 个厩的相邻厩:
0   e: 10   w:9     n :7     s:1         6   e :7   w:8   n:9   s:8
1 e: 4 w:7 n :0 s:4 7 e :1 w:6 n:2 s:0
2 e: 9 w:5 n :4 s:7 8 e :6 w:4 n:6 s:3
3 e: 3 w:3 n :8 s:10 9 e :0 w:2 n:10 s:6
4 e: 8 w:1 n :1 s:2 10 e :5 w:0 n:3 s:9
5 e: 2 w:10 n :5 s:5
考虑从 1 号厩出发:
距离 1: 你能从 1 号厩一步到达 4 ,7 ,0 号厩,所以我们称这些厩的距离为 1。
距离2 : 这些是所有能恰好两步到达的厩,所以我们找出从距离为 1 的厩能到达哪些
厩。从 4 号厩能到达 8, 1, 2;从 7 号厩能到达 1 ,6 ,2 , 0;从 0 号厩能到达 10, 9 , 7, 1。将这
些合起来, 0, 1, 2, 6, 7, 8, 9, 10 可以两步到达,但是 1 号厩是出发点而且到 0 和 7 号厩存
在更短的路,所以只剩下 2, 6, 8, 9 号距离为 2。
距离 3: 类似的,我们能找出 3 号和 5 号厩距离为 3(我们已经到达所有的厩)。
下面的表统计了最短路的结果:
Dist .       stalls
  1   3
  2   5
  3   2
在上表中, ‘Dist’ 表示到其他厩的最短距离, ‘Stalls’ 表示最短距离为 ‘Dist’ 的厩的个
数。上表还提供了平均距离的长度(1 * 3 + 2 * 5 + 3 * 2)/ 10 = 1 . 9000。
下面是与每一个厩的距离不同的厩的总和:
STALL
Dist     # 0   # 1   # 2   # 3   # 4   # 5   # 6   # 7   # 8   # 9   # 10
1 | 4 3 4 2 3 2 3 4 3 4 4
2 | 5 5 5 5 6 5 6 5 5 6 5
3 | 1 2 1 3 1 3 1 1 2 1
 
 
 
厩的数目
Avg .| 1 . 7 1 . 9 1 . 7 2 . 1 1 . 8 2 . 1 1 . 8 1 .7 1 . 9 1 . 6 1 . 7
所以最短的平均路程是 1 .6000,中心厩是 # 9。
· 5 3 ·输出举例:
9 1 . 6000
输入文件为 INPUT .C2,将结果写入输出文件 OUT .C2 中。
第三题: 网络通讯
农夫 John 的奶牛喜欢通过 E-mail 互相联系,所以它们建立了一个网络来互相通讯。
这些机器可沿路线发送 E-mail。如果存在一个由计算机组成的序列 a1 , a2 , . . ., an ,其中 a1
与 a2 相连, a2 与 a3 相连…,则 a1 和 an 可以互相传送 E-mail。
不幸的是,如果一个奶牛偶然间踩到计算机上或者农夫 John 开车经过,则机器将停
止工作。这意味着, 这个计算机将不能接发 E-mail , 则与这个计算机的连接将不能再
使用。
两个通讯的奶牛正在考虑至少发生多少这种事故,才能使它们不能用他们的计算机
进行互相通讯。写出一个程序,为他们计算这个最小值并找出对应这个最小值的那一组
机器。
例如,网络:
  1 *
 /
3 * - 2 *
表示 3 个计算机用两条线连接,我们想在 1, 2 之间传递信息。直线连接了 1, 3 和 2,
3。如果计算机 3 被破坏,则从 1 到 2 无法进行通讯。
输入: 网络的第一行包含 4 个整数: n, m, a, b。第一个数字 n 是网络上计算机的数目,第
二个数字 m 是每对计算机之间连接的数目,最后两个数字 a 和 b 是通讯的两个奶牛所使
用的计算机的 ID 号码。
下面 m 行是每对相连的计算机,它们的 ID 号码范围是 1~n。上面的网络表示为:
Input
3 2 1 2
1 3
2 3
计算机的数目将不大于 40,每个连接是唯一而且双向的(如果 c1 与 c2 连接,则 c2 也
与 c1 连接)。每两个计算机之间至多连一根线。对于这个任务,终端 a 和 b 不会直接相
连。
输入文件名为 INPUT .C3,输入文件可能包含几个网络,文件的结束行为 0 0 0 0。
输出:
对于每个网络,将有三行输出。第一行的形式为 “Network # n” ,其中 n 是数据的编
号;第二行是使终端 a 和 b不再连接的最少损坏计算机数;第三行是使 a 和 b 不再连接而
损坏的计算机列表,之间用空格隔开。注意, a 和 b 不能被损坏。
输出文件名为 OUTPUT .C3。
· 6 3 ·输入举例:
3 2 1 2
1 3
2 3
8 14 1 2
1 3
1 6
1 7
1 8
2 3
2 4
2 5
2 6
2 7
3 6
4 5
4 7
4 8
7 8
0 0 0 0
输出举例:
Network # 1
1
3
Network # 2
4
3 4 6 7
(3 6 7 8 也对)

打印本文   加入收藏   返回顶部   关闭窗口Tags:计算机程序设计选拔赛试题,计算机程序设计选拔赛试题,计算机程序设计试题  
相关文章列表
  • 没有文章
参与评论
共有评论 0网友评论列表
CopyRight © 2009-2012 计算机基础知识 Inc.All Rights Reserved. 备案:苏ICP备09028880号