全国ITAT教育工程就业技能大赛的试题解析
1、 建造冬奥会滑雪场的空中升降轨道。从起点到终点，有若干可选的支架作为固定点，再在相邻固定点间架设导轨。假设所有可选的支架在一条轴线（x轴）上，从起点到终点的x轴间隔为1的每一点上都有一个支架，并给出支架的高度。建造要求如下：
a) 选择尽可能少的支架建立固定点；
b) 导轨保持平直，即固定点中间的支架不高于导轨；
c) 两个相邻固定点之间，沿x轴距离不能超过给定的K；
d) 第一个（起点）和最后一个（终点）一定是固定点。
测试数据文件说明：
输入文件skilift.in的内容：
第一行是N和K，N和K之间以空格分开，2<=N<=5000，1<=K<=N-1。
接下来N行，按顺序是支架的高度h，0<=h<=1000000000。
输出文件skilift.out的内容：
一个整数，表示最少要选择几个固定点，以及选择的固定点序列号。
样例：
输入文件：
13 4
0
1
0
2
4
6
8
6
8
8
9
11
12
输出文件：
6 -- 1、5、7、10、12、13
如下图所示，至少需要6个固定点，选择第1、5、7、10、12、13个支架作为固定点。
（1）请根据以上要求设计最佳算法，并加以说明；
（2）编程实现算法，并以样例文件进行测试，输出结果；
（3）按照下面给定的三个测试数据进行测试，并输出结果。
测试数据一：
N=20，K=3
N行数据（，作为换行提示符）：
0，2，1，3，5，7，4，5，3，8，10，12，11，13，14，15，12，9，20，22
测试数据二：
N=18，K=5
N行数据（，作为换行提示符）：
0，2，1，3，7，6，2，8，10，9，11，12，15，7，4，5，19，21
测试数据三：
N=30，K=4
N行数据（，作为换行提示符）：
0，1，3，5，4，2，3，5，7，8，10，9，12，15，21，20，23，25，22，27，28，29，27，30，22，31，35，36，35，39
（本题60分，要求1占20分，要求2占10分，要求3占30分）
2、 设有n个球队要进行排球循环赛，设计一个满足以下要求的比赛日程表：
a) 每个球队必须与其他n-1个球队各赛一次；
b) 每个球队一天只能赛一次；
c) 当n是偶数时，循环赛进行n-1天。当n是奇数时，循环赛进行n天。
n=6的比赛日程表示例（把6个队从1到6进行编号）：
n=6的比赛日程表
第一天
第二天
第三天
第四天
第五天
1~2
1~3
1~4
1~5
1~6
3~5
2~4
2~5
2~6
2~3
4~6
5~6
3~6
3~4
4~5
n=5的比赛日程表示例（增加编号0，凡碰0者该天即轮空）：
n=5的比赛日程表
第一天
第二天
第三天
第四天
第五天
1~0
1~5
1~4
1~3
1~2
2~5
0~4
5~3
4~2
3~0
3~4
2~3
0~2
5~0
4~5
（1）请根据以上要求分析问题，设计算法，并加以说明；
（2）编程实现算法，并以n=10和n=15进行测试，输出结果；
（3）分析算法的时间复杂度。
（本题共60分，要求1占20分，要求2占30分，要求3占10分）
题目命名要求：请将编写好的源程序以T+题号的方式命名，例如第1题的源程序保存为“T1.java” ）。
1、 某企业在未来的12个月要研究一种新产品，新产品的研制需要四个阶段，每个阶段都可用慢、正常、快等三种速度进行，时间和成本如下表所列。
理论研究
试验阶段
政府批准
销售
慢
5/5
3/6
6/1
5/8
正常
4/7
2/8
4/1
4/10
快
2/10
1/12
2/3
3/15
说明：单位（月/万元），时间按月，成本按万元为单位。
例如：5/5代表5个月，5万元；4/7代表4个月，7万元。
该企业准备在12个月内花费最少的费用就可以有新产品。
（1）请给出最佳方法或算法。
（2）编程实现最佳算法。
（3）达到同一目标的次佳方法或算法是什么？
（本题60分，要求1占20分，要求2占30分，要求3占10分）
2、 有三个白子和三个黑子如下图布置：
○
○
○
●
●
●
用最少的步数将上图中白子和黑子的位置进行交换：
●
●
●
○
○
○
规则是：
（1）一次只能移动一个棋子；
（2）棋子可以向空格中移动，也可以跳过一个对方的棋子进入空格，但不能向后跳，也不能跳过两个子。
（本题共60分，要求1占30分，要求2占30分）
要求：
（1）分析问题，找出规律，总结出规则和算法，并描述你的算法设计思想。
（2）编程显示每一步交换过程。
1、 编写一个Java应用程序，对于给定的一个字符串的集合，格式如：
{aaa bbb ccc}， {bbb ddd}，{eee fff}，{ggg}，{ddd hhh}
要求将其中交集不为空的集合合并，要求合并完成后的集合之间无交集，例如上例应输出：
{aaa bbb ccc ddd hhh}，{eee fff}， {ggg}
请将制作好的源文件保存为“t1.java”。（本题60分，要求1占20分，要求2占35分，要求3占5分）
（1）分析问题，描述你解决这个问题的思路、处理流程，以及算法复杂度。
（2）编程实现题目要求的集合合并。
（3）描述可能的改进（改进的方向如效果，算法复杂度，性能等等）。
2、 在下图中的九个点上，空出中间的点，其余的点上任意填入数字1至8；1的位置保持不动，然后移动其余的数字，使1到8顺时针从小到大排列。移动的规则是：只能将数字沿线移向空白的点。请将制作好的源文件保存为“t2.java”。（本题共60分，要求1占20分，要求2占40分）
要求：
（1）分析问题，并描述你的算法设计思想。
（2）编程显示数字移动过程。