sy5.cpp

用动态规划的方法找出两个序列的最长公共子序列

//动态规划求最长公共子序列。
//L[i][j]存储最长公共子序列的长度的迭代过程。
//S[i][j]存储相应的状态。最长公共子序列存储在数组z[k]中。
//x[m]、y[n]原始序列X,Y。
#include<iostream>
using namespace std;


int L[7][10],S[7][10];//已初始化
int *z;
int CommonOrder(int m,int n,int x[],int y[]){
	int i,j,k;

	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++)
			if(x[i-1]==y[j-1])           {L[i][j]=L[i-1][j-1]+1;S[i][j]=1;}
			else if(L[i][j-1]>=L[i-1][j]){L[i][j]=L[i][j-1];S[i][j]=2;}
			else                         {L[i][j]=L[i-1][j];S[i][j]=3;}

	cout<<"存放最长子序列迭代过程的L数组如下："<<endl;
	for(i=0;i<7;i++){
		for(j=0;j<10;j++)
			cout<<L[i][j]<<" ";
		cout<<endl;
	}
	cout<<endl;

	cout<<"存放相应状态的S数组如下："<<endl;
	for(i=0;i<7;i++){
		for(j=0;j<10;j++)
			cout<<S[i][j]<<" ";
		cout<<endl;
	}
	cout<<endl;
	
	i=m;j=n;k=L[m][n];
	z=new int [k];
	while(i>0&&j>0){
		if(S[i][j]==1){z[k-1]=x[i-1];k--;i--;j--;}
		else if(S[i][j]==2)j--;
			else i--;
	}
	return L[m][n];
}
void main(){
	int x[]={1,2,3,2,4,2};
	int y[]={1,3,2,2,1,2,4,2,2};
	int m=6,n=9,i,j,k;
	cout<<"X序列为：";
	for(i=0;i<m;i++)
		cout<<x[i]<<"  ";
	cout<<endl;
	cout<<"Y序列为：";
	for(j=0;j<n;j++)
		cout<<y[j]<<"  ";
	cout<<endl<<endl;

	k=CommonOrder(m,n,x,y);
	cout<<"最长公共子序列如下："<<endl;
	for(i=0;i<k;i++)
		cout<<z[i]<<"  ";
	cout<<endl;
	cout<<"最长公共子序列的长度为： "<<k<<endl;
	delete [] z;//释放动态生成的空间
	
}