最长公共子序列问题

内容前言12需求分析12.1任务和要求12.2操作环境12.3开发工具13分析和设计13.1系统分析和设计思维13.2主要数据结构和算法23.3功能流程图24特定代码实施35课程设计总结135.1程序运行结果或预期运行结果135.2设计结论13参考文献14谢谢你141前言如果给定序列x=x1，x2，XM，另一个序列z=Z1，z2，是x的子序列，意味着存在严格递增的下标序列i1，I2，因此对于所有j=1，2，k has: zj=xij。例如，序列Z=B，c，d，B是序列X=A，B，c，B，d，A，B的子序列，对应的下标序列是2，3，5，7。给定两个序列x和y，当另一个序列z既是x的子序列又是y的子序列时，z被称为序列x和y的公共子序列。请使用C语言编程设计一个有效的算法来解决以下问题：给定两个序列x=x1，x2，xm和y=y1，y2，yn找到x和y的最长公共子序列。2需求分析2.1任务和要求利用C语言编程，设计了一个有效的算法来解决以下问题：给定两个序列x=x1，x2，xm和y=y1，y2，yn找到x和y的最长公共子序列。2.2操作环境(1)WINDOWS2000/XP系统(2)可视化C 6.0编译环境或TC编译环境2.3开发工具c 语言3分析和设计3.1系统分析和设计思想让序列的最长公共子序列x=x1，x2，xm和y=y1，y2，yn be z=Z1，z2，那么，zk(1)如果xm=yn，则zk=xm=yn，并且zk-1是xm-1和yn-1的最长公共子序列。(2)如果xmyn和zkxm，则Z是xm-1和y的最长公共子序列(3)如果xmyn和zkyn，则Z是X和yn-1的最长公共子序列。因此，两个序列中最长的公共子序列包含两个序列前缀中最长的公共子序列。利用最长公共子序列问题的最优子结构性质，建立子问题最优值的递推关系。用cij记录序列和的最长公共子序列的长度。其中Xi=x1，x2，Xi ；Yj=y1，y2，yj .当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。因此，此时ij=0。该程序的设计思想是调用函数void Initialize()，输入两个字符串，并动态分配这两个字符串的存储数组b、c。调用函数void lcslength (intm，intn，stringx，stringy，int * * c，int * * b)，将长度较小的字符串作为第一个参数，将长度较大的字符串作为第二个参数。调用函数void LCS(inti，int j，string x，int*b)构造了一个最长的公共子序列调用函数。调用函数ReadCommand来指示系统操作屏幕，然后使用函数void解释器(charcmd)来执行函数的整体操作，最后获得最长的公共子序列。3.2主要数据结构和算法使用命名空间标准为两个字符串动态申请存储空间：字符串x，y系统操作屏幕显示：读取命令(cmd)字符串比较函数： void lcslength (intm，intn，stringx，stringyy，int * * c，int * * b)构造最长公共子序列调用函数：void LCS(inti，int j，string x，int*b)使用命名空间标准为两个字符串动态申请存储空间：字符串x，y3.3功能流程图实()/释放指针野猪c1=纽特1；b1=新国际1；int I=0；I=m；im=x . length()；n=y . length()；c=新国际*m1；b=新国际m1；开始使用命名空间标准stringx，y；int*c，*b，m，n；char cmdReadCommand(cmd)。口译(cmd)。cmd！=qcmd！=Q NY返回0ReadCommand(charcmd)Cout n n 请选择操作：；cincmd标准输出cmd！=ccmd！Ccmd！=qcmd！=Q)；NY初始化()m=x . length()；n=y . length()；c=新国际*m1；b=新国际m1；int I=0；I=m；iNYRealese()/释放指针板c1=纽特1；b1=新国际1；删除一号；删除一号；删除c；删除b；解释器(charcmd)开关(cmd)case c :caseC初始化()；LCSLength(m，n，x，y，c，b)；显示()；real ese()；休息；LCSLength(int m，int n，string x，string y，int*c，int*b整数1=0；I=m。iNYxi-1=yj-111=111；j=1；ci-1j=ij-111=11；j=2；(1=0；I=m。0=0；(I=1；i=n .01=0；I=1；I=m。我；j=1；j=n .j；NYNYNYLCS(int i，int j，string x，int *b)i=0|j=011=11；bij=3返回bij=1NYNYbij=2LCS(i-1，j，x，b)LCS(一、j-1、x、b)显示()结束LCS(i-1、j-1、x、b)；数数#包括使用命名空间标准；字符串x，y；/x，y用来存放字符序列int *c，*b，m，n；/*m，n分别存储字符串x，y的长度，数组存储xi和Yj得最长公共子序列的长度，记录的值是有哪一个子问题的解得到的*/void LCSLength(int m，int n，string x，string y，int *c，int * * b)；void LCS(int i，int j，string x，int * * b)；空的初始化()；/对数组b，c动态分配空间以及对其进行初始化void ReadCommand(char cmd)；无效解释器(char cmd)；void Realese()；/释放指针无效显示()；int main()char cmd做读取命令(cmd).口译(cmd).同时(cmd！=qcmd！=Q)；返回0；void ReadCommand(char cmd)系统(“cls”)；/清屏cout n- n ；coutntttt操作提示；cout n- n ；退出-继续- C/C n ；做coutnnt请选择操作；cincmdcout n- n ；同时(cmd！=ccmd！=Ccmd！=qcmd！=Q)；无效初始化()cout 分别输入两个字符串（每个字符串以回车结束) n ；cinx辛尼m=x长度()；n=y . length()；c=新国际*m1；b=新国际*m1；对于(整数1=0；I=m。c1=新国际1；b1=新国际1；void Realese()/释放指针板对于(整数1=0；I=m。删除一号；删除一号；删除c；删除b；无效解释器(char cmd)开关(cmd)案例c:案例C:初始化()；LCSLength(m，n，x，y，c，b)；显示()；real ese()；休息；void LCSLength(int m，int n，string x，string y，int *c，int*b)int i，j；对于