四川大学_算法分析与设计_左劼
4星 · 超过85%的资源 需积分: 18 183 浏览量
2009-11-15
16:01:46
上传
评论 2
收藏 28KB DOCX 举报 
算法分析 3-1：
题目分析：
要求出 n 个数组成的序列的最长单调递增子序列，假设有数组 a,x.就是将将数组 a 复制
到数组 x,先用排序算法将数组 x 排序，在调用查找最长公共子序列的算法求出数组 a 和数
组
x 中的最长公共子序列，因为数组 x 是单调递增的，所以由此求出来的最长公共子序列就是
题设所求的最长单调递增子序列。题目要求在 O(n*n)的时间内找出 n 个数组成的序列的最
长单调递增子序列,需要用到排序算法，查找最长公共子序列的算法。
具体实现如下：
//计算最长公共子序列长度
void LCSL(int m,int n,int *x,int *y,int c[][N],int b[][N])
{
c[0][0]=0;
int i,j;
for(i=1;i<=m;i++)
c[i][0]=0;
for(i=1;i<=n;i++)
c[0][i]=0;
for(i=1;i<=m;i++)
for(j=1;j<=m;j++)
{
if(x[i]==y[j])
{
c[i][j]=c[i-1][j-1]+1;
b[i][j]=1;
}
else if(c[i-1][j]>=c[i][j-1])
{
c[i][j]=c[i-1][j];
b[i][j]=2;
}
else
{
c[i][j]=c[i][j-1];
b[i][j]=3;
}
}
cout<<c[m][m]<<endl;
}
//根据 b[i][j]的内容打印 a,x 数组的最长公共子序列
void LCS(int i,int j,int *x,int b[][N])
{
if(i==0||j==0) return;
if(b[i][j]==1)
剩余14页未读，继续阅读
资源评论
z9320999252013-10-24当做参考还是可以的
qmsggg2013-06-01很好 ， 当时不能拿来交作业，还是要自己写- ffddp2013-06-20参考使用了。有些帮助吧
