voip
风的方向
厚德致远,博学敦行!
posts - 52,comments - 21,trackbacks - 0
       问题描述:给定序列X={x1,x2,..xn}和Y={y1,y2...ym},求一个Z={z1,z2,..zk}序列是X,Y的最长公共子序列!!

      书上描述的已经十分详细了,而且容易理解。通过定义c[i][j]用于记录Xi和Yi的最长公共子序列的长度,从而递推得到结果。

递推方程如下:
                 c[i][j]=0,i=0,j=0;    c[i][j]=c[i-1][j-1]+1,xi=yj;     c[i][j]=max(c[i-1][j],c[i][j-1]),xi!=yj; (不知道怎么输出大括号,悲剧啊!)

代码如下:
#include<stdio.h>
void LCSLength(int m,int n,char *x,char *y,int c[][100],int b[][100])
{
    
int i,j;
    
for(i=1;i<=m;i++) c[i][0]=0;                        //当i==0或者j==0时,代表其中一个序列为空,c[i][j]当然为0
    for(j=1;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][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;
                }

            }

        }

}


void LCS(int i,int j,char x[],int b[][100])    //递归求得最长子序列
{
    
if(i==0||b==0)
        
return;
    
if(b[i][j]==1)
    
{
        LCS(i
-1,j-1,x,b);
        printf(
"%c",x[i]);
    }

    
else if(b[i][j]==2)
        LCS(i
-1,j,x,b);
    
else 
        LCS(i,j
-1,x,b);
}


int main()
{
    
char x[100],y[100];
    
int i,j;
    
int c[100][100],b[100][100];
    scanf(
"%s %s",x+1,y+1);
    c[
0][0]=0;
    LCSLength(
7,6,x,y,c,b);
    
for(i=0;i<8;i++)
    
{
        
for(j=0;j<7;j++)
        
{
            printf(
"%d ",c[i][j]);
        }

        printf(
"\n");
    }

    LCS(
7,6,x,b);
    printf(
"\n");
    
return 0;
}
运行结果:


posted on 2010-09-04 23:17 jince 阅读(310) 评论(0)  编辑 收藏 引用 所属分类: 算法设计与分析

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


哈哈哈哈哈哈