2011暑期头脑风暴编程题

部分题目比较难 大家要有决心 想办法都搞定它们 开学后将源代码交给我部分题目比较难 大家要有决心 想办法都搞定它们 开学后将源代码交给我 看看 看看 题目命名要求 请将编写好的源程序以题目命名要求 请将编写好的源程序以 T T 题号的方式命名 例如第题号的方式命名 例如第 1 1 题的源程题的源程 序保存为序保存为 T1 java T1 java 题目本身有命名要求的除外 题目本身有命名要求的除外 1 某企业在未来的 12 个月要研究一种新产品 新产品的研制需要四个阶段 每个阶段都 可用慢 正常 快等三种速度进行 时间和成本如下表所列 理论研究试验阶段政府批准销售 慢5 53 66 15 8 正常4 72 84 14 10 快2 101 122 33 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 编程显示每一步交换过程 3 建造冬奥会滑雪场的空中升降轨道 从起点到终点 有若干可选的支架作为固定点 再 在相邻固定点间架设导轨 假设所有可选的支架在一条轴线 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 分 4 设有 n 个球队要进行排球循环赛 设计一个满足以下要求的比赛日程表 e 每个球队必须与其他 n 1 个球队各赛一次 f 每个球队一天只能赛一次 g 当 n 是偶数时 循环赛进行 n 1 天 当 n 是奇数时 循环赛进行 n 天 n 6 的比赛日程表示例 把 6 个队从 1 到 6 进行编号 n 6 的比赛日程表的比赛日程表 第一天第二天第三天第四天第五天 1 21 31 41 51 6 3 5 2 42 52 62 3 4 6 5 63 6 3 44 5 n 5 的比赛日程表示例 增加编号 0 凡碰 0 者该天即轮空 n 5 的比赛日程表的比赛日程表 第一天第二天第三天第四天第五天 1 01 51 41 31 2 2 5 0 45 34 23 0 3 4 2 30 2 5 04 5 1 请根据以上要求分析问题 设计算法 并加以说明 2 编程实现算法 并以 n 10 和 n 15 进行测试 输出结果 3 分析算法的时间复杂度 本题共 60 分 要求 1 占 20 分 要求 2 占 30 分 要求 3 占 10 分 5 编写一个 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 描述可能的改进 改进的方向如效果 算法复杂度 性能等等 6 在下图中的九个点上 空出中间的点 其余的点上任意填入数字 1 至 8 1 的位置保持 不动 然后移动其余的数字 使 1 到 8 顺时针从小到大排列 移动的规则是 只能将数字 沿线移向空白的点 请将制作好的源文件保存为 t2 java 本题共 60 分 要求 1 占 20 分 要求 2 占 40 分 要求 1 分析问题 并描述你的算法设计思想 2 编程显示数字移动过程 7 编写一个 Java 程序要求 开启一个文本文件 一次读取其内的一行文本 令每一行形 成一个 String 并将读出的 String 对象置于 LinkedList 中 请以相反次序印出 LinkedList 内 的所有文本行 public class Input public void input BufferedReader reader new BufferedReader new FileReader new File 文件路径 while true String s reader readLine 读一行 if s null break 8 50 分 现有 21 根火柴 两人轮流取 每人每次可取走 1 4 根 不可多取 也不能不取 谁取最后一根火柴则谁输 请编写一个程序进行人机对弈 要求人先取 计算机后取 计 算机一方为 常胜将军 9 70 分 编程完成商人过河游戏 有三个商人带着三个随从和货物过河 船每次最多只 能载两个人 由他们自己划行 并且如何乘船渡河的大权由商人掌握 要求保证在过河期 间的任一岸上商人的人数要大于或等于随从的人数 否则随从会杀死商人抢走货物 设计 一个符合上述要求的商人过河的游戏 1 有游戏规则提示 按任意键开始游戏 按 Q 键退出游戏 2 程序开始 分别提示每次从河岸这边到那边 从河岸那边到这边的商人和随从人数 3 如果输入错误 如一次输入的人数不得超过 2 个 过河的人数不得超过 2 个 则提 示错误并且按任意键重新开始游戏 4 当任一河岸的商人数小于随从数时 提示商人被杀 按任意键继续游戏 5 当游戏成功时提示游戏成功 按任意键结束游戏 10 产生无连续重复部分的字符串 60 分 1 描述 编写程序