《算法分析与设计》
课程设计报告
学院（系）：软件工程系
班级：2
学生姓名：邹军学号
指导教师：
时间：从2015年1月12 日到2014年1月16日
目录
基因序列比较问题 (1)
棋盘覆盖问题 (6)
题目一基因序列比较问题
1. 问题描述：人类基因由4种核苷酸，分别用字母ACTG表示。
随意给出两个基因序列，比如：AGTGATG和GTTAG，它们有多相似呢？测量两个基因的相似度一种方法称为对齐。
使用对齐方法可以在基因的适当位置加入空格，让两个基因的长度相等，然后根据基因的分值矩阵计算分数。
2.解决问题所用的方法及基本思路：关于基因序列问题，采用了动态规划思想，即将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
关键是找出两个基因序列的最长公共子序列，利用LCS算法可以找出任意两个序列的最长公共子序列，然后采用补齐的方式，将两个基因序列对齐，并将两
个序列相同的部分对应到指定的位置，空出来的地方填写相应的标识符。
LCS算法设序列X={x1,x2,x3.......x m}和Y={y1,y2,y3........y n}的一个最长公共子序列Z={z1,z2,z3......z k},则有
(1）若x m=y n,z k=x m=y n，且Z k-1是X m-1和Y n-1的最长公共子序列；
(2）若x m≠y n,且z k≠x m，则Z是X m-1和Y的最长公共子序列；
(3）若x m≠y n,且z k≠y n,则Z是X和Y n-1的最长公共子序列。
X m-1={x1,x2....xm-1},Y n-1={y1,y2.....yn-1},Z k-1={z1,z2....zk-1} 3. 采用的数据结构描述：
（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. 问题描述：在一个（k≥0）个方格组成的棋盘中，恰有一
个方格与其他方格不同，称该方格为特殊方格。
显然，特殊方格在棋盘中可能出现的位置有种，因而有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(dr<s并且dc<s)
递归调用ChessBoard
Else
覆盖棋盘(tr+s-1,tc+s-1)的位置
递归调用ChessBoard
//覆盖右上角子棋盘
If(dr<s并且dc>s)
递归调用ChessBoard
Else
覆盖棋盘(tr+s-1,tc+s)的位置
递归调用ChessBoard
//覆盖左下角子棋盘
If(dr>s并且dc<s)
递归调用ChessBoard
Else
覆盖棋盘(tr+s,tc+s-1)的位置
递归调用ChessBoard
//覆盖右下角子棋盘
If(dr>s并且dc>s)
递归调用ChessBoard
Else
覆盖棋盘(tr+s,tc+s)的位置
递归调用ChessBoard
}
6.算法的时间空间复杂度分析
(1)时间复杂度
棋盘覆盖题目中，时间花费主要集中于覆盖时的递归调用。
因此，时间复杂度为O(nlog8n)+4O(1)
(2)空间复杂度
空间的花费并不是太大，主要集中在存储覆盖后的二维数组，故空间复杂度为O(m*n)(m与n取决于输入棋盘的规模大小)
6.算法实例：
数据的输入
数据的输出
课程设计总结。
