资源描述：
《算法分析与设计文档(1)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、《算法分析与设计》课程设计报告学院（系）：软件工程系班级：112030802学生姓名：邹军学号11203080239指导教师：时间：从2015年1月12日到2014年1月16日目录基因序列比较问题……………………………………………1棋盘覆盖问题………………………………………………6题目一基因序列比较问题1.问题描述：人类基因由4种核苷酸，分别用字母ACTG表示。随意给出两个基因序列，比如：AGTGATG和GTTAG，它们有多相似呢？测量两个基因的相似度一种方法称为对齐。使用对齐方法可以在基因的适当位置加入空格，让两
2、个基因的长度相等，然后根据基因的分值矩阵计算分数。2.解决问题所用的方法及基本思路：关于基因序列问题，采用了动态规划思想，即将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。关键是找出两个基因序列的最长公共子序列，利用LCS算法可以找出任意两个序列的最长公共子序列，然后采用补齐的方式，将两个基因序列对齐，并将两个序列相同的部分对应到指定的位置，空出来的地方填写相应的标识符。LCS算法设序列X={x1,x2,x3.......xm}和Y={y1,y2,y3........yn}的一个
3、最长公共子序列Z={z1,z2,z3......zk},则有(1）若xm=yn,zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列；(2）若xm≠yn,且zk≠xm，则Z是Xm-1和Y的最长公共子序列；(1）若xm≠yn,且zk≠yn,则Z是X和Yn-1的最长公共子序列。Xm-1={x1,x2....xm-1},Yn-1={y1,y2.....yn-1},Zk-1={z1,z2....zk-1}3.采用的数据结构描述：（2）ArrayList链表结构为了便于后期数据的处理，将输入的两组基因序列分别放入
4、两个不同的链表中，（3）数组本程序中，数组作为中间临时存储的空间（4）String字符串类型4.算法描述：算法名称：基因序列比较输入：任意两组基因序列输出：基因相似度分值分数算法实现细节（可以用流程图，伪代码）publicstaticint[][]lcslength(Stringfo[],Stringfs[]){通过LCS算法计算出两序列的长度数组C[][]，并返回}publicstaticintlcs(intl,ints,intfb[][],String[]fo){由C[][]数组找出相同的基因，并调用相应的分值
5、计算方法}publicstaticintgrade(m,n){通过传递过来的字母m,n找出分值并返回}5.算法的时间空间复杂度分析(1)时间复杂度分析基因序列问题，花费的时间主要集中在填写用于记录的二维数组表。其中填写数组时，用到四个循环，因此，时间复杂度为O(m4)(m的取值与基因序列长度有关)(2)空间复杂度分析基因序列题目中，存储二维数组int[][],假定数组长度为m,n(m,n实际取值视输入字符串以及最终对齐后的长度决定)，则该题目的空间复杂度为O(m*n).6.算法实例：数据的输入数据的输出题目二棋盘覆
6、盖问题1.问题描述：在一个（k≥0）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格。显然，特殊方格在棋盘中可能出现的位置有种，因而有4k种不同的棋盘，图a所示是k=2时16种棋盘中的一个。棋盘覆盖问题（chesscoverproblem）要求用图(b)所示的4种不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。2.解决问题所用的方法及基本思路：针对棋盘覆盖问题，采用分治策略进行解答。分治策略的基本步骤如下：（1）分解：将原问题分解为若干个规模较小，相互独立
7、，与原问题形式相同的子问题。（2）解决：若子问题规模较小而容易被解决则直接解决，否则递归地解决各个子问题。（3）合并：将各个子问题的解合并为原问题的解。关于棋盘覆盖问题，就是利用这三个步骤，首先根据特殊方格所在的位置，将整个棋盘进行划分，并在切分过后的交界处，进行L型骨牌覆盖。如此，每一块切分的区域都含有一块特殊方格，然后递归调用之前的做法，直到每一块区域全部覆盖为止。3.采用的数据结构描述：（1）数组本程序中，数组作为存储的空间4.算法描述：算法名称：棋盘覆盖问题输入：任意输入棋盘规格，特殊方格的横、纵坐标输出：
8、覆盖后的棋盘算法实现细节（可以用流程图，伪代码）publicvoidChessBoard(inttr,inttc,intdr,intdc,intsize){Intt=title++;Ints=size/2;//覆盖左上角子棋盘If(dr
