main.cpp

设计一个O(n2)时间的算法

#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;

}



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];

 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;

}

 

int main()

{

       int *a,*x;

       a=new int[N];

       x=new int[N];

		int b[N][N];

       int c[N][N];

       cout<<"Please Input 10 Numbers:"<<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);
		return 0;

}