算法分析与设计文档(1)

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