设为首页 | 加入收藏夹

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

2012-06-02 18:13:49 作者:计算机基础知识试题 录入:应序康 访问:3146 次 被顶:1 次 字号:【
摘要:第一题: 低价买入,更低价买入 在股票市场中, “低价买入” 就是成功的一半,但是作为一个出色的投资者,你必须遵循下面的规则:“低价买入,更低价买入”就是说,当你买入股票的时候,它的价格必须低于你最近一次购买的价格。你这样购买的次数越多,作...
第一题: 低价买入,更低价买入
    在股票市场中, “低价买入” 就是成功的一半,但是作为一个出色的投资者,你必须遵
循下面的规则:
“低价买入,更低价买入”
就是说,当你买入股票的时候,它的价格必须低于你最近一次购买的价格。你这样购
买的次数越多,作为投资者你做的就越出色。
你将得到每天股票的价格,你可以在任意一天买股票,但必须记住每次买的价格必须
比上一次购买的价格低。你的任务是写出一个程序,找出哪些天应该购买股票(遵循这个
原则) ,使得购买的次数最多。
例如, IBM 的股票在连续一些天内的价格为:
Day 1 2 3 4 5 6 7 8 9 10 11 12
Price 68 69 54 70 68 64 70 62 67 78 98 87
    对于上面的例子,最出色的投资者最多可以买四次(如果他遵循上面的每次买价都低
于前一次的规则)。
这四天的顺序是:
Day 4 5 6 8
Price 70 68 64 62
输入数据:
价格被存放在名为 INPUT .TXT 的文件中, 这个文件开始首先是天数 ( 1≤N≤
5000 ) ,下面是每天的价格(一个正整数)。
例如:
INPUT .TXT
12
68
69
54
70
68
64
70
62
· 5 2 ·67
78
98
87
输出数据:
在屏幕上输出最长的递减价格序列的长度和这种长度的序列的数目,输出格式并不
重要。
运行举例:
Longest length 4
Total with this length 2
在统计结果数目时,当两种结果包含完全相同的数字串时(即当它们被打印出来时看
起来完全相同) ,它们被认为是相同的(只能被统计一次)。两个不同天数组成的序列可能
出现完全相同的价格数字串。
第二题: 重叠的方框
考虑下面 5 个放置在 9×8 的点阵中的方框图,见图 2 .6 .1。
图   2 . 6 . 1
现在,将他们按顺序叠放起来( 1 在底层, 5 在顶层)。如果一个框的一部分盖住了另
外一个框,则将被挡住的部分隐去。下面是这 5 个框叠放起来的图形:
. C C C . . . .
E C B C B B . .
D C B C D B . .
D C C C . B . .
D . B . A B A A
D . B B B B . A
D D D D A D . A
E . . . A A A A
E E E E E E . .
· 6 2 ·    这些方框从下至上叠放的顺序是什么 ?
答案是 EDABC。
你的任务是对于一个给定的方框叠放后的图形,找出它们从下至上叠放的顺序。
下面是其规则:
(1 ) 方框边的宽度为 1 个字符,边长不少于 3 个字符;
(2 ) 每个框的 4 条边都有一部分可见。一个角代表两个边;
(3 ) 方框用大写字母来标注,没有两个方框用同样的字母来标注。
输入数据:
文件 INPUT .TXT 包含高度 h( h≤30 )和宽度 w( w≤30 )。h 个长度为 w 的字符串,
代表所有方框叠放后的图形。
例如:
INPUT .TXT
9
8
. C C C . . . .
E C B C B B . .
D C B C D B . .
D C C C . B . .
D . B . A B A A
D . B B B B . A
D D D D A D . A
E . . . A A A A
E E E E E E . .
输出数据:
在屏幕上输出结果。以方框从下至上叠放的顺序给出代表他们的字母。如果有很多
种可能的顺序,写出所有的情况。输入数据至少有一种合法的顺序。
例如:
EDABC
2 .7   1995 年美国计算机程序设计总决赛试题
第一题: 奶牛排队
    有一天农夫 John 带着他的 19 头最好的奶牛(奶牛有两种: Black Angus 和 WhiteJer-
sey)去赶集。当奶牛排成一列走过他家门口的时候,他的妻子 Joanne 发现 4 头黑白奶牛
的所有 16 种组合( bbbb, bbbw, bbwb,…, wwww )在队列中都出现(作为子序列)。当然,
这些子序列之间可能有重叠。
任务一: 打印出一组这 19 头黑白奶牛的可能的排列顺序,使得它包含所有四头牛的
组合。
· 7 2 ·任务二: 由键盘输入奶牛的个数和子序列的长度,打印出一组奶牛的可能排列,使得
它包含全部可能的子序列。例如奶牛的个数和子序列的长度可以是: 2 , 5; 3, 10; 4, 19; 5,
36 ;…。奶牛的个数不会超过 32782,子序列的长度不会超过 15。而且保证至少存在一个
解,你的程序运行时间应不超过 30 秒。
第二题: 奶牛运输
有一个奶牛运输公司,设在农场 A 中, 它有一个用来在 7 个农场 A, B, C, D, E, F , G
之间运输奶牛的运输车。7 个农场之间的距离由下表给出:
B C D E F G
A 56 43 71 35 41 36
B . 54 58 36 79 31
C . . 30 20 31 58
D . . . 38 59 75
E . . . . 44 67
F . . . . . 72
    每天早晨,运输公司都要决定运输奶牛的顺序,使得总路程最少。下面是规则:
