《算法设计与分析》实验报告
- 格式：doc
- 大小：93.50 KB
- 文档页数：7
湖南涉外经济学院计算机科学与技术专业《算法设计与分析》课程
最长公共子序列问题
实验报告
班级：
学号：
姓名：
教师：
成绩：
2012年5月
【实验目的】
1 掌握动态规划和LCS的相关算法
2 利用动态规划的思想实现最长公共子序列
3 分析实验结果，总结算法的时间和空间复杂度。
【系统环境】
Windows 7 平台
【实验工具】
VC++6.0中文企业版
【问题描述】
描述：在给定的两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z 是X和Y的公共子序列；给定两个序列X={x1,x2……,xm}和Y={y1,y2……,yn},找出X和Y 的最长公共子序列。
要求：①、在算法LCSLength和LCS中，可进一步将数组的B省去。
事实上，数组元素C[i][j]的值仅有C[i-1][j-1],C[i-1][j]和C[i][j-1]这三个数组元素的值所确定。
②、在只需要计算最长公共子序列的长度时只用到C数组的第i行和第i-1行。
例：若X={A,B,C,B,D,A,B},Y={B,D,C,A,B,A}则序列{B,C,A}是X和Y的一个公共子序列，但它不是X和Y的一个最长公共子序列。
序列{B,C,B,A}也是X和Y的一个公共子序列，它的长度为4，而且它是X和Y的最长公共子序列，因为X和Y没有长度大于4的公共子序列。
【实验原理】
一、最长公共子序列具有最优子结构：
设序列X={x1, x2, …, x m}, Y={y1, y2, …, y n}, Z={z1, z2, …, z k},则
(1)若x m = y n, 则Z k - 1 是X m–1和Y n–1的最长公共子序列；如：X = {…, C}, Y = {…, C},
则Z = {…, C}；
(2)若x m≠ y n, 且z k≠ x m，则Z是X m–1和Y的最长公共子序列；如：X = {… , C}, Y = {…,
B}, z k≠C, 则在计算最长公共子序列时，可不考虑X的最后一个元素C；
(3)若x m≠ y n, 且z k≠ y n，则Z是X和Y n– 1的最长公共子序列如：X = {… , C}, Y = {…, B},
z k≠B, 则在计算最长公共子序列时，可不考虑Y的最后一个元素B
二、最长公共子序列具有重叠子性质：
由最长公共子序列问题的最优子结构性质可知，要找出X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列，可按以下方式递归地进行：当xm=yn是，找出Xm-1和Yn-1的最长公共子序列，然后再其尾部加上xm（=yn）即可得X和Y的最长公共子序列。
当X m≠y n时，必须解两个子问题，即找出Xm-1和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列。
这两个公共子序列中较长者即为X和Y的最长公共子序列。
由此递归结构容易看到，最长公共子序列问题具有子问题的重叠性质。
例如，在计算X和Y的最长公共子序列时，可能要计算X和Y n-1及X m-1和Y的最长公共子序列。
而这两个子问题都包含一个公共子问题，即计算Xm-1和Yn-1的最长公共子序列。
例：字符串X={A,C,B,D},字符串Y={A,B,D,A}，下面是数组C的数据
A
C
B
D
由表可知X[1]=Y[1]，所以C[1][1]=C[0][0]+1；如X[1] ≠Y[2],而C[0][2]<C[1][1],此时
C[1][2]=C[1][1];X[2]=Y[3]，所以C[2][3]=C[1][2]+1
三、程序的介绍
本程序主要包括四个函数分别是：LCSLength()、LCS()、RandChar()。
下面分别介绍三个函数的功能：
1、LCSLength是本程序实现动态规划的核心算法，主要以X和Y为输入，C为输出。
C[i][j]
存储Xi和Yj的最长公共子序列的长度。
该问题的最优值，即X和Y的最长公共子序列的长度记录在C[m][n]中。
2、LCSLengh1算法是只用C数组的第i行和第i-1行，找到最长公共子序列的长度。
3、LCS算法实现根据C内容的来源判断出X与Y相等的值的位置。
通过调用该算法可以打
印出序列X和Y的最长公共子序列。
4、RandChar()，该函数的主要功能使随机产生一个字符，因为在输入X和Y字符串时太麻烦了，所以我根据随机产生一个整数的函数，写了一个可以随机产生字符的函数。
方便了许多。
【源程序代码】
#include<iostream>
#include<cstdlib>
#include<ctime>
#define N 1000
using namespace std;
char x[N],y[N];
int c[N][N];
void LCSLength(int m,int n,char x[],char y[],int c[][N])
{
int i,j;
for(i=1;i<=m;i++)c[i][0]=0;//初始化C数组的列
for(i=1;i<=n;i++)c[0][i]=0;//初始化C数组的行
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{
if(x[i]==y[j])//如果X字符串的第i个与Y字符串的第j个相等则将c[i-1][j-1]+1的值赋值给c[i][j]
{
c[i][j]=c[i-1][j-1]+1;
}
else
if(c[i-1][j]>=c[i][j-1])
{
c[i][j]=c[i-1][j];
}
else
{
c[i][j]=c[i][j-1];
}
}
}
int LCSLength1(int n,char x[],char y[])
{
int s;
for(int i=1;i<=n;i++)
{
s=i%2;
for(int j=1;j<=n;j++)
{
if(x[i-1]==y[j-1])
L[s][j]=L[(s+2-1)%2][j-1]+1;
else
{
if(L[s][j-1]>=L[(s+2-1)%2][j])
L[s][j]=L[s][j-1];
else
L[s][j]=L[(s+2-1)%2][j];
}
}
}
return L[s][n];
}
void LCS(int i,int j)//根据C[i][j]的当前内容，判断C[i][j]当前内容的来源，如果C[i][j]当前内容由C[i-1][j-1]+1而来，那么输出该位置X或Y的内容。
{
if(i==0||j==0)
return ;
if(c[i][j]==c[i-1][j-1]+1)
{
LCS(i-1,j-1);
cout<<x[i];
}
else
if(c[i][j]==c[i-1][j])
{
LCS(i-1,j);
}
else
LCS(i,j-1);
}
char RandChar()//随机产生字符
{
int a;
char ch;
A:a=rand()%122;
if((a<=90&&a>=65)||(a<=122&&a>=97))
ch= char(a);
else goto A;
return ch;
}
int main()
{
int m,n;
cout<<"请输入x和y字符串的大小：";
cin>>m;
cin>>n;
cout<<endl;
cout<<"随机产生x字符串：";
for(int h=0;h<m;h++)
{
x[h]=RandChar();
cout<<x[h];
}
cout<<endl;
cout<<endl;
cout<<"随机产生y字符串：";
for(h=0;h<n;h++)
{
y[h]=RandChar();
cout<<y[h];
}
cout<<endl;
cout<<endl;
cout<<"x和y的最长公共子序列：";
LCSLength(m,n,x,y,c);
LCS(m,n);
cout<<endl;
int length=LCSLength1(n,x,y);
cout<<"最长公共子序列的长度为：";
cout<<length;
cout<<endl;
return 0;
}
【实验结果】。
