算法代码

/*
最长公共子序列
*/
#include <stdio.h>
#include <stdlib.h>
const int N=10;
const int M=12;
int LCS_recursion(char A[],char B[],int i,int j)//递归
{
	if (i==0 || j==0) 
		return 0;
	else
	{
	 	if (A[i]==B[j])
			return LCS_recursion(A,B,i-1,j-1)+1;
	  	else
			return LCS_recursion(A,B,i,j-1)>LCS_recursion(A,B,i-1,j)
			?LCS_recursion(A,B,i,j-1):LCS_recursion(A,B,i-1,j);
	}
}

int LCS(char A[],char B[],	int L[][M+1],int n,int m)//非递归
{
	int i,j; 
	for(i=0;i<=n;i++)
		L[i][0]=0;	
	for(j=0;j<=m;j++)
		L[0][j]=0;	
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			if(A[i]==B[j])
				L[i][j]=L[i-1][j-1]+1;
			else
				L[i][j]=L[i][j-1]>L[i-1][j]?L[i][j-1]:L[i-1][j];		
	return L[n][m];
}
void table(char A[],char B[],int L[][M+1])
{
	int i,j;
	printf("       ");
	for(i=1;i<=M;i++)
		printf("%3c",B[i]);
	printf("\n    ");
	for(i=0;i<=M;i++)
		printf("%3d",i);
	printf("\n ");
	for(i=0;i<=M+1;i++)
		printf("%3d",0);
	printf("\n");
	for(i=1;i<=N;i++)
	{
		printf("%c%3d",A[i],i);
		for(j=0;j<=M;j++)
			printf("%3d",L[i][j]);
		printf("\n");
	}
}
void main ()
{
	char A[N+1]={'0','x','y','x','x','z','x','y','z','x','y'};
	char B[M+1]={'0','z','x','z','y','y','z','x','x','y','x','x','z'};
	int L[N+1][M+1];
	long start,end;
	LCS(A,B,L,N,M);
	table(A,B,L);
	printf("\nLCS              : %d\n",L[N][M]);
	printf("\nLCS_recursion    : %d\n\n\n",LCS_recursion(A,B,N,M));
	system("pause");
}

测试结果