欢迎来到天天文库
浏览记录
ID:38076825
大小:45.50 KB
页数:6页
时间:2019-05-26
《最长公共子序列论文2》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、最长公共子序列13计科行知班张宗雷2013一、问题描述一个序列的子序列:该序列删除若干子序列后得到的序列。最长公共子序列:给定两个子序列X和Y当另一个序列Z既是X的子序列又是Y的子序列则称Z是X和Y的公共子序列。当Z是最长的一个公共子序列时Z称为X和Y的最长公共子序列。二、问题分析及推导过程1.申明两个数组,用于保存比较的两个字符串;由于事先不知字符串大小,故动态的实现,这里用C++的容器。2.申明全局变量,二维数组B和数组C。数组C用于保存计算Xi和Yi的LCS值;数组B保存当前的C是从哪个子问题得来的。
2、为此,定义一个枚举类型,用于标识不同的方向,分别为对角线、向上、向左和向左向上四个方向。3.根据动态规划,实现一个函数LCS_LENGTH,完成的功能是计算数组B和C。具体过程是:先是动态申请二维数组B和C,他们的行列长度都增加1,目的就是方便计算。将C的第0行和第0列都赋上0,即初始化。开始计算C[i][j],以行为主,一次计算C的每一个元素,即将两个数组逐一比较。比较时就有两种情况,分别是若相等时,就将C[i][j]设置成C[i-1][j-1],同时将B[i][j]设置成DIAGONAL。若不相等时,比
3、较C[i-1][j]和C[i][j-1]的值,又有三种情况:一是C[i-1][j]与C[i][j-1]相等,就随便把某一个赋给C[i][j],比如C[i-1][j],B[i][j]设置为UP_LEFT;二是若C[i-1][j]大于C[i][j-1],则将C[i-1][j]赋给C[i][j],并且将B[i][j]设置成UP;最后是若C[i-1][j]小于C[i][j-1],则将C[i][j-1]赋给C[i][j],并且将B[i][j]设置成LEFT。4.根据第3)步骤的结果,就可以找出所有LCS了。这里会用到
4、回溯方法,具体实现可以用栈,也可以用递归。本人使用的是递归,代码简单、易懂。具体实现方法是:申请一个数组用于保存一个LCS,这个数组会反复使用,因此,一旦找到一个就会立即将它输出。再设置一个变量curpos标识当前的数组下标,一个变量len保存当前LCS数组的元素个数。扫描二维数组B,从最后一个开始,判断B的值,有四种情况:当B的值是UP时,就向上递归;当B的值是LEFT时,就向左递归;当B的值是向上或是向左时,这是存在两个选择,先左后上,或是先上后左;当B的值是对角线的时,此时LCS数组才保存当前的字符,
5、len加1,继续沿对角线递归,递归完之后,len减1,回溯。若len为LCS的长度时,就输出。三、计算求解过程及算法实现#include#include#include#include#includeusingnamespacestd;int**C,**B;//C保存计算Xi和Yi的LCS值;B保存当前的C是从哪个子问题得来的char*LCS;//保存一个最长公共子序列intlen=0;//回溯时用到的统计保存LCS
6、数组当前长度enum{DIAGONAL,UP,LEFT,UP_LEFT};//定义方向,分别是:对角线、向上、向左和向左向上/*LCS_LENGTH函数,求出数组C和B*/voidLCS_LENGTH(vectorX,vectorY,intm,intn)//计算C{C=newint*[m];//动态分配二维数组B=newint*[m];for(inti=0;i7、列C[i][0]=0;for(intj=0;j8、}elseif(C[i-1][j]>C[i][j-1])//up{C[i][j]=C[i-1][j];B[i][j]=UP;}else//left{C[i][j]=C[i][j-1];B[i][j]=LEFT;}}}}}/*Print_LCS函数,打印出所有的LCS*/voidPrint_LCS(int**B,vectorX,inti,intj,intcurpos,intmaxLCS,ostream&
7、列C[i][0]=0;for(intj=0;j8、}elseif(C[i-1][j]>C[i][j-1])//up{C[i][j]=C[i-1][j];B[i][j]=UP;}else//left{C[i][j]=C[i][j-1];B[i][j]=LEFT;}}}}}/*Print_LCS函数,打印出所有的LCS*/voidPrint_LCS(int**B,vectorX,inti,intj,intcurpos,intmaxLCS,ostream&
8、}elseif(C[i-1][j]>C[i][j-1])//up{C[i][j]=C[i-1][j];B[i][j]=UP;}else//left{C[i][j]=C[i][j-1];B[i][j]=LEFT;}}}}}/*Print_LCS函数,打印出所有的LCS*/voidPrint_LCS(int**B,vectorX,inti,intj,intcurpos,intmaxLCS,ostream&
此文档下载收益归作者所有