课程设计题目求要模板.doc

2014课程设计要求及题目 一、课程设计任务 在1周的时间内完成一组题目 时间：19周下午 地点： 班级 地点 教师（暂定） 1238-1，2 4-313 韩逢庆，刘祥 1238-3，4 4-314（周1，4，5）， 4-207、208（周2）， 4-209（周3） 韩逢庆，朱常鹏 1238-5，6，7 4-210（周1，3，4，5) 4-205206（周2） 董世都，王华秋 二、课程设计成绩评定 1.纪律要求：旷课2次即取消成绩，成绩直接判为不及格； 迟到早退3次则成绩降等级。若迟到早退超过了一节课则判为旷课一天。 成绩 文档占40%，程序占30%，答辩占30%。 2 文档要求： （1）采用什么算法设计方法:分治？动态规划？贪心？回溯？分支限界？等。 （2）算法采用哪些数据结构 （3）算法描述(自然语言，伪代码都可以) （4）算法的时间空间复杂度分析 3 程序要求： （1）要有良好的界面。 （2）要能理解所有出现在程序中的语句。 （3）要能解释清楚算法的基本思路。 4 等级 （1）不及格： 文档或程序有明显的抄袭现象，不能回答程序当中的语句的含义，不能描述算法的基本思路。 （2）优秀 提出“申优”申请，界面良好，文档规范，准确回答老师的问题，有独特功能等出众的表现(会向做算法演示系统的倾斜)。 （3）良好 界面良好，文档规范，准确回答老师的问题。 （4）中 完成了规定的题目，文档及程序完整， 能基本准确地回答老师的问题。 （5）及格 完成了规定的题目，文档及程序完整。 第一组题目 要求完成2个题目 1. 基因序列比较 人类基因由4种核苷酸，分别用字母ACTG表示。要求编写一个程序，按以下规划比较两个基因序列并确定它们的相似程度。即两 给出两个基因序列AGTGATG和GTTAG，它们有多相似呢？测量两个基因的相似度一种方法称为对齐。使用对齐方法可以在基因的适当位置加入空格，让两个基因的长度相等，然后根据基因的分值矩阵计算分数。 A C G T - A 5 -1 -2 -1 -3 C -1 5 -3 -2 -4 G -2 -3 5 -2 -2 T -1 -2 -2 5 -1 - -3 -4 -2 -1 * 比较AGTGATG与GTTAG 要 2.棋盘覆盖问题 在一个（k≥0）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格。显然，特殊方格在棋盘中可能出现的位置有种，因而有4k种不同的棋盘，图a所示是k=2时16种棋盘中的一个。棋盘覆盖问题（chess cover problem）要求用图 (b)所示的4种不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。 图a 图b 图c 结果 （1） 设计出基本的数据结构，算法，程序 （2） 棋盘大小可以变化。 （3）分析算法的时间复杂度 （4） 设计结果应用图形化表示如图C 第二组题目 1. 流水作业调度问题 n个作业{1,2,………,n}要在由两台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为a[i]和b[i]，1≤i≤n。流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。 2地图着色问题 1．设计内容： 已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使用的颜色总数最少。 2．设计要求： （1）设计该问题的核心算法； （2）设计可视化的界面，界面中能显示和区分中国地图中各省、市、自治区； （3）程序能正确对地图着色。 第三组题目 1. 数字三角形问题 如图所示的数字三角形，从顶部出发，在每一结点可以选择向左走或向右走，一直走到底层。试设计一个算法，计算出从三角形的顶至底的一条路径，使该 路径经过的数字总和最大。 要用图形界国面，根据输入数塔的高度自动生成数塔吊，并给出数塔从顶部到低部的路径。 2 学校超市选址问题（带权有向图的中心点） 设计内容：对于某一学校超市，其他各单位到其的距离不同，同时各单位人员去超市的频度也不同。请为超市选址，要求实现总体最优。 设计要求： （1）设计该问题的核心算法； （2）设计可视化的界面，界面中能有效显示学校超市可设立的地点和各单位的位置以及它们之间的有效路径； （3）程序能自动计算出最优设立点，并最好以图示化方式演示。 第四组题目 设计一个演示系统动态演示快速排序、归并排序的执行过程。 第五组题目 设计一个演示系统动态演示最长公