设为首页 | 加入收藏夹

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

2012-06-02 18:08:22 作者:计算机基础知识试题 录入:应序康 访问:3119 次 被顶:1 次 字号:【
摘要:第一题: 闭合篱笆 一个在平面上的 “闭合篱笆” 是一个有 N 个端点且无交叉的闭合折线,见图 2 .3 .1。端点以逆时针方向存放在数组{xi yi}中( i = 1, 2,…, N)。每一对相邻的端点定义了篱笆的一条边。因此, {xi ...
第一题: 闭合篱笆
    一个在平面上的 “闭合篱笆” 是一个有 N 个端点且无交叉的闭合折线,见图 2 .3 .1。
端点以逆时针方向存放在数组{xi yi}中( i = 1, 2,…, N)。每一对相邻的端点定义了篱笆
的一条边。因此, {xi yi xi + 1 yi + 1 } 是篱笆的一条边( i = 1, 2,…, N)。注意 xN + 1 = x1 , yN + 1
= y1 以使得最后一个端点与第一个端点相连使篱笆闭合。
图   2 . 3 . 1
写一个程序完成以下任务:
(1 ) 检查一个端点数组{ xi yi} , i = 1, 2,…, N 是否能组成一个合法的篱笆。一个合法
的篱笆不自交。
(2 ) 假设一个人(没有高度)站在平面上坐标为( x y )的位置上看篱笆。他将看到哪
些边 ? 你的程序必须找出所有能被全部看见或部分看见的边。这相当于在点( x y)存在
一条不与其它边相交的光线照到这条边上。与视线平行的边被认为是不可见的。在上图
中,线段 x3 y3 x4 y4和包含两条边的折线段 x5 y5 x6 y6 x1 y1 对于点 x y 是可见的或部分可
见的。如果一条边的一部分是可见的,整条边都应该被列出而不仅仅是可见的部分。
输入文件: FENCE .DAT
FENCE .DAT 中的每组数据包含:
(1 ) N(端点数目 N≤30) ;
( 2) 一个端点包含两个由空格隔开的整数(每个绝对值都小于100 ) ,两个相邻端点之
间也用空格隔开。端点按逆时针方向给出。如果有必要,端点将分几行给出;
(3 ) 人观察篱笆时所在的坐标( x y)。
输出文件: FENCE .SOL
FENCE .SOL 中的每组数据包含:
(1 ) M(可见边的个数) ;
(2 ) 每行写出一个可见的折线段(由一条或多条相连的边组成)。

· 5 1 ·(1 ) 如果 FENCE .DAT 中给出的篱笆是非法的,则写出信息 “NO FENCE” 。
不同组数据之间用空行隔开(只有换行符)。
运行举例:
输入
FENCE .DAT
4
0 0 2 0 1 1 0 1
2 2
4
0 0 2 0 1 1 1 -1
3 0
5
0 0 2 0 2 2 1 1 0 2
4 3
13
0 0 7 0 5 2 7 5 5 7 3 5 4 9 1 8 2 5 0 9 -2 7 0 3 -3 1
5 5
13
0 0 7 0 5 2 7 5 5 7 3 5 4 9 1 8 2 5 0 9 -2 7 0 3 -3 1
5 10
16
0 0 2 0 2 1 3 1 4 0 4 2 3 2 3 3 4 4 2 4 2 3 1 3 0 4 0 2 1 2 1 1
2 2
输出
FENCE .SOL
2
2 0 1 1 0 1
NO FENCE
2
2 0 2 2
1 1 0 2
· 6 1 ·7
-2 7 0 3 -3 1 0 0 7 0
5 2 7 5 5 7 3 5
5
7 5 5 7 3 5 4 9 1 8
2 5 0 9
8
0 0 2 0
2 1 3 1
4 0 4 2
3 2 3 3
4 4 2 4
2 3 1 3
0 4 0 2
1 2 1 1
第二题: 算术级数
一个算术级数是形如 a , a + b, a + 2b,…, a + nb( n = 0, 1, 2, 3,…)的数列。假设 a, b 都
是非负整数(0 ,1 ,2 ,3 ,…)。
写一个程序在双平方数集合 S 中找出所有长度为 n 的算术级数。双平方数的集合是
由所有形如 p
2
+ q
2
( p, q 均是非负整数)的整数所组成的集合。你的程序应该接受一个级
数的长度 n 和双平方数的上限 m。输入文件 ARITH .DAT 的每一行包含两个数: n, m。
假设 m≤10 000。
运行举例:
ARITH .DAT
8 200
10 1000
ARITH .SOL
Arithmetic progressions of length 8
taken f rom bisquares within the range
from 0 to 200:
Difference of 12 :
1 13 25 37 49 61 73 85
13 25 37 49 61 73 85 97
25 37 49 61 73 85 97 109
37 49 61 73 85 97 109 121
· 7 1 ·Difference of 24 :
1 25 49 73 97 121 145 169
2 26 50 74 98 122 146 170
25 49 73 97 121 145 169 193
26 50 74 98 122 146 170 194
There are 8 progressions .
Arithmetic progressions of length 10
taken f rom bisquares within the range
from 0 to 1000 :
Difference of 12 :
1 13 25 37 49 61 73 85 97 109
13 25 37 49 61 73 85 97 109 121
Difference of 24 :
2 26 50 74 98 122 146 170 194 218
26 50 74 98 122 146 170 194 218 242
101 125 149 173 197 221 245 269 293 317
761 785 809 833 857 881 905 929 953 977
Difference of 36 :
421 457 493 529 565 601 637 673 709 745
Difference of 48 :
4 52 100 148 196 244 292 340 388 436
52 100 148 196 244 292 340 388 436 484
202 250 298 346 394 442 490 538 586 634
Difference of 60 :
5 65 125 185 245 305 365 425 485 545
65 125 185 245 305 365 425 485 545 605
Difference of 72 :
29 101 173 245 317 389 461 533 605 677
Difference of 84 :
29 113 197 281 365 449 533 617 701 785
37 121 205 289 373 457 541 625 709 793
73 157 241 325 409 493 577 661 745 829
121 205 289 373 457 541 625 709 793 877
· 8 1 ·205 289 373 457 541 625 709 793 877 961
Difference of 96 :
8 104 200 296 392 488 584 680 776 872
104 200 296 392 488 584 680 776 872 968
Difference of 108:
9 117 225 333 441 549 657 765 873 981
There are 21 progressions .
测试数据:
题目一:
FENCE .DAT
27
2 3 3 3 4 4 4 5 3 6 2 6 1 5 0 4 0 3 0 2 1 1
2 1 3 0 4 1 5 0 6 1 7 0 8 1 7 2 7 3 6 3 6 4
5 4 5 2 4 2 3 2 2 2
7 1
27
2 3 3 3 4 4 4 5 3 6 2 6 1 5 0 4 0 3 0 2 1 1
2 1 3 0 4 1 5 0 6 1 7 0 8 1 7 2 7 3 6 3 6 4
5 4 5 2 4 2 4 0 3 2
7 1
题目二:
ARITH .DAT
7 100
12 1000
22 10000

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