(1 ) 运输车总是从在农场 A 的公司总部出发,而且当所有的运输任务完成之后还要
返回总部;
(2 ) 运输车一次只能运送一个奶牛;
(3 ) 每个运输任务是由一对字母给出的,分别代表奶牛将从哪个农场被运向另外一
个农场。
你的任务是写一个程序,对一组给定的任务,求出一条完成所有任务的最短路线(从
农场 A 出发,最后返回农场 A)。
输入格式: 任务存放在一个名为 “DELVR .TXT” 的文件中。文件的第一行是任务的总数
N( 1≤N≤12) ,从第二行开始,每个任务由一对被一个空格隔开的字母给出,第一个字母
代表奶牛所在的农场,第二个字母代表奶牛将被运向的农场。你的程序运行时间应不超
过 60 秒。
输入举例:
5
F C
G B
B D
A E
G A
输出格式: 在屏幕上打印出最短路线的长度,并显示出运输车经过的农场的顺序。
输出举例:
368
A E F C G B D G A
· 8 2 ·第三题: 攻击性奶牛
农夫 John 的 8 头奶牛在 “北 40 区” 做一种名叫 PAINTBALL 的游戏。 “北 40 区” 被
分成 64 个奶牛大小的方格— — —一个 8×8 的网格,每头牛占据一个格子。它可以攻击在
网格中的任何来自其他种群的奶牛(或者别的动物)。
非常奇怪的是不好战的 Holsteins 以一种懦弱的方式来做 PAINTBALL 游戏。在他
们新发明的 F18 Hornet Paintball 游戏中,奶牛可以向 8 个方向喷洒染料— — —覆盖与奶牛
所占据的格子同行同列或同对角线的格子。
安排这 8 个 Holsteins ,使得他们攻击的格子总数最少。奶牛本身占据的格子忽略
不计。
第四题: 完美的奶牛和堂兄弟
像大多数农夫一样,农夫 John 也有一份他的优良品种奶牛的记录,每一个奶牛有一
个代号。为了参加 Cownty 展览会, John想找出最好品种的奶牛,即完美的奶牛。
完美奶牛的代号应该是它的所有合适约数的和,合适约数表示小于一个数本身的约
数。例如: 28 = 1 + 2 + 4 + 7 + 14。
完美的堂兄弟也很有趣,因为它们各自的代号的所有合适约数的和恰好等于对方的
代号。例如: 代号 220 和 284。
稀有的五牛堂兄弟,它们的代号形成了一个序列,在这个序列中,第一头牛的合适约
数的和等于第二头牛的代号,第二头牛的合适约数的和等于第三头牛的代号,……,第五
头牛的合适约数的和等于第一头牛的代号。
输出完美奶牛、 完美堂兄弟代号,以及完美五牛堂兄弟的序列。
输出举例:
6
28
220 284
(以下不超过 20 行)
第五题: Cowc ycle
由于在 Playboy中中奖, Hugh Heiffer 从乡下的土地搬到了郊区一个时髦的庭院中。
为了找回他在田园的记忆,他想回去看看自己原来的土地。考虑到环境的限制, Hugh 打
算骑着自己的 Cowcycle (一种为他的肥胖体形专门设计的自行车)。但 Hugh 的体重超过
一吨,因此,在传统的 Cowcycle 上平稳的加速对他来说是个难题。一些相距很远的齿轮
(Cowcycle 的前后齿轮)的比例的改变将会对他的心脏不好。
Hugh 在他自己的 Cowcycle 的前部安装两个大齿轮,后部安装 5 个小齿轮,但应满足
下面的要求:
(1 ) 前面两个齿轮包含的齿数为 39~62;
(2 ) 后面 5 个齿轮包含的齿数为 12~28;
· 9 2 ·(3 ) 对于每种设置前后齿轮的比例就是前面齿轮的齿数和后面齿轮的齿数的商;
(4 ) 齿轮比例的范围跨度至少应为 3;
(5 ) 所有齿轮的齿数的方差应达到最小。
一组数的方差的计算公式为:
珔 x = 1
n∑
n
i = 1
xi
方差 = 1
n∑
n
i = 1
( x i - 珔 x )
2
    打印并标出最理想的前后齿轮的齿数。
