最长公共子序列_实验
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
王典 学号Y201005009
最长公共子序列_实验报告 一、
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
分析
, 问题描述:
若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有:zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。给定2个序列X= {x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列(LCS)。 , 设计思路:
设X=(x1,...xm), Y=(y1,y2,...yn)是两个序列，Z=(z1,z2,...zk)是X与Y的LCS。下列结论成立:
? 如xm=yn, 则zk=xm=yn, Zk-1是Xm-1和Yn-1的LCS，即，
LCSXY=LCSXm-1Yn-1+
.
? 若xm?yn，且zk?xm，则Z是Xm-1和Y的LCS，即
LCSXY=LCSXm-1Y
若xm?yn,且zk?yn,则Z是X与Yn-1的LCS，即 ?
LCSXY=LCSXYn-1
由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。
由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序列xi和yj的最长公共子序列的长度。其中， Xi={x1,x2,…xi};Yj={y1,y2,…,yj}。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时C[i][j]=0。其它情况下，由最优子结构性质可建立递归关系如下:
,00,0ij,,
,cijcijijxy[][][1][1]1,0;,,,，,,,ij
,max[][1],[1][],0;cijcijijxy,,,,,,ij,
二、程序代码
c语言实现
#include #include
#define N 20
void LCSLength(int m,int n,char x[N+1],char y[N+1],char b[N+1][N+1]);
void LCS(int i,int j,char x[N+1],char b[N+1][N+1]);
1
王典 学号Y201005009
{
int i,j,s,t;
int c[N+1][N+1];
for (i=0;i<=m;i++)
c[i][0]=0;
for (i=0;i<=n;i++)
c[0][i]=0;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
{
if (x[i]==y[j])
{
c[i][j]=c[i-1][j-1]+1;
b[i][j]='A';
}
else if (c[i-1][j]>=c[i][j-1])
{
c[i][j]=c[i-1][j];
b[i][j]='U';
}
else
2
王典 学号Y201005009
{
c[i][j]=c[i][j-1];
b[i][j]='L'; }
}
for (s=0;s<=m;s++)
{
for (t=0;t<=n;t++)
printf("%d",c[s][t]);
printf("\n");
}
printf("length=%d\n",c[m][n]);
}
void LCS(int i,int j,char x[],char b[N+1][N+1])
{
if (i==0 || j==0)
return;
if (b[i][j]=='A')
{
LCS(i-1,j-1,x,b);
printf("%c",x[i]);
}
else if (b[i][j]=='U')
LCS(i-1,j,x,b);
else
LCS(i,j-1,x,b);
}
3
王典 学号Y201005009 三、测试用例
四、实验
总结
初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf
通过本实验加深了对动态规划算法的理解，总结出动态规划算法的一般步骤:
1、找出最优解的性质，并刻划其结构特征。
2、递归地定义最优值。
3、以自底向上的方式计算出最优值。
4、根据计算最优值时得到的信息，构造最优解。
4
浙公网安备 33021202002483