资源描述:
《最长公共子序列课程设计文档及源码》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、最长公共子序列◊课程设计项目:说明:若给定序歹!JX二{Xi,X2,・・・,Xm},则另一序列Z={zi,z2,...,zk},是X的子序列是指存在一个严格递增下标序列使得对于所有戸1,2,…,k有:zj=xijo例如,序列Z={B,C,D,B}是序列X二{A,B,C,B,D,A,B}的子序列,相应的递增下标序列为{2,3,5,7)o给定2个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列。设计要求:请使用C语言编程,设计一个有效的算法解决下述问题:给定2个序列X={xi,x2,...,xm}和Y={yi
2、,y2,...,yn},找出X和Y的最长公共子序列。设计提示:{z={z设序列X={xi,X2,...,Xm}和Y={yi,y2,...,yn}的最长公共子序列为,Z2,・・.,Zk},则若若若17—/lz123z(z(z(Xm=yn,则Zk=Xni=yn,且Zk_
3、是Xm-l和yn-l的最长公共子序列。XmHyn且ZkHXm,则Z是Xm.
4、和Y的最长公共子序列。XmHyn且ZkHy”则Z是X和yn-i的最长公共子序列。由此可见,2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。由最长公共子序列问题的最优子结构性质
5、建立子问题最优值的递归关系。用c[i][j]记录序列和的最长公共子序列的长度。其中,Xi={xi,x2,...,xi};Yj={y],y2,...,yj}o当i=0或j=0时,空序列是xi和比的最长公共子序列。故此时C[i][j]=Oo其他情况下,由最优子结构性质可建立递归关系如下:0/=0,7=0c[i][j]=c[i—1][/—1]+1i,j>0;兀=兀max{(?[/][j-1],c[i-1][j]}z,j>0;x,.丰y.◊课程设计目的:用c语言编程列出解决的方法,复习c语言的用法,提高动手实践能力◊课程设计内容♦需求分析:1.本演
6、示程序中,输入的x序列和y序列是任意的,当然是在不超过MAXSIZE的前提下进行的;1.演示程序以用户和计算机的对话方式执行,即在计算机的终端上显示“提示信息”Z后,由用户在键盘上输入相应数据(即X序列和Y序列)2.测试数据(1)x序列:ADJdjfk48*&*d(j*&hj6GHh%$y序列:AhdhGHGF67HGHGA%&HGF%$输出:Adh6GH%$(1)x序列:SDJFKJdkjfjA&*UJGHJ&A$y序列:SHJhjhdA&657HGFT$输岀:SJdA&GHA$(2)其余省略♦概要设计1.voidlcs_length(c
7、har*x,char*y,intc[][MAXSIZE])c[i,j]记录序列Xi和Yj的最长公共子序列的长度根据下面条件,构造类似图lcsjength的表0i=0J=0c[i][j]=^c[/-l][j-l]+lmax{c[/][j-1],c[i-1][j]}j0123456012345670QQ0QQQQT0T0T011Q1—1?12—20T1T12—2T2T201T1t2?23—30T12T2t3T30T13T340LT2tT34?4BAABCBDAB图LcsjengthCA2.intles(intc[][MAX
8、SIZE],char*x,char*y,intlen_x,intlen_y,char*lcs^arr)♦详细设计1.元素类型:C[i][j]记录Xi和Yj序列的最长公共子序列长度Lcs_arr数组存储最长公共子序列的元素2.每个模块的分析(1)主程序模块:intmain(void){inti,c;charx[MAXSIZE],y[MAXSIZE];wh订cd){printf(〃'y‘tocontinue,andyoucaninputlistofxandy;'rftostop:“);c=getchar();if(c二二’n'){printf(
9、z,Areyousuretoquit,'y‘toquit,tocontinue:“);getchar();c=getchar();if(cH'y'){exit(1);}elseif(c=='n'){getchar();printf(Z,Pleaseinputthearrayofx(like:ABCDEF):“);if(fgets(x,sizeof(x),stdin)=NULL)exit(1);printf(z,Pleaseinputthearrayofy(like:ABCDEF):“);if(fgets(y,sizeof(y),stdin)
10、=NULL)exit(1);intlen_x=strlen(x);intlen_y=strlen(y);intc[MAXSIZE][MAXSIZE];lcs_length(x,y