算法设计课程设计任务书

1、算法设计与分析课程设计任务书所属学期：10-11-2 下达时间：完成班级：信本08【设计目的】本课程设计是信息与计算科学专业重要的实践性环节之一，是在学生学习完算法设计 与分析课程后进行的一次全面的综合练习。本课程设计的目的和任务：（1）巩固和加深学 生对本课程的基本知识的理解和掌握；（3）掌握基本算法的设计与实现；（3）掌握算法设计 的基本思想；（4）提高解决实际问题的能力；（5）掌握书写程序设计说明文档的能力。【设计内容与任务】题目一：五子棋游戏软件设计设计内容：设计一程序能完成五子棋游戏功能。五子棋规则：双方各执一色棋子，轮流下子（即将棋子放在棋盘 的任一空交叉点上），直到有一方的棋子有

2、5个排成一线（无论是横向、竖向还是斜向均可），则棋局结 束，该方胜利。设计要求：（1）设计游戏的核心算法；（2）设计可视化的界面且双方所使用的两色棋子和彩色棋盘得体大方、比例恰当；（3）双方轮流用键盘或鼠标下子。只有当鼠标单击在棋盘网格交叉点附近时才可下子，点击其他地方及已有子的位置不能下子，且应给出相应提示；（4）在适当位置可显示比赛结果，比赛中能随时存储当前棋局。题目二：象棋游戏软件设计设计内容：中国象棋是中国一种流传十分广泛的游戏。下棋双方根据自己对棋局形式的理解和对棋艺规律的掌 握，调动车马，组织兵力，协调作战在棋盘一一这块特定的战场上进行着象征性的军事战斗。设计软件能 实现此游戏。游

3、戏规则：“将”或“帅”的移动范围只能在王宫内，移动规则为每一步只可以水平或垂直移动一点。“士”的移动范围只能在王宫内，移动规则为每一步只可以沿对角线方向移动一点。“象”的移动范围为河界的一侧，移动规则为每一步只可以沿对角线方向移动两点，另外，在移动的 过程中不能够穿越障碍。“马”的移动范围为任何位置，移动规则为每一步只可以水平或垂直移动一点，再按对角线方面向左 或者右移动。另外，在移动的过程中不能够穿越障碍。“车”的移动范围为任何位置，移动规则为可以水平或垂直方向移动任意个无阻碍的点。“炮”的移动范围为任何位置，移动规则为和车相似，但它必须跳过一个棋子来吃掉对方的一个棋子。“兵”的移动范围为任

4、何位置，移动规则：每步只能向前移动一点。过河以后，它便增加了向左右移 动的能力，兵不允许向后移动。设计要求：设计游戏的核心算法；设计可视化的界面且双方所使用的两色棋子和彩色棋盘得体大方、比例恰当；棋子活动的场所棋盘，在长方形的平面上，绘九条平行的竖线和十条平行的横线相交组成，共 九十个交叉点，棋子就摆在这些交叉点上。中间第五、第六两横线之间未画竖线的空白地带，称为河界 ，整个棋盘就以河界分为相等的两部分；两方“将”“帅”坐镇。各棋子为：红方：帅(1)、仕(2)、相(2)、车(2)、马(2)、炮(2)、兵(5)黑方：将(1)、士 (2)、象(2)、车(2)、马(2)、炮(2)、卒(5)双方轮流用

5、键盘或鼠标下子。只有当鼠标单击在棋盘网格交叉点附近时才可下子，点击其他地方及已有子的位置不能下子，且应给出相应提示；在适当位置可显示比赛结果，比赛中能随时存储当前棋局。题目三：跳棋游戏软件设计设计内容：跳棋在我国是一项老少皆宜、流传广泛的益智型棋类游戏。由于其规则简单，一玩就懂，一辈子都不 会忘，所以几乎每个人从小到大都下过跳棋。设计一程序能完成跳棋游戏功能。跳棋规则和胜负判定方法如下：首先，游戏参与人数必须是偶数，即2人、4人或者6人，然后与对角线的一方对抗。棋子的移动可 以一步步在有直线连接的相邻六个方向进行，如果相邻位置上有任何方的一个棋子，该位置直线方向下一 个位置是空的，则可以直接跳

6、到该空位上，跳的过程中，只要相同条件满足就可以连续进行。谁最先 把正对面的阵地全部占领，谁就取得胜利。设计要求：设计游戏的核心算法；设计可视化的界面且双方所使用的两色棋子和彩色棋盘得体大方、比例恰当；双方轮流用鼠标出子；在适当位置可显示比赛结果，比赛中能随时存储当前棋局。题目四：24点游戏软件设计设计内容：24点游戏为随机产生的四个数，通过四则计算(每个数只能使用一次)，使其结果为24.本游戏对培 养人们的注意力、计算力(尤其是心算能力)，开阔人们的思路，大有益处。游戏规则为：每次由计算机随机给出1至10四个数字，使用这些数字计算，使结果等于24。要求：只能使用加、减、乘、除四种运算；每一数字

