设为首页 | 加入收藏夹

1993年美国计算机程序设计总决赛试题

2012-06-02 18:06:21 作者:计算机基础知识试题 录入:应序康 访问:3196 次 被顶:1 次 字号:【
摘要:第一题: 分数排序 考虑在 0 和 1 之间的所有分母不大于 N 的最简分数。下面是 N = 5 时的情况:0 / 1 1/ 5 1 / 4 1/ 3 2 / 5 1/ 2 3 / 5 2/ 3 3 / 4 4/ 5 1 / 1写出一个程序...
第一题: 分数排序
    考虑在 0 和 1 之间的所有分母不大于 N 的最简分数。下面是 N = 5 时的情况:
0 / 1   1/ 5   1 / 4   1/ 3   2 / 5   1/ 2   3 / 5   2/ 3   3 / 4   4/ 5   1 / 1
写出一个程序对于一个给定的整数 N( 1≤N≤100 ) ,按从小到大的顺序打印出这些
分数。你还应该打印出它们的总数。在每个分数后面打印一个制表符,使他们在显示的
时候一行不会很长。
要求: 当 N < 1 或 N > 100 时,程序应判错。
运行举例:
Enter the maximum denominator : 5
0 / 1   1 / 5   1 / 4   1 / 3   2 / 5   1 / 2   3 / 5   2/ 3   3/ 4   4/ 5   1/ 1
There were 11 f ractions .
第二题: 最大的谷仓
一个农夫想在自己的农场上建一个尽可能大的谷仓。但是他的农场上有树木及其他
建筑物,他不想移动它们中任何一个。为了简单,农场用一个 M×N 的网格代表,包含占
用整数格的树木及其他建筑物。长方形的谷仓不能与它们中的任何一个接触。如果农场
的大小为 5×6:
1 2 3 4 5 6
1 XX
2
· 1 1 ·3
4 XXXX
5 XXXX
则谷仓可以是
1 2 3 4 5 6
1 XX BB BB BB BB
2 BB BB BB BB
3
4 XXXX
5 XXXX

1 2 3 4 5 6
1 XX
2
3 BB
4 BB XXXX
5 BB XXXX
    在这种情况下,最大的谷仓从 1, 3 到 2, 6,面积为 8。
任务是,找出最大谷仓的面积以及建这个最大谷仓的所有可能位置的数目。
任务一 .从文件 BARN .IN 中读入任意组数据。每组数据第一行包含障碍物的数
目,第二行包含农场的长和宽,下面每行是障碍物的左上角坐标及长宽。文件将以一个负
数结尾。文件中至少有一组数据,每组数据至少有一个障碍物。上面例子的文件是:
2
5 6
1 1 1 1
4 3 2 2
- 1
任务二 .找出最大谷仓的面积以及建这个最大谷仓的所有可能位置的数目,以下面
的格式输出:
Maximum area = # # # , number of solutions = # # # .
对任务二,农场的长宽将不大于 20。输入数据中的障碍物的数目不大于 20。注意:
任务三的程序同样能解决任务二。
任务三 .农场的长宽将小于 1000。其它所有要求与任务二相同。注意 1000
2
> 2
16

运行举例:
BARN .IN:
2
5 6
· 2 1 ·4 3 2 2
1 1 1 1
2
11 13
1 1 5 5
7 9 5 5
- 1
输出:
Maximum area = 8 , number of solutions = 1
Maximum area = 35, number of solutions = 2
第三题: Polyomino e
一个 Polyominoe 是一个由 N 个方块边对边拼成的二维图形。下面是 N = 4 时的
Polyominoe:
*   * *     *     *   * *
* * * * * * * *
* *   * *
*
注意上面五个 Polyominoe 中,有一些可能通过对称或旋转以其它方式出现。对于上
面第四个图形,有下面这几种出现方式:
  *     * *           *
* * * * * * * *
*   * *   *
任务要求:
写出一个程序对一个给定的 N,建立并打印所有的 Polyominoe。每个 Polyominoe 只
打印一次(就是它的一个代表)。打印的顺序并不重要。你还应该打印出不同的 Polyomi-
noe 的数目。
如果你的程序能计算出 N≥9 的情况(在 486 / 33 上运行时间不超过 60 秒) , 你将得
到额外的分数。如果你的程序想得到额外的分数,它必须包含一个选项(当 N 的符号为
负) ,只打印 Polyominoe 的总数而不打印图形。
运行举例:
Enter N: 4
* * * *
*
* * *
  *
· 3 1 ·* * *
  * *
* *
* *
* *
There were 5 Polyominoes .
(取得额外分数的程序)
Enter N: - 4
There were 5 polyminoes .
第四题: 单词变换
在这个任务中,你要把一个单词转变成另一个单词,一次变换一个字母。
任务一 .1-morphs : 一个单词的1-morphs集合是由只改变该单词的一个字母后
所得单词组成的。 写出一个程序,打印出一个单词的1-morphs中的所有单词。 你将得
到一个名为 “WORDS” 的文件, 包含所有可采用的单词。 单词以字母顺序排列, 每行
一个。
任务二 . Laddergrams: 一个 laddergram 是由一串将第一个单词转换成最后一个单词
的1-morphs组成。例如: 将单词 “lead” 转换成 “gold” 的最短 Laddergram 是: lead load
goad gold . 写出一个程序对于一个给定的起始单词和一个结束单词,找出并打印出一个
最短的 laddergram(采用与任务一同样的文件作为字典)。
任务三 .所有结果:注意任务二中我们要求 “一个最短的 laddergram” ,并不是 “最短
的 laddergram” 。对于一个转换单词的任务,可能包含很多最短的解。写出 一个程序找
出所有最短的 laddergram。
任务四 .最长链:在给出的文件中找出由包含 5 个字母的单词所组成的最长的 lad-
dergram。你不需要为此单独写出一个程序,但你的结果必须有根据。
运行举例:
Part 1:
The 1-morphs of TIMES are :
timer timed tires tiles tides tames limes dimes
Part 2:
这里有一些例子你可以用来测试你的程序:
LOVE to HATE: love lone lane late hate
BRAIN to THINK: brain train trait t ract t rack trick thick think
WHITE to BLACK: white whine shine spine spice slice slick slack black
· 4 1 ·

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