#include<iostream>
#include<ctime>
using namespace std;
#define N 10
void LCSL(int m,int n,int *x,int *y,int **c,int **b);//计算最长公共子序列长度。
void LCS(int i,int j,int *x,int **b);//根据b[i][j]的内容打印a,x数组的最长公共子序列。
void QuickSort(int a[],int p,int r);//快速排序。
int Partition(int a[],int p,int t);//数组划分,将小于等于x的元素移到x左边,大于x的元素移到x右边。
void Swap(int &x,int &y);//交换元素x和y。
//计算最长公共子序列长度
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)
{
LCS(i-1,j-1,x,b);
for(int y=1;y<i;y++)
if(x[y]==x[i])
return;
cout<<x[i]<<" ";
}
else if(b[i][j]==2)
{
LCS(i-1,j,x,b);
}
else
LCS(i,j-1,x,b);
}
void QuickSort(int a[],int p,int r)
{
if(p<r)
{
int q=Partition(a,p,r);
QuickSort(a,p,q-1);//对左半段排序
QuickSort(a,q+1,r);//对右半段排序
}
}
int Partition(int a[],int p,int r)
{
int i=p,
j=r+1;
int x=a[p];
//将<x的元素交换到左边区域
//将>x的元素交换到右边区域
while(true)
{
while(a[--j]>x);
while((i<j)&&a[++i]<x);
if(i>=j)break;
Swap(a[i],a[j]);
}
a[p]=a[j];
a[j]=x;
return j;
}
void Swap(int &x,int &y)
{
int t;
t=x;
x=y;
y=t;
}
void main(void)
{
int *a,*x;
a=new int[N];
x=new int[N];
int b[N][N];
int c[N][N];
cout<<"请输入十个数:"<<endl;
for(int i=1;i<N;i++)
{
cin>>a[i];
x[i]=a[i];
}
QuickSort(x,1,N-1);
LCSL(N-1,N-1,a,x,c,b);
LCS(N-1,N-1,a,b);
}
lcsLength.rar_LCSength
版权申诉
44 浏览量
2022-09-24
13:59:43
上传
评论
收藏 6KB RAR 举报
我虽横行却不霸道
- 粉丝: 75
- 资源: 1万+
最新资源
- vscode-1.64.1.tar源码文件
- vscode-1.64.0.tar源码文件
- vscode-1.52.0.tar源码文件
- Music-Player +PlayerActivity+ rockplayer+ SeeJoPlayer 播放器JAVA源码
- vscode-1.46.0.tar源码文件
- 最近很火植物大战僵尸杂交版2.08苹果+安卓+PC+防闪退工具V2+修改工具+高清工具+通关存档整合包更新
- 超级好用的截图工具PixPin,可录制Gif图
- Screenshot_2024-05-21-17-06-42-64_2332cb9b27b851b548ba47a91682926c.jpg
- 毕业设计参考 - 基于树莓派、OpenCV及Python的人脸识别
- node-v18.20.2-linux-arm64
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