lcs算法c语言代码,LCS算法
求兩個序列的最長公共子序列
x序列為：zxyxyz
y序列為：xyyzx
(動態(tài)規(guī)劃--C語言實現(xiàn))#include?
void?print(int?i,int?j,char?x[],int?a[][6]){
if(i==0||j==0)
return;
if(a[i][j]==1){
print(i-1,j-1,x,a);
printf("%c",x[i]);
}else?if(a[i][j]==2){
print(i,j-1,x,a);
}else{
print(i-1,j,x,a);
}
}
int?main()
{
int?i,j;
char?x[]={'0','z','x','y','x','y','z'};
char?y[]={'0','x','y','y','z','x'};
int?a[7][6]={0};
int?lcs[7][6]={0};
for(i=1;i<=6;i++){
for(j=1;j<=5;j++){
if(x[i]==y[j]){
lcs[i][j]=lcs[i-1][j-1]+1;
a[i][j]=1;
}else
if(lcs[i][j-1]>=lcs[i-1][j]){
lcs[i][j]=lcs[i][j-1];
a[i][j]=2;
}else{
lcs[i][j]=lcs[i-1][j];
a[i][j]=3;
}
}
}
for(i=0;i<=6;i++){
for(j=0;j<=5;j++){
printf("lcs[%d][%d]=%d\t",i,j,lcs[i][j]);
}
printf("\n");
}
printf("最大子序列長度為：%d\n",lcs[6][5]);
printf("最長子序列為：");
print(6,5,x,a);
return?0;
}
總結(jié)
以上是生活随笔為你收集整理的lcs算法c语言代码,LCS算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 秒懂设计模式之状态模式（State Pa
- 下一篇： 基于SpringBoot的共享单车管理系