2007算法设计与分析_课程设计大纲

《算法设计与分析课程设计》大纲适用于四年制本科计算机应用技术、信息与计算科学专业（参考学时数：64 学时）一、课程代码二、设计的性质、任务算法设计与分析课程设计是与对应课程配套的一个实践性教学环节。

它是连接算法设计与分析理论教学课程与实际运用的桥梁，也是毕业设计的一项练兵。

学生通过这门课的学习能够更好地掌握算法设计与分析的理论部分的内容，同时将理论运用于实践，提高综合应用算法设计的能力，通过分析算法进而对算法进行优化。

经过这一阶段的训练，使学生得到抽象能力、演绎推理能力、综合概括能力的提高。

三、设计的基本要求1．充分掌握算法设计与分析理论课的基本内容；2．1－2名学生构成一个小组；3．学生可从教师当年提出的课题中选择一个题目。

如果学生自命题，学生应在老师的指导下完成题目的所有规范的文档，提交院学术委员会讨论通过；4．学生可从不同方式、渠道获取相关知识完成课程设计，但杜绝任何形式的抄袭和剽窃，或他人代做行为；5．学生应将设计内容按学校规定的格式提交设计报告（包括书面、电子文档各1份）；6．一名教师最多可以指导30名学生；7．指导教师每周指导学生的时间不少于10学时；四、设计内容参见附件：算法设计与分析课程设计题目五、建议设计的时间分配两周，计1个学分六、成绩考核办法课程成绩＝工作态度分（10分）＋课程设计内容（75分）×选择的题目的难度系数＋课程设计报告的书写（15分）＝100分；七、教材及主要参考书教材：《算法设计与分析》宋文等编重庆大学出版社，2001。

参考书：[1] 《算法设计与分析》周培德电子工业出版社，2000。

[2] 《算法设计与分析》王晓东电子工业出版社，2004八、大纲使用说明课程设计的题目每年都在变。

当年题目由各指导教师提交学院学术委员会通过，再向学生公布。

附件1：《算法设计与分析》课程设计要求及题目一．课程设计的目的课程设计的目的是训练学生灵活应用所学的算法设计与分析知识，独立完成问题分析、总体设计、详细设计和编程实现等软件开发全过程的综合实践能力。

巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。

二．课程设计的要求在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过类的设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。

前期准备工作完备与否直接影响到后序上机调试工作的效率。

在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率。

三．课程设计的内容题目一：五子棋游戏软件设计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．设计要求：（1）设计游戏的核心算法；（2）设计可视化的界面且双方所使用的两色棋子和彩色棋盘得体大方、比例恰当；棋盘：棋盘纵横十九条线，棋子要下在线与线的交叉点上，方格中不能放入棋子。

交叉点的数目是19*19=361个。

为了便于识别棋子的位置，棋盘上划了九个点，术语称做“星＂，中央的星点又称为“天元＂。

下让子棋时，所授之子要放在星上。

棋盘可分为九个部分：四个“角＂，即左上角、左下角、右上角、右下角；四条“边＂，即上边、下边、左边、右边；角、边以外的地方就是“中腹”。

棋子：棋子以黑和白区别各自的一方。

棋子的数量和棋盘的交点相同，黑181个，白180个，合计361个。

不过一次对局不会全部用完，也就是说不需要这么多棋子就可以对局；（3）双方轮流用键盘或鼠标下子。

只有当鼠标单击在棋盘网格交叉点附近时才可下子，点击其他地方及已有子的位置不能下子，且应给出相应提示；（4）在适当位置可显示比赛结果，比赛中能随时存储当前棋局。

题目四：陆军棋游戏软件设计1．设计内容：陆军棋是小朋友喜欢玩的游戏。

陆军棋的目的是攻占对方的军旗,而由于棋子都是盖着的,因此在布署、进攻及防守时都有其学问,是一个相当好玩的策略益智游戏。

现要求设计一程序能完成陆军棋游戏功能，满足下面要求：（1）其中棋盘布局为：行走路线包括公路线和铁路线，显示较细的是公路线，任何棋子在公路线上只能走一步，显示为粗黑的为铁路线，铁路上没有障碍时，工兵可在铁路线上任意行走，其它棋子在铁路线上只能直走或经过弧形线，不能转直角弯；（2）棋子落点包括结点、行营、两个司令部，行营是个安全岛，进入以后，敌方棋子不能吃行营中的棋子，军旗必须放在司令部中，进入任何司令部的棋子不能再移动；（3）棋子布局的限制为：炸弹不能放在第一行，地雷只能放在最后两行，军棋只能放在司令部；（4）吃子规则为：司令>军长>师长>旅长>团长>营长>连长>排长>工兵，但只有工兵可以挖地雷。

工兵可以顺着1黑1白的轨道走，只要不出轨道走多远都可以。

军旗与地雷不能走，任何人都可以抗军旗！军旗没了就输了,任何人碰到炸弹会一起消失……；（5）胜负判决方法为：最后的幸存的一方为胜家，军旗被扛、无棋可走、超时5次都会被判负。

2．设计要求：（1）设计游戏的核心算法；（2）设计可视化的界面且双方所使用的两色棋子和彩色棋盘得体大方、比例恰当；（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．设计内容：已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使用的颜色总数最少。