lcs_length_main.cpp

使用动态规划方法,实现了最长公共子序列算法,并对动态规划方法作了时间和空间的改进

#include <string.h>
#include <iostream.h>
#include "LCS_Length.h"
#include <time.h>
#include <stdlib.h> 

template<typename T>
void  LCS_Length(T x[],T y[]);      // 计算LCS的长度，并标记
template<typename T>
void PRINT_LCS(T x[],int i,int j);  //构造一个LCS并打印出来

void Rdom(void) ; //随机生成分别含有M个和N个元素的两个序列
double spendtime(clock_t start, clock_t end) ;   // LCS计算P次所用的时间

int b[M][N];     //存放标记
char x[M],y[N];
int P;    //LCS计算次数

//char x[M]={'0','1','2','3','4','5','6','7','8','9'};   //M=10
//char y[N]={'0','1','2','3','4','5','6','7','8','9'};    //N=10

int main(int argc, char* argv[])
{
    clock_t start, end;
    double cost;
    Rdom();  //随机生成分别含有M个和N个元素的两个序列
	cout<<endl;
	LCS_Length<char>(x,y);    // 计算LCS的长度，并标记
	cout<<endl;
    cout<<"序列X和序列Y的最长子序列(LCS)为：:"<<endl;
    PRINT_LCS<char>(x,M-1,N-1);  //构造LCS，并输出
    cout<<endl;

	//根据不同的M值，调整循环次数，减少运行时间
	if(M<50)
		P=1000000;
	else if(M<=500)
		P=100000;
	else if(M<=5000)
		P=10000;
	else if(M<=10000)
		P=1000;
    else 
		P=100;
	cout<<"所用时间还在计算,请等待...................."<<endl;
	cost=spendtime(start, end)/P;
	cout<<"所用时间为:"<<cost<<"s"<<endl;
    return 0;
}

template<typename T>
void  LCS_Length(T x[],T y[])  // 计算LCS的长度，并标记
{
	int i,j;
	int c[M+1][N+1];
	for (i=0;i<=N;i++)
	{
		c[i][0]=0;
	}
	for(j=0;j<=N;j++)
	{
		c[0][j]=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-1][j-1]=LUP;
			}
			else if(c[i-1][j]>=c[i][j-1])
			{
				c[i][j]=c[i-1][j];
				b[i-1][j-1]=UP;
			}
			else
			{
				c[i][j]=c[i][j-1];
				b[i-1][j-1]=LEFT;
			}
		}
	}
}

template<typename T>
void PRINT_LCS(T x[],int i,int j) //构造一个LCS
{
	if(i==-1 || j==-1)
	{
		return;
	}
	if(b[i][j]==LUP)
	{
		PRINT_LCS(x,i-1,j-1);
		cout<<x[i];
		cout<<"  ";
	}
	else if(b[i][j]==UP)
	{
		PRINT_LCS(x,i-1,j);
	}
	else
	{
		PRINT_LCS(x,i,j-1);
	}
}

void Rdom(void)    //随机生成分别含有M个和N个元素的两个序列
{
	srand( (unsigned)time(NULL)); //设置基准
	cout<<"序列X的"<<M<<"个元素为:"<<endl;
	for(int i=0;i<M;i++)
	{
		x[i]= 92+ rand() %25 ;     //序列X
		cout<<x[i]<<"   ";
		if((i+1)%20==0)
			cout<<endl;
	}
	cout<<endl;
	cout<<"序列Y的"<<N<<"个元素为:"<<endl;
	for(i=0;i<N;i++)
	{
		y[i]=92+ rand() %25 ;    //序列Y
		cout<<x[i]<<"   ";
		if((i+1)%20==0)
			cout<<endl;
	}
}

double spendtime(clock_t start, clock_t end)    // LCS计算P次所用的时间
{
   start=clock();  //开始时间

   for(int i=1;i<=P;i++)     //循环P次
   {
       LCS_Length<char>(x,y);    // 计算LCS的长度，并标记
   }
   end=clock();  //结束时间
   return (end - start) / (CLK_TCK);  //CLK_TCK=CLOCKS_PER_SEC=1000 
}