《算法设计与分析》课程设计要求

本文格式为Word版，下载可任意编辑——《算法设计与分析》课程设计要求算法设计与分析课程设计要求

一、课程设计的内容和基本要求

利用《算法设计与分析》课程中所学到的编程知识和编程技巧，完成具有一定难度和工作量的程序设计题目，帮助学生把握编程、调试的基本技能，独立完成所布置的任务。参考题目：

题目一,棋牌游戏设计(限2人完成，报告内容注明两个人分工)五子棋;象棋;围棋;军棋;跳棋;24点;斗地主等,

要求:包涵部分格局;设计游戏的核心算法;可视化的软件设计;参考的知识:回溯法;程序语言不限;

题目二,地图着色问题(限1人完成)

设计要求:已知中国地图,对各省进行着色,要求相邻省所使用的颜色不同,并保证使用的颜色总数最少.

题目三,校园导航问题(限1人完成)

设计要求:设计你的学校的平面图,至少包括10个以上的场所,每两个场所间可以有不同的路,且路长也可能不同,找出从任意场所到达另一场所的最正确路径(最短路径).

题目四,学校超市选址问题(带权有向图的中心点)(限1人完成)

设计要求:对于某一学校超市,其他各单位到其的距离不同,同时各单位人员去超市的频度也不同.请为超市选址,要求实现总体最优.

题目五,走迷宫游戏(限1人完成)

程序开始运行时显示一个迷宫地图,迷宫中央有一只老鼠,迷宫的右下方有一个粮仓.游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处.

要求:

老鼠形象可鉴别,可用键盘操纵老鼠上下左右移动;迷宫的墙足够厚实,老鼠不能穿墙而过;

正确检测结果,若老鼠在规定时间内走到粮仓处,提醒成功,否则提醒失败;添加编辑迷宫功能,可修改当前迷宫,修改内容:墙变路,路变墙;找出走出迷宫的所有路径,以及最短路径。

利用序列化功能实现迷宫地图文件的存盘和读出等功能。

题目六,拓扑排序与关键路径在实际中的应用

1.判定问题是否存在拓扑序,假使是求关键路径;求所有关键路径;求关键之关键;

2.将算法用在解决一个实际的应用问题中;

3.分析在数据结构课程中出现的算法是属于我们学过的那一种方法;4.给出新的方法。

题目七,最优二叉探寻树在数据库中的应用实现该算法;

模拟一个数据库,该数据库具有动态的非顺序结构;

题目八,积木游戏的设计

积木为矩形块,区间是矩形的设计;

积木为矩形块,T形块,L形块,区间是矩形的设计;积木为矩形块,T形块,L形块,区间是凸边形的设计;积木为矩形块,T形块,L形块,区间是矩形的设计;积木为矩形块,T形块,L形块,区间是口袋的设计;参考算法:典型的装箱问题(二维,三维)

教材中的算法：1.贪婪算法(1人)

要求:(1)贪婪算法的基本思想

(2)给出背包问题的贪婪算法和程序(3)给出单源最短路径的贪婪算法和程序(4)给出霍夫曼编码问题的贪婪算法和程序2．递归算法(1人)要求:

(1)给出递归的基本思想

(2)给出n阶hanoi塔的递归算法和程序(3)给出数组主元素的递归算法和程序(4)给出n个元素全排列的递归算法和程序(5)给出整数划分问题的递归算法和程序

3.回溯法(1人)要求:

(1)给出回溯法的基本思想

(2)给出n后问题的回溯算法和程序(3)给出0\\1背包问题的回溯算法和程序(4)给出哈密顿回路的回溯算法和程序4.动态规划算法(1人)要求:

(1)动态规划的基本思想

(2)给出多段图的最短路径的动态规划算法和程序

(3)给出资源分派的动态规划算法和程序

(4)给出最长公共子序列的动态规划算法和程序5.分治法(1人)要求:

(1)分治法思想

(2)给出最大最小的算法和程序(3)给出合并排序算法和程序(4)给出快速排序算法和程序

(5)给出多项式乘积和大整数相乘的分治算法和程序

三、课程设计方式、学时分派及安排所有题目均按以下进度执行：

时间安排表序号内容安排备注1方案设计2程序框图3编写程序代码4程序调试分析和结果5课程设计报告和总结总计

课程设计报告内容结构：

一、问题描述：

二、概要设计（流程图）三、源程序

四、运行主要结果界面贴图五、总结

算法设计与分析课程设计

题目：文档：