7、必须且只能使用一次。如果用户能做题目，则可以通过把数字拖到两个方框中，并选择一种运算来显示他的计算步骤。 每一步骤，只能计算两个方框中的数字，其结果能用于下一步。例如，如果给出数字1、2、3和4；可以这样做：步骤 1： 3*4=12步骤 2： 2*12=24步骤3： 24*1=24(每一数字必须被使用一次)有时不能从诸如1、1、1、1或者9、9、9、9的四个数中得到结果“24”，当遇到困难或确信不能得 到数字“ 24 ”时，可以点按“帮助”按钮查看答案或者点按“开始”按钮做下一道题。设计要求：设计游戏的核心算法；设计可视化的界面；能随机产生4个1位数并显示；用户能利用鼠标或键盘选择给出的数和运

8、算符；程序能判别正误并计分；能给出帮助和能重产生数。题目五：利用贪婪算法实现多种实际问题设计内容：给出多种可以用贪婪算法解决的典型问题，并分析、证明、编程。设计要求：贪婪算法的基本思想；给出背包问题的贪婪算法；给出有限期计算机作业调度的贪婪算法；给出上面两个算法的证明；给出上面两个算法的程序。给出时间复杂度。题目六：递归算法的应用设计内容：实现多种问题的递归算法并分析、总结，给出结论。设计要求：给出01背包问题的递归算法和程序；给出n阶hanoi塔的递归算法和程序；给出棋子移动的递归算法和程序；给出n个元素全排列的递归算法和程序；总结哪些问题可能用递归算法实现。题目七：回溯法的应用设计内容：给

9、出多种可以用贪婪算法解决的典型问题，并分析、编程和总结。设计要求：给出回溯法的基本思想；给出n后问题的回溯算法和程序；给出子集和树问题的回溯算法和程序；给出哈密顿回路的回溯算法和程序。题目八：动态规划算法的应用设计内容：实现多种问题的动态规划算法并分析、编程和总结，给出结论。设计要求：给出动态规划的基本思想；给出最小代价子母树的动态规划算法和程序；给出最短路径的动态规划算法和程序；给出最优树的动态规划算法和程序。题目九：分治法的应用设计内容：利用分治法实现多种问题，并分析、编程和总结，给出结论。设计要求：给出分治法思想；给出数据查找的算法和程序；给出合并排序算法和程序；给出快速排序算法和程序；

10、给出矩阵乘法的分治算法和程序；给出多项式乘法的分治法和程序；给出分治法的时间复杂度。题目十一：用二分搜索法查找数据设计内容：折半查找法也称为二分查找法或二分搜索法，它充分利用了元素间的次序关系，采用分治策略而较快 地查找数据。现要求给出一个待查找的实例，并给出二分搜索算法，编写程序利用此算法实现查找。设计要求：给出分治思想；给出一个实际应用；给出二分搜索算法；编程实现算法；给出算法的时间复杂度分析。题目十二：用探索(穷举)法求解货郎担问题设计内容：货郎担问题又称推销员问题，是组合数学中的一个著名问题。求解四个城市的货郎担问题，距离关系 如下：1到2、3、4城的距离分别为6、7、92到1、3、4

11、城的距离分别为8、9、73到1、2、4城的距离分别为5、8、84到1、2、3城的距离分别为6、5、5当推销员从1城出发，经过每个城市一次且仅一次，最后回到1城，问按照怎样的路线走，使总的行 程距离最短。设计要求：给出求解算法；编程实现此算法；以图形化界面各城市间及各城市间的路径和距离；给出时间复杂度分析。题目十三：用分支限界法求解0/1背包问题设计内容：分枝限界是另一种系统地搜索解空间的方法，它与回溯法的主要区别在于对E-节点的扩充方式。每个 活节点有且仅有一次机会变成E-节点。当一个节点变为E-节点时，则生成从该节点移动一步即可到达的所 有新节点。在生成的节点中，抛弃那些不可能导出(最优)可

12、行解的节点，其余节点加入活节点表，然后 从表中选择一个节点作为下一个E-节点。从活节点表中取出所选择的节点并进行扩充，直到找到解或活动 表为空，扩充过程才结束。现要求给出一个具体的0/1背包问题，并用分支限界法求解之。设计要求：给出一个实例；编写算法；编程实现；给出分析。十四.自命题【设计要求】1、分析课程设计题目的要求2、写出详细设计说明3、编写程序代码，调试程序使其能正确运行4、设计完成的软件要便于操作和使用5、设计完成后提交课程设计报告，课程设计报告内容包括：课程设计目的、设计任务与 要求、设计说明书、设计成果和设计心得五个部分，具体要求见设计报告模板。6、分组：最多两个人一组，提供一份设计说明书，并注明任务分工。每组题目不能相 同。【设计时间】13周-16周【设计报告】设计报告内容不少3000字。其正文一般有如下几个方面的内容：1、课程设计名称、班级号、学号、学生姓名和课程设计起止日期2、课程设计目的和要求3、课程设计任务内容4、详细设计说明5、软件使用说明6、课程设计心得与体会7、附录1：参考文献8、附录2：部分程序清单（带有较详细的注释）【提交要求】（1）每组需独立提交书面设计报告书，要求编排格式统一、规范、内容充实（3）提交日期：第17周以前，以班为