第六题: 监视奶牛
农夫 John 刚刚投资在 Locowter-2000 建立了一个新的牧场来放牛。Locowter-2000
的最好的特点是只需从牧场的周围取得补给。
农夫 John 为了方便,将他的农场分为 10×15 的奶牛大小的网格,每个方格可以放 0
或 1 个食槽。
在牧场的周围有 73 个扫描装置,每个装置能统计它所在的直线上奶牛的个数,农夫
John 用这些扫描装置观察所有行列及对角线(两个方向)上牛的个数。
统计的数字将被传送到 L2000 的计算机上,用来计算奶牛的位置,并显示出一张用
ASCI I 码符号组成的图。
非常可惜的是, L2000 的计算机受到损坏,农夫 John 需要你来帮助他计算奶牛的
位置。
扫描装置的输出是一组整数,它代表了每行每列和对角线上奶牛的数目, 第一行的
10 个数字代表每行奶牛的数目,注意下图中字母的顺序:
a - > . # # # # # # # # # # . . . .
b-> . # # # # # # # # # # . . . .
c - > . . . . # # # # # # . . . . .
d-> . . . . . . # # # # . . . . .
e - > . . . . . . . # # # # . . # #
f-> . . . . . . . # # # # # # # #
g-> # # # # # . . # # # # # # # #
h- > # # # # # # # # # # # # # # #
i - > . . # # # # # # # # # . . # #
j - > . . . . # # # # # # . . . . .
    第二行的 24 个数字代表对角线上奶牛的数目,注意下图中字母的顺序:
. # # # # # # # # # # . . . .
/ . # # # # # # # # # # . . . .
a/ . . . . # # # # # # . . . . .
b / . . . . . . # # # # . . . . .
· 0 3 ·c/ . . . . . . . # # # # . . # #
d / . . . . . . . # # # # # # # #
e/ # # # # # . . # # # # # # # #
f / # # # # # # # # # # # # # # #
g / . . # # # # # # # # # . . # #
h / . . . . # # # # # # . . . . .
i / / / / / / / / / / / / / / /
j k l m n o p q r s t u v w x
    第三行的 15 个数字代表每列上奶牛的数目,注意下图中字母的顺序:
. # # # # # # # # # # . . . .
. # # # # # # # # # # . . . .
. . . . # # # # # # . . . . .
. . . . . . # # # # . . . . .
. . . . . . . # # # # . . # #
. . . . . . . # # # # # # # #
# # # # # . . # # # # # # # #
# # # # # # # # # # # # # # #
. . # # # # # # # # # . . # #
. . . . # # # # # # . . . . .
| | | | | | | | | | | | | | |
a b c d e f g h i j k l m n o
    最后一行的 24 个数字代表另一方向对角线上奶牛的数目,注意下图中字母的顺序:
. # # # # # # # # # # . . . .
. # # # # # # # # # # . . . . \
. . . . # # # # # # . . . . . \ x
. . . . . . # # # # . . . . . \ w
. . . . . . . # # # # . . # # \ v
. . . . . . . # # # # # # # # \ u
# # # # # . . # # # # # # # # \ t
# # # # # # # # # # # # # # # \ s
. . # # # # # # # # # . . # # \ r
. . . . # # # # # # . . . . . \ q
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ p
a b c d e f g h i j k l m n o
    此例的输入文件如下:
10 10 6 4 6 8 13 15 11 6
0 1 2 2 2 2 4 5 5 6 7 6 5 6 6 5 5 6 6 3 2 2 1 0
2 4 5 5 7 6 7 10 10 10 7 3 3 5 5
0 0 1 3 4 4 4 4 3 4 5 7 8 8 9 9 6 4 4 2 0 0 0 0
你的程序应该提示输入一个文件名,然后用所给的输入文件中的数据重新建立一个
· 1 3 ·所有奶牛的放牧的图形。注意, 存在一组数据不能对应唯一的图形的可能,但是农夫
John 的牛从来不以这种方式来安排。你一定能在不做任何猜疑的情况下决定每个方格
中牛的数目。

参与评论
共有评论 0网友评论列表
CopyRight © 2009-2012 计算机基础知识 Inc.All Rights Reserved. 备案:苏ICP备09028880号