2017年计算机ACM编程竞赛
主办：计算机科学与技术学院
时间：2017-11-22 18:00---20:00
地点：计算机学院奋进楼4楼5机房
竞赛规则
1、比赛时间为120分钟，从18:00开始，20:00结束。
2、比赛形式为上机编程，每个小组使用三台电脑，可任选语言，同一小组不同题目可使用不同语言；
3、比赛期间可以使用自己电脑，不可查阅书籍、但禁止查阅个人U盘，禁止使用手机、电脑进行上网查询，禁止使用现有代码，违者取消比赛资格；（正式ACM中是可以携带纸质材料的，但由于本次比赛，有大量题目参考书上例题，所以就不让携带了）
4、比赛期间，如遇到设备问题，可举手示意工作人员；
5、由于机房电脑系统有重启还原功能，比赛期间请勿轻易重启电脑；
6、【重要】比赛结束后，请确认将所要提交文件拷至工作人员U盘，否则成绩无效概不负责。
提交方式
1、创建文件夹，文件夹命名格式为小组号-小组队长-组员1-组员2
2、将每一题的源程序文件夹以题目编号命名，拷贝至上述创建的文件夹中
3、在本文档中每题相应位置附上源码及截图（windows截图键:Alt+Prt sc
sysrq）,拷贝至上述创建的文件夹中
4、比赛结束后将上述文件夹拷贝至工作人员U盘中，提交方算完成，提交
完成前请勿重启电脑。
注：本次比赛共14题，满分120分。
没有完成题目，但有部分解题步骤者按完成度给分。
每道题要有注释。
竞赛题目
1. 青年歌手大奖赛中，评委会给参赛选手打分。
选手得分规则为去掉一个最高分和一个最低分，然后计算平均得分，请编程输出某选手的得分。
输入数据有多组，每组占一行，每行的第一个数是n(2<n<100)，表示评委的人数，然后是n 个评委的打分。
（5分）
【要求】
输入数据：输入数据有多组，每组占一行，每行的第一个数是n(2<n<100)表示评委的人数，然后是n个评委的打分。
输出数据：对于每组输入数据，输出选手的得分，结果保留2位小数，每组输出占一行。
【样例输入】
3 99 98 97
4 100 99 98 97
【样例输出】
98.00
98.50
2. 使用for循环、while循环和递归写出3个函数来计算给定数列的总和。
（5分）
【要求】
输入数据：n(表示数组长度)
一组数字（如：1，2，3，4，5）
输出数据：该组数字的和
3. 编写一个计算前100位斐波那契数的函数。
根据定义，斐波那契序列的前两位数字是0和1，随后的每个数字是前两个数字的和。
例如，前10位斐波那契数为：0，1，1，2，3，5，8，13，21，34。
（5分）
【要求】
输入数据：n（表示前n位斐波那契数列）
输出数据：n位斐波那契数列
4.实现两个矩阵的相加。
（5分）
例如： 2 3 5 3 5 6 5 8 11
3 1 6 + 1 2
4 = 4 3 10
2 6 7 2 4 6 4 10 13
【要求】
输入数据：两个矩阵数据不限
输出数据：这两个矩阵的和
5. 二分查找是一种针对有序集合的查找方法。
通过比较查找键K和数组中间元素A[M]来完成查找工作。
如果它们相等，算法结束。
否则，如果K < A[M]，就对数组的前半部分执行该操作，如果K > A[M]，则对数组的后半部分执行该操作。
（5分）
伪代码：
BinarySearch(A[0..N-1]，K)
//实现非递归的折半查找
//输入：一个升序数组A[0…N-1]和一个查找键K
//输出：一个数组元素的下标，该元素等于K;如果没有这样一个元素，则返回-1
i <- 0; r <- n – 1
while i <= r do
m <- [(i + r) / 2]
if K = A[m] return m
else if K < A[m] r <- m – 1
else l <- m + 1
return -1
【要求】
输入数据：一个有序数组和要查找的数字
输出数据：返回查找数字的位置没有则返回-1
【样例输入】
4，5，8，9，10
8
【样例输出】
2
6. 汉诺塔。
汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。
大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。
大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。
并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘，请用编程实现。
（7分）
【要求】
输入数据：无
输出数据：盘子的移动过程
（例如：用abc表示三个柱子第n个盘子 a ---- b）
7. 简单计算机。
有一台功能极其简单的计算机，只能计算简单的七种指令A、B、
C、D、E、F；只有两个内存M1、M2；只有三个寄存器R1、R2、R3，六种指令的含义如下：
命令A：将内存M1的数据装到寄存器R1中；
命令B：将内存M2的数据装到寄存器R2中；
命令C：将寄存器R3的数据装到内存M1中；
命令D：将寄存器R3的数据装到内存M2中；
命令E：将寄存器R1中的数据和寄存器R2中的数据相加，结果放到寄存器R3中；
命令F：将寄存器R1中的数据和寄存器R2中的数据相减，结果放到寄存器R3中。
命令G: 输出M1和M2的值
你的任务是：设计一个程序模拟该计算机的运行（10分）
【样例输入】
100 288
ABECEDG
【样列输出】
388 388
8. 编写一个能将给定非负整数列表中的数字排列成最大数字的函数。
例如，给定[50，2，1,9]，最大数字为95021。
（10分）
【要求】
输入数据：一组数字
输出数据：最大数字
9. 现设计一种算法实现如下功能，具体如下：将1~100首尾相连（即100的后面是1），输入一个1~9之间的数字n，从1开始，每数n位便去掉当前数字，直至100个数字中只余下1个。
例：取n=9，先后去掉的数字有9,18,27,36......99,8,19,29......（10分）（此题禁止使用ArrayList等动态数组类库）
【要求】
输入数据：n
输出数据：最后保留的数字。
10. 整数的分划问题。
如，对于正整数n=6，可以分划为：（10分）
6
5+1
4+2, 4+1+1
3+3, 3+2+1, 3+1+1+1
2+2+2, 2+2+1+1, 2+1+1+1+1
1+1+1+1+1+1+1
【要求】
输入数据：需要划分的整数
输出数据：所有划分结果
11.请把算式中缀表达式转化为后缀表达式，并根据后缀表达式得出计算结果（12分）
【要求】
输入数据：中缀表达式（将运算符写在两个操作数中间的表达式成为中缀表达式）输出数据：后缀表达式（将运算符写在两个操作数后面的表达式成为中缀表达式）结果
注意！运算符的优先顺序。
【样例输入】1+2*（3-4）+5
【样列输出】1234-*+5+
4
12.编写一个在1，2，…，9（顺序不能变）数字之间插入+或-或什么都不插入，使得计算结果总是100的程序，并输出所有的可能性。
（12分）
例如：1 + 2 + 34 – 5 + 67 – 8 + 9 = 100。
【要求】
输入数据：无
输出数据：所有的可能性。
13. 农夫老王种植了一片树木，他想为树林建起一座护栏，为使成本最低，他决定为最外围的树木作为端点建立护栏，如图所示。
请帮设计算法帮助老王找到这些树木的坐标。
（12分）
【要求】
输入数据：所有树木的坐标
输出数据：最外围树木的集合。
【样例输入】（2，1），（1，3），（3，5），（3，3），（5，3），（4，1）
【样列输出】（2，1），（1，3），（3，5），（5，3），（4，1）
14.求解n元联立方程组（12分）a11X1 + a12X2 + … + a1nXn = b1 a21X1 + a22X2 + … + a2nXn = b2 . . an1X1 + an2X2 + … + annXn = bn 【要求】
输入数据：二元方程组的系数矩阵输出数据：结果矩阵
【样例输入】 2 -1 1 1
4 1 -1 5
1 1 1 0
表示2*x1 - 1*x2 + x3 = 1
4*x1 - 1*x2 - x3 = 5
1*x1 - 1*x2 + x3 = 0 【样列输出】 1 0 0 1
0 1 0 0
0 0 1 -1。