算法设计课程设计任务书

算法设计与分析课程设计任务书所属学期： 下达时间：完成班级：【设计目的】本课程设计是信息与计算科学专业重要的实践性环节之一，是在学生学习完算法设计 与分析课程后进行的一次全面的综合练习。本课程设计的目的和任务：（1）巩固和加深学 生对本课程的基本知识的理解和掌握；（3）掌握基本算法的设计与实现；（3）掌握算法设计 的基本思想；（4）提高解决实际问题的能力；（5）掌握书写程序设计说明文档的能力。【设计内容与任务】题目一：五子棋游戏软件设计1. 设计内容：设计一程序能完成五子棋游戏功能。五子棋规则：双方各执一色棋子，轮流下子（即将棋子放在棋盘 的任一空交叉点上），直到有一方的棋子有5个排成一线（无论是横向、竖向还是斜向均可），则棋局结 束，该方胜利。2. 设计要求：（1）设计游戏的核心算法；（2）设计可视化的界面且双方所使用的两色棋子和彩色棋盘得体大方、比例恰当；（3）双方轮流用键盘或鼠标下子。只有当鼠标单击在棋盘网格交叉点附近时才可下子，点击其他地方及已有子的位置不能下子，且应给出相应提示；（4）在适当位置可显示比赛结果，比赛中能随时存储当前棋局。题目二：象棋游戏软件设计1. 设计内容：中国象棋是中国一种流传十分广泛的游戏。下棋双方根据自己对棋局形式的理解和对棋艺规律的掌 握，调动车马，组织兵力，协调作战在棋盘一一这块特定的战场上进行着象征性的军事战斗。设计软件能 实现此游戏。游戏规则：“将”或“帅”的移动范围只能在王宫内，移动规则为每一步只可以水平或垂直移动一点。“士”的移动范围只能在王宫内，移动规则为每一步只可以沿对角线方向移动一点。“象”的移动范围为河界的一侧，移动规则为每一步只可以沿对角线方向移动两点，另外，在移动的 过程中不能够穿越障碍。“马”的移动范围为任何位置，移动规则为每一步只可以水平或垂直移动一点，再按对角线方面向左 或者右移动。另外，在移动的过程中不能够穿越障碍。“车”的移动范围为任何位置，移动规则为可以水平或垂直方向移动任意个无阻碍的点。“炮”的移动范围为任何位置，移动规则为和车相似，但它必须跳过一个棋子来吃掉对方的一个棋子。“兵”的移动范围为任何位置，移动规则：每步只能向前移动一点。过河以后，它便增加了向左右移 动的能力，兵不允许向后移动。2. 设计要求：(1) 设计游戏的核心算法；(2) 设计可视化的界面且双方所使用的两色棋子和彩色棋盘得体大方、比例恰当；棋子活动的场所一一棋盘，在长方形的平面上，绘九条平行的竖线和十条平行的横线相交组成，共 九十个交叉点，棋子就摆在这些交叉点上。中间第五、第六两横线之间未画竖线的空白地带，称为河界 ，整个棋盘就以河界分为相等的两部分；两方“将”“帅”坐镇。各棋子为：红方：帅(1)、仕(2)、相(2)、车(2)、马(2)、炮(2)、兵(5)黑方：将(1)、士 (2)、象(2)、车(2)、马(2)、炮(2)、卒(5)(3) 双方轮流用键盘或鼠标下子。只有当鼠标单击在棋盘网格交叉点附近时才可下子，点击其他地方及已有子的位置不能下子，且应给出相应提示；(4) 在适当位置可显示比赛结果，比赛中能随时存储当前棋局。题目三：跳棋游戏软件设计1. 设计内容：跳棋在我国是一项老少皆宜、流传广泛的益智型棋类游戏。由于其规则简单，一玩就懂，一辈子都不 会忘，所以几乎每个人从小到大都下过跳棋。设计一程序能完成跳棋游戏功能。跳棋规则和胜负判定方法如下：首先，游戏参与人数必须是偶数，即2人、4人或者6人，然后与对角线的一方对抗。棋子的移动可 以一步步在有直线连接的相邻六个方向进行，如果相邻位置上有任何方的一个棋子，该位置直线方向下一 个位置是空的，则可以直接跳到该空位上，跳的过程中，只要相同条件满足就可以连续进行。谁最先 把正对面的阵地全部占领，谁就取得胜利。2. 设计要求：(1) 设计游戏的核心算法；(2) 设计可视化的界面且双方所使用的两色棋子和彩色棋盘得体大方、比例恰当；(3) 双方轮流用鼠标出子;(4) 在适当位置可显示比赛结果，比赛中能随时存储当前棋局。题目四：24点游戏软件设计1. 设计内容：24点游戏为随机产生的四个数，通过四则计算(每个数只能使用一次)，使其结果为24.本游戏对培 养人们的注意力、计算力(尤其是心算能力)，开阔人们的思路，大有益处。游戏规则为：每次由计算机随机给出1至10四个数字，使用这些数字计算，使结果等于24。要求：(1) 只能使用加、减、乘、除四种运算；(2) 每一数字必须且只能使用一次。(3) 如果用户能做题目，则可以通过把数字拖到两个方框中，并选择一种运算来显示他的计算步骤。 每一步骤，只能计算两个方框中的数字，其结果能用于下一步。例如，如果给出数字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”时，可以点按“帮助”按钮查看答案或者点按“开始”按钮做下一道题。2. 设计要求：(1) 设计游戏的核心算法；(2) 设计可视化的界面；(3) 能随机产生4个1位数并显示；(4) 用户能利用鼠标或键盘选择给出的数和运算符；(5) 程序能判别正误并计分；(6) 能给出帮助和能重产生数。题目五：利用贪婪算法实现多种实际问题1. 设计内容：给出多种可以用贪婪算法解决的典型问题，并分析、证明、编程。2. 设计要求：(1) 贪婪算法的基本思想；(2) 给出背包问题的贪婪算法；(3) 给出有限期计算机作业调度的贪婪算法；(4) 给出上面两个算法的证明；(5) 给出上面两个算法的程序。(6) 给出时间复杂度。题目六：递归算法的应用1. 设计内容：实现多种问题的递归算法并分析、总结，给出结论。2. 设计要求：(1) 给出01背包问题的递归算法和程序；(2) 给出n阶hanoi塔的递归算法和程序；(3) 给出棋子移动的递归算法和程序；(4) 给出n个元素全排列的递归算法和程序；(5) 总结哪些问题可能用递归算法实现。题目七：回溯法的应用1. 设计内容：给出多种可以用贪婪算法解决的典型问题，并分析、编程和总结。2. 设计要求：(1) 给出回溯法的基本思想；(2) 给出n后问题的回溯算法和程序；(3) 给出子集和树问题的回溯算法和程序；(4) 给出哈密顿回路的回溯算法和程序。题目八：动态规划算法的应用1. 设计内容：实现多种问题的动态规划算法并分析、编程和总结，给出结论。2. 设计要求：(1) 给出动态规划的基本思想；(2) 给出最小代价子母树的动态规划算法和程序；(3) 给出最短路径的动态规划算法和程序；(4) 给出最优树的动态规划算法和程序。题目九：分治法的应用1. 设计内容：利用分治法实现多种问题，并分析、编程和总结，给出结论。2. 设计要求：(1) 给出分治法思想；(2) 给出数据查找的算法和程序；(3) 给出合并排序算法和程序；(4) 给出快速排序算法和程序；(5) 给出矩阵乘法的分治算法和程序；(6) 给出多项式乘法的分治法和程序；(7) 给出分治法的时间复杂度。题目十一：用二分搜索法查找数据1. 设计内容：折半查找法也称为二分查找法或二分搜索法，它充分利用了元素间的次序关系，采用分治策略而较快 地查找数据。现要求给出一个待查找的实例，并给出二分搜索算法，编写程序利用此算法实现查找。2. 设计要求：(1) 给出分治思想；(2) 给出一个实际应用；(3) 给出二分搜索算法；(4) 编程实现算法；(5) 给出算法的时间复杂度分析。题目十二：用探索(穷举)法求解货郎担问题1. 设计内容：货郎担问题又称推销员问题，是组合数学中的一个著名问题。求解四个城市的货郎担问题，距离关系 如下：1到2、3、4城的距离分别为6、7、92到1、3、4城的距离分别为8、9、73到1、2、4城的距离分别为5、8、84到1、2、3城的距离分别为6、5、5当推销员从1城出发，经过每个城市一次且仅一次，最后回到1城，问按照怎样的路线走，使总的行 程距离最短。2. 设计要求：(1) 给出求解算法；(2) 编程实现此算法；(3) 以图形化界面各城市间及各城市间的路径和距离；(4) 给出时间复杂度分析。题目十三：用分支限界法求解0/1背包问题1. 设计内容：分枝限界是另一种系统地搜索解空间的方法，它与回溯法的主要区别在于对E-节点的扩充方式。每个 活节点有且仅有一次机会变成E-节点。当一个节点变为E-节点时，则生成从该节点移动一步即可到达的所 有新节点。在生成的节点中，抛弃那些不可能导出(最优)可行解的节点，其余节点加入活节点表，然后 从表中选择一个节点作为下一个E-节点。从活节点表中取出所选择的节点并进行扩充，直到找到解或活动 表为空，扩充过程才结束。现要求给出一个具体的0/1背包问题，并用分支限界法求解之。2. 设计要求：(1) 给出一个实例；(2) 编写算法；(3) 编程实现；(4) 给出分析。十四.自命题【设计要求】1、分析课程设计题目的要求2、写出详细设计说明3、编写程序代码，调试程序使其能正确运行4、设计完成的软件要便于操作和使用5、设计完成后提交课程设计报告，课程设计报告内容包括：课程设计目的、设计任务与 要求、设计说明书、设计成果和设计心得五个部分，具体要求见设计报告模板。6、分组：最多三个人一组，提供一份设计说明书，并注明任务分工。每组题目不能相 同。【设计时间】13周-16周【设计报告】设计报告内容不少3000字。格式按照：课程设计说明书规范格式.doc【提交要求】(1)每组需独立提交书面设计报告书，要求编排格式统一、规范、内容充实(3)提交日期：第16周以前，以班为单位刻录源程序、设计书电子版【设计时间】第13周一第16周【设计成绩评定】设计成绩按优、良、中、及格、不及格五级评定。指导教师:2015月5日