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

2014课程设计要求及题目一、课程设计任务在1周的时间内完成一组题目时间：19周下午地点：班级地点教师（暂定）1238-1，24-313韩逢庆，刘祥1238-3，44-314（周1，4，5），4-207、208（周2），4-209（周3）韩逢庆，朱常鹏1238-5，6，74-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，它们有多相似呢？测量两个基因的相似度一种方法称为对齐。使用对齐方法可以在基因的适当位置加入空格，让两个基因的长度相等，然后根据基因的分值矩阵计算分数。ACGT-A5-1-2-1-3C-15-3-2-4G-2-35-2-2T-1-2-25-1-3-4-2-1*比较AGTGATG与GTTAG要2.棋盘覆盖问题在一个2k2k（k0）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格。显然，特殊方格在棋盘中可能出现的位置有4k种，因而有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所需的时间分别为ai和bi，1in。流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。2地图着色问题1设计内容：已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使用的颜色总数最少。2设计要求：（1）设计该问题的核心算法；（2）设计可视化的界面，界面中能显示和区分中国地图中各省、市、自治区； （3）程序能正确对地图着色。第三组题目1. 数字三角形问题如图所示的数字三角形，从顶部出发，在每一结点可以选择向左走或向右走，一直走到底层。试设计一个算法，计算出从三角形的顶至底的一条路径，使该 路径经过的数字总和最大。要用图形界国面，根据输入数塔的高度自动生成数塔吊，并给出数塔从顶部到低部的路径。2 学校超市选址问题（带权有向图的中心点）设计内容：对于某一学校超市，其他各单位到其的距离不同，同时各单位人员去超市的频度也不同。请为超市选址，要求实现总体最优。设计要求：（1）设计该问题的核心算法；（2）设计可视化的界面，界面中能有效显示学校超市可设立的地点和各单位的位置以及它们之间的有效路径； （3）程序能自动计算出最优设立点，并最好以图示化方式演示。第四组题目设计一个演示系统动态演示快速排序、归并排序的执行过程。第五组题目设计一个演示系统动态演示最长公共子序列以及矩阵链相乘的执行过程。（演示填表的过程）第六组题目设计一个演示系统动态演示m着色问题、及背包问题算法的执行过程。第四五六组题目要求：（1） 语言不限，可以用AS通过Flash编写（2） 实例要能根据用户输入产生（3） 可以自动演示或根据用户的提示一步一步演示。（4） 做该组题目的同学可以20周答辨。算法分析与设计课 程 设 计 报 告 学院（系）： 软件工程系 班 级： 学生姓名： 学号 指导教师： 时间： 从2015年1月 12 日 到 2014年 1月16日目录背包问题1题目一 背包问题1. 问题描述：2. 解决问题所用的方法及基本思路：3. 采用的数据结构描述：4.