最长公共子序列问题(共21页).doc

精选优质文档-倾情为你奉上目 录1 前言若给定序列X=x1,x2,xm，则另一序列Z=z1,z2,zk，是X的子序列是指存在一个严格递增下标序列i1,i2,ik使得对于所有j=1,2,k有：zj=xij。例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相应的递增下标序列为2，3，5，7。给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。请使用C语言编程，设计一个有效的算法解决下述问题：给定2个序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最长公共子序列。2 需求分析2.1 任务和要求使用C语言编程，设计一个有效的算法解决下述问题：给定2个序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最长公共子序列。2.2 运行环境（1）WINDOWS2000/XP系统（2）Visual C+ 6.0编译环境或TC编译环境2.3 开发工具C语言3 分析和设计3.1 系统分析及设计思路设序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列为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的最长公共子序列。由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用cij记录序列和的最长公共子序列的长度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时Cij=0。程序的设计思路是：调用函数void Initialize（），输入两个字符串，对两个串的存储数组b，c进行动态分配。调用函数void LCSLength（int m,int n,string x,string y,int*c,int*b），将长度较小的字符串作为第一参数，将长度较大的字符串作为第二个参数。调用函数void LCS（inti，int j,string x,int*b）构造最长公共子序列调用函数。调用函数ReadCommand进行系统操作屏幕指示，然后利用函数void Interpret（char&cmd）对函数进行总体操作，最后得出最长公共子序列。3.2 主要数据结构及算法动态申请两个字符串的存储空间:using namespace std;string x,y系统操作屏幕指示: ReadCommand(cmd)字符串比较函数:void LCSLength（int m,int n,string x,string y,int*c,int*b）构造最长公共子序列调用函数:void LCS（inti，int j,string x,int*b）动态申请两个字符串的存储空间:using namespace std;string x,y3.3 函数流程图Realese()/释放指针boarci=newtn+1;bi=new intn+1;int i=0;i<=m;i+m=x.length();n=y.length();c=new int*m+1;b=new intm+1;开始 using namespace stdstringx,y;int*c,*b,m,n;char cmd;ReadCommand(cmd);Interpret(cmd);cmd!=q&&cmd!=Q N Yreturn 0ReadCommand(char&cmd) cout<<“nnt请选择操作： ”；cin>>cmd;cout<<cmd!=c&&cmd!C&&cmd!=q&&cmd!=Q); N Y Initialize（）m=x.length();n=y.length();c=new int*m+1;b=new intm+1; int i=0;i<=m;i+ N Y Realese()/释放指针boardci=newtn+1;bi=new intn+1;delete ci;delete bi;deletec;deleteb;interpret(char&cmd)switch(cmd)casec:caseC;Initialize();LCSLength(m,n,x,y,c,b);Display();Realese();break;LCSLength(int m,int n,string x,string y,int*c,int*bint i=0；i<=m;i+ N Yxi-1=yj-1cij=ci-1j-1+1;bij=1;ci-1j>=ij-1cij=ci-1j;bij=2;(i=0;i<=m;i+)ci0=0;(i=1;i<=n;i+)c0i=0;i=1;i<=m;i+;j=1;j<=n;j+; N Y N Y N YLCS(int i,int j,string x,int *b)i=0|j=0cij=cij-1;bij=3return bij=1 N Y N Ybij=2LCS(i-1,j,x,b)LCS(I,j-1,x,b)Dispiay()结束LCS(i-1,j-1,x,b);count<<xi-1;图3.1 程序总体流程图流程图4 具体代码实现#include<iostream>#include<string>using namespace std;string x,y;/x,y用来存放字符序列int *c,*b,m,n;/*m，n分别存储字符串x,y的长度,数组cij存储Xi和Yj得最长公共子序列的长度，bij记录cij的值是有哪一个子问题的解得到的*/void LCSLength(int m,int n,string x,string y,int *c,int*b);void LCS(int i,int j,string x,int *b);void Initialize();/对数组b,c动态分配空间以及对其进行初始化void ReadCommand(char &cmd);void Interpret(char &cmd);void Realese();/释放指针void Display();int main()char cmd;doReadCommand(cmd);Interpret(cmd);while(cmd!='q'&&cmd!='Q');return 0;void ReadCommand(char &cmd)system("cls"); /清屏cout<<"n-n"cout<<"ntttt操 作 提 示"cout<<"n-n"cout<<"tquit-q/Q tt continue-c/Cn"docout<<"nnt请选择操作："cin>>cmd;cout<<"n-n"while(cmd!='c'&&cmd!='C'&&cmd!='q'&&cmd!='Q');void Initialize()cout<<"分别输入两个字符串（每个字符串以回车结束）n"cin>>x;cin>>y;m=x.length();n=y.length();c=new int*m+1;b=new int*m+1;for(int i=0;i<=m;i+)ci=new intn+1;bi=new intn+1; void Realese()/释放指针boardfor(int i=0;i<=m;i+)delete ci;delete bi;delete c;delete b;void Interpret(char &cmd)switch(cmd)case 'c':case 'C': Initialize();LCSLength(m,n,x,y,c,b); Display();Realese();break;void LCSLength(int m,int n,string x,string y,int *c,int*b)int i,j;for(i=0;i<=m;i+)ci0=0;for(i=1;i<=n;i+)c0i=0;for(i=1;i<=m;i+)for(j=1;j<=n;j+)if(xi-1=yj-1)cij=ci-1j-1+1;bij=1;else if(ci-1j>=cij-1)cij=ci-1j;bij=2;elsecij=cij-1;bij=3; /构造最长公共子序列void LCS(int i,int j,string x,int *b)if(i=0|j=0)return;if(bij=1)LCS(i-1,j-1,x,b);cout<<xi-1;else if(bij=2)LCS(i-1,j,x,b);else LCS(i,j-1,x,b);void Display()LCS(m,n,x,b);cout<<"n请按回车键继续！n"cin.get();cin.get();5 课程设计总结5.1 程序运行结果或预期运行结果5.2 设计结论回顾起此课程设计，至今我仍感慨颇多，从理论到实践，在这段日子里，可以说得是苦多于甜，但是可以学到很多很多的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，才能提高自己的实际动手能力和独立思考的能力。实验过程中，使我更加扎实的掌握了有关数据结构方面的知识，在设计过程中虽然遇到了一些问题，但经过一次又一次的思考，一遍又一遍的检查终于找出了原因所在，也暴露出了前期我在这方面的知识欠缺和经验不足。实践出真知，通过亲自动手制作，使我们掌握的知识不再是纸上谈兵。过而能改，善莫大焉。在课程设计过程中，我不断发现错误，不断改正，不断领悟，不断获取。最终的调试运行环节，本身就是在践行“过而能改，善莫大焉”的知行观。这次课程设计终于顺利完成了，在设计中遇到了很多问题，最后在老师的指导下，终于迎刃而解。在今后社会的发展和学习实践过程中，一定要不懈努力，不能遇到问题就想到要退缩，一定要不厌其烦的发现问题所在，然后一一进行解决，只有这样，才能成功的做成想做的事，才能在今后的道路上劈荆斩棘，而不是知难而退，那样永远不可能收获成功，收获喜悦，也永远不可能得到社会及他人对你的认可！此次设计也让我明白了思路即出路，有什么不懂不明白的地方要及时请教或上网查询，只要认真钻研，动脑思考，动手实践，就没有弄不懂的知识，收获颇丰。参考文献1张福祥. C语言程序设计M. 辽宁大学出版社，2008.12 张福祥，王萌C语言程序设计习题解答与实验实训M沈阳：辽宁大学出版社，20083 牛莉，刘远军等计算机等级考试辅导教程M北京：中国铁道出版社，2008致 谢本课题在选题及进行过程中得到李仲生老师的悉心指导。论文行文过程中，李老师多次帮助我分析思路，开拓视角，在我遇到困难想放弃的时候给予我最大的支持和鼓励。李老师严谨求实的治学态度，踏实坚韧的工作精神，将使我终生受益。再多华丽的言语也显苍白。在此，谨向李老师致以诚挚的谢意和崇高的敬意。课程设计(论文)题 目 名 称 最长公共子序列（动态规划法） 课 程 名 称 数据结构课程设计 学 生 姓 名 张强 学 号 系 、专 业 信息工程系、通信工程 指 导 教 师 李仲生 2011年 12 月 25 日邵阳学院课程设计（论文）评阅表学生姓名 张强 学 号 系 信息工程系 专业班级 通信工程一班 题目名称 最长公共子序列（动态规划法） 课程名称 数据结构 一、学生自我总结通过这次课程设计，综合运用本专业所学课程的理论和实际知识进行一次最长公共子序列设计训练从而培养和提高我独立工作能力，巩固与扩充了数据结构等课程所学的内容，基本掌握用动态规划法求公共子序列设计的方法，同时各科相关的课程都有了全面的复习，独立思考的能力也有了提高。在设计过程中虽然遇到了一些问题，但经过一次又一次的思考，一遍又一遍的检查终于找出了原因所在，也暴露出了前期我在这方面的知识欠缺和经验不足。此次设计也让我明白了思路即出路，有什么不懂不明白的地方要及时请教或上网查询，只要认真钻研，动脑思考，动手实践，就没有弄不懂的知识，收获颇丰。 学生签名： 张强 2011 年 12月 7日二、指导教师评定评分项目资料查阅编写规范基本技能设计能力科学素养工作量综合成绩权 重101525301010单项成绩指导教师评语： 指导教师（签名）： 年 月 日注：1、本表是学生课程设计（论文）成绩评定的依据，装订在设计说明书（或论文）的“任务书”页后面；2、表中的“评分项目”及“权重”根据各系的考核细则和评分标准确定。邵阳学院课程设计（论文）任务书年级专业10级通信工程学生姓名张强学 号题目名称最长公共子序列（动态规划法）设计时间1718周课程名称数据结构课程设计课程编号设计地点新实验楼四楼机房一、 课程设计（论文）目的学生在教师指导下运用数据结构课程的知识来研究、解决一些具有一定综合性的专业课题。通过课程设计，巩固课程所学的知识，提高学生综合运用所学知识分析、解决实际问题、查阅文献资料、及进行技术设计的初步能力。二、 已知技术参数和条件（1）WINDOWS2000/XP系统（2）Visual C+ 6.0编译环境或TC编译环境三、 任务和要求使用C语言编程，设计一个有效的算法解决下述问题：给定2个序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最长公共子序列。注：1此表由指导教师填写，经系、教研室审批，指导教师、学生签字后生效；2此表1式3份，学生、指导教师、教研室各1份。四、参考资料和现有基础条件（包括实验室、主要仪器设备等）参考资料：教材及实验指导书基础条件：计算机一台，安装Visual C+或TC五、进度安排2011.12.5前：指导教师拟定课程设计课题2011.12.62011.12.9：学生选题，指导教师下发任务书，学生搜集相关参考资料2011.12.102011.12.18：学生按课题小组编程2011.12.192011.12.25：学生独立撰写课程设计报告2011.12.262011.12.31：指导教师批阅课程设计报告，评定学生成绩六、教研室审批意见教研室主任（签字）： 年 月 日七|、主管教学主任意见 主管主任（签字）： 年 月 日八、备注指导教师（签字）： 学生（签字）： 专心-专注-专业