第七届全国信息技术应用大赛Java程序设计决赛试题.doc

教育部教育管理信息中心

第七届全国信息技术应用水平大赛决赛试题
Java程序设计
请仔细阅读并严格遵守题目中关于文件命名和保存的要求。
考生开始答题时，首先创建以“准考证号”命名的文件夹（形式如：102029618），并将考试结果严格按题目上的命名要求进行命名并直接保存在该文件夹下。
注意：考生不得在该文件夹下创建任何子文件夹，所有考试结果均直接保存在该文件夹根目录下。
考生答题完毕，选中整个文件夹，用Winrar压缩工具打包后存放在本考场指定的考试结果存放地址，经监考老师确认上传无误后方可离开考场。
注意：在提交答案时，请务必选中上述存放作品的文件夹（如前面创建的102029618文件夹，而不是文件夹下的全部文件）进行压缩，在完成答案提交后，请确保上述压缩包仍保存在本地计算机中。
请务必按照试卷要求提交指定的文件，不得包含非题目要求的过程文件和临时文件，不得包含本试题文件和试题素材。
凡违反上述规定的考生，其成绩一律按零分处理。

题目命名要求：
（1）请将编写好的源程序以T+题号的方式命名，例如第1题的源程序保存为“T1.java”，题目本身有命名要求的除外。
（2）根据题目要求，各题还需要提供相应的算法文字说明，包括待解问题分析、算法描述、性能分析等内容，请考生在自建的Word文档中完成，并分别用题号命名，如“1.doc”。如缺少该文档，将扣除相应的分数。

1、2012年第十号台风“达维”在我国登陆，某港口为减少损失，需要紧急将滞留在港口的货物运输到安全地带。由于运力紧张、台风来势凶猛，港口不能抢救出所有货物，但是工作人员希望抢救出价值总额更高的货物以减少损失。已知港口目前仅剩一艘运输船，它的承载能力为T吨（不考虑轮船货舱的容积）。滞留货物的重量及价值如下表(每种货物均以箱为单位进行抢救，并且假定有无限箱)：
货物编号
1
2
3
……
n
每箱货物重量（吨）
N1
N2
N3
……
Nn
每箱货物价值（万）
V1
V2
V3
……
Vn
题目要求如下：
（1）请根据题意设计算法，加以文字说明，并给出算法的时间复杂度。
（2）编程实现算法，要求输出能抢救的最大价值及每种货物的装船数量。
测试用例：假如目前港口仅剩1艘运输能力为2200吨的轮船，所剩货物的重量及价值如下表，采用所编写的程序输出抢救货物的总价值以及装船的方法。
货物编号
1
2
3
4
每箱货物重量（吨）
200
300
700
800
每箱货物价值（万）
20
30
110
130
（3）如果同样目前港口仅剩1艘运输能力为2200吨的轮船，所剩货物重量及价值如下表，是否有时间复杂度更低的算法，若有请写出时间复杂度更低的算法的设计思想及文字说明，并注明时间复杂度；若没有请说明理由。
货物编号
1
2
3
4
每箱货物重量（吨）
200
300
700
800
每箱货物价值（万）
10
40
110
130
【分 数】40分

2、根据给出的两个大于1的正整数N和M（N<=15，M<=100000000，N<M），自行选取另外N+1个正整数，这些数中可以有重复值，但要求其中的最大值必须为M，最小值必须大于等于1。
计算规则如下：
每次从N+1个数中选择一个数（每个数可选择任意次，且N+1个数可以不全部使用），对选择的数进行加减操作，要求最终结果为-1。
示例：当N=2，M=18，自行选取的N+1个数为（5,15,18），通过计算得出：
18+18+18-5-5-15-15-15=-1
注意：不是所有的N+1个正整数都可以通过计算得到-1。例如，当N=2，M=18，如果自行选取的N+1个数为（12,15,18），则无论怎样计算也不可能得到-1。
题目要求如下：
（1）请根据题意设计算法，并加以文字说明。
（2）编程实现算法，按照题目中的数据N=2，M=18来验证程序的正确性。
（3）假设输入N=2，M=4，输出所有通过计算不能得到-1的数字组合。
【分 数】40分

3、随着触屏手机的兴起，基于触屏的各种小游戏层出不穷，其中有一款游戏叫做“埋炸弹”。它的基本玩法是由玩家购买一定数量的炸弹，使炸弹覆盖的范围尽量大，以便消灭更多的敌人。现在将游戏简单化，假设游戏地图是由M*N个方格组成的矩阵，如果在其中一个方格中埋入炸弹，那么炸弹除了自己所在的方格外，还可以覆盖上、下、左、右四个方格。
试给出一个最佳的埋弹方法，使得炸弹能够覆盖整个地图，且使用的炸弹最少。
题目要求如下：
（1）请根据题意设计算法，并加以文字说明。
（2）编程实现算法，假定M=10，N=8，输出使用的最少炸弹数，以及埋弹方法（结果用10×8矩阵表示，1代表埋炸弹，0代表不埋炸弹）。
【分 数】40分

3