2011暑期头脑风暴编程题_IT/计算机_专业资料。部分题目比较难，大家要有决心，想办法都搞定它们。 部分题目比较难，大家要有决心，想办法都搞定它们。开学后将源代码交给我 看看。 看看。 题目命名要求： T+题号的方式命名 题号的方式命名， 题目命名
部分题目比较难，大家要有决心，想办法都搞定它们。 部分题目比较难，大家要有决心，想办法都搞定它们。开学后将源代码交给我 看看。 看看。 题目命名要求： T+题号的方式命名 题号的方式命名， 题目命名要求：请将编写好的源程序以 T+题号的方式命名，例如第 1 题的源程 序保存为“T1.java” ，题目本身有命名要求的除外。 序保存为“T1.java” ） 题目本身有命名要求的除外。 1. 某企业在未来的 12 个月要研究一种新产品，新产品的研制需要四个阶段，每个阶段都可 用慢、正常、快等三种速度进行，时间和成本如下表所列。 理论研究 慢 正常 快 5/5 4/7 2/10 试验阶段 3/6 2/8 1/12 批准 6/1 4/1 2/3 销售 5/8 4/10 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）编程显示每一步交换过程。 ● ● ○ ○ ○ 3. 建造冬奥会滑雪场的空中升降轨道。从起点到终点，有若干可选的支架作为固定点，再 在相邻固定点间架设导轨。假设所有可选的支架在一条轴线（x 轴）上，从起点到终点的 x 轴间隔为 1 的每一点上都有一个支架，并给出支架的高度。建造要求如下： a) b) c) d) 选择尽可能少的支架建立固定点； 导轨保持平直，即固定点中间的支架不高于导轨； 两个相邻固定点之间，沿 x 轴距离不能超过给定的 K； 第一个（起点）和最后一个（终点）一定是固定点。 测试数据文件说明： 测试数据文件说明： 说明 输入文件的内容： 第一行是 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) f) g) 每个球队必须与其他 n-1 个球队各赛一次； 每个球队一天只能赛一次； 当 n 是偶数时，循环赛进行 n-1 天。当 n 是奇数时，循环赛进行 n 天。 n=6 的比赛日程表示例（把 6 个队从 1 到 6 进行编号） ： n=6 的比赛日程表 第一天 1~2 3~5 4~6 第二天 1~3 2~4 5~6 第三天 1~4 2~5 3~6 第四天 1~5 2~6 3~4 第五天 1~6 2~3 4~5 n=5 的比赛日程表示例（增加编号 0，凡碰 0 者该天即轮空） ： n=5 的比赛日程表 第一天 1~0 2~5 3~4 第二天 1~5 0~4 2~3 第三天 1~4 5~3 0~2 第四天 1~3 4~2 5~0 第五天 1~2 3~0 4~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）描述：编写程序，产生由 1，2，3 这 3 个数字符号所构成、长度为 n 的字符串，并且 在字符串中对于任何一个子串而言，都不会有相邻的、完全相同的子串； （2）输入：字符串长度 n； （3）输出：无相邻重复子串的所有字符串，每个字符串换行输出。 例如： Please input string length n: 5 （回车） 屏幕输出: 13121 13123 13212 ……
本文由325棋牌 （www.325games.com）整理发布