1前言。
设计一个算法求出两个序列的所有lcs，分析最坏情况，用“会计方法”证明利用b[i][j]求出所有lcs的算法在最坏情况下的需求分析根据最长公共子序列问题的性质，即经过分解后的子问题具有高度重复性，并且具有最优子结构性质，采用动态规划法求解问题。根据以上辅助数组c和b的定义，算法首先需要求出这两个数组，c[m][n]中记录的最长公共子序列的长度，b中记录了查找子序列元素的搜索方向。对于某些情况会输出重复的lcs，这是因为算法在沿不同路径搜索时可能会出现相同的lcs序列。
利用c和b的信息以及find_all_lcs可以采用回溯法求出所有的lcs。由上述对find_all_lcs算法的分析可知，求出所有的lcs实际上是根据搜索的方向信息遍历所有的路径找出满足条件的元素集合。因此可以得出结论。
2.1课程设计目的。
运用所学课程的知识来研究、解决一些具有一定综合性问题的专业课题。通过课程设计（**），提高学生综合运用所学知识来解决实际问题、使用文献资料、及进行科学实验或技术设计的初步能力，为毕业设计（**）打基础。对于本课程设计而言，重点在熟悉c语言基本语法规范以及灵活运用c语言编程解决实际问题。
2.2课程设计任务。
1．初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2．完成最低要求：完成第一个功能；3．进一步要求：进一步完成后续功能。
有兴趣的同学可以自己扩充系统功能。要求：
1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案。
5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。
2.3设计环境。
1）windows2000/2003/xp/7/vista系统（2）visualc++或tc集成开发环境。
2.4开发语言。
c语言。3分析和设计。
3.1模块设计。
根据最长公共子序列问题的性质，即经过分解后的子问题具有高度重复性，并且具有最优子结构性质，采用动态规划法求解问题。设x=,y=,为了构造出lcs，还需要使用一个二维数组b[m][n]，b[i][j]记录c[i][j]是通过哪个子问题的值求得的，以决定搜索的方向，欲求出所有的lcs，定义数组b如下：
设1-对角线方向；2-向上；3-向左；4-向上或向左若x[i]=y[j],b[i][j]=1,若c[i-1][j][i][j-1],则b[i][j]=3,若c[i-1][j]=[i][j-1],则b[i][j]=4,根据以上辅助数组c和b的定义，算法首先需要求出这两个数组，c[m][n]中记录的最长公共子序列的长度，b中记录了查找子序列元素的搜索方向。
利用c和b的信息，find_all_lcs可以采用回溯法求出所有的lcs。基本思路如下：使用一个辅助数组记录每次调用find_all_lcs得到的lcs中的元素，每次递归调用一次find_all_lcs，进入一个新的执行层，首先要判断当前处理的两个子序列长度是否大于等于0，若不满足，则该层的递归结束，返回上一层；然后再判断当前得到的子序列是否等于数组c中求出的最长公共子序列长度，若等于，则说明算法执行到此已经得到一个lcs，按序输出；若不等于，此。
时根据数组b中记录的搜索方向继续搜索，特别要说明的是，当b[i][j]=4时，即要向上或向左，需要对这两个方向分别调用find_all_lcs，保证沿着这两个方向上lcs元素不被漏掉，都可以搜索到；若b[i][j]=1，即沿对角线方向搜索前进时，此时元素x[i]为lcs中的元素，存放至辅助数组中去，同时将当前已经求得的lcs长度增1，当递归调用find_all_lcs从b[i][j]=1处时，需要回溯一步，搜索其它路径上可能为lcs中的元素。当所有的可能路径都已经搜索完，算法结束。
对于某些情况会输出重复的lcs，这是因为算法在沿不同路径搜索时可能会出现相同的lcs序列。
2.时间复杂度分析。
由上述对find_all_lcs算法的分析可知，求出所有的lcs实际上是根据搜索的方向信息遍历所有的路径找出满足条件的元素集合。因此，除求解辅助数组c和b所用的o(mn+m+n)的执行时间外，find_all_lcs的时间复杂度取决于所遍历路径数。而路径数是由搜索方向决定的。
显然算法在最好的情况下，即m=n并且b中所有的值都指示沿着对角线方向搜索，时间复杂度为o(n).相反，当x和y序列不存在公共子序列时为算法的最坏情况，此时c中所有值都等于0，数组b中所有的值都指示要分别沿两个不同的方向（向左或向上）搜索，这种情况下每处理一次x[i],y[j]时总是要沿两个方向分别调用find_all_lcs，遇到i=0或j=0时返回，直到搜索完所有的可能路径才结束。
3.2系统流程图。
开始。intm=strlen(x)-1
inti=0iyn
i++intj=1jny
j++i=1y
i<=m
nx[i]==y[j]x[i]==y[j]yn
c[i-1][j]>c[i][j]}yn
c[i-1][j[i][j-1]}
yc[i][j]=c[i-1][j-1]+1
c[i][j]=c[i-1][j]c[i][j]=c[i][j-1]
i++c[i][j]=c[i-1][j]结束。
4具体**实现。
#include#include<>#definemaxsize100usingnamespacestd;
intc[maxsize][maxsize];/记录序列x和y的lcs的长度。
intb[maxsize][maxsize];/记录二维数组c是通过哪一个子问题的值求。
得的，以决定搜索的方向：1-对角线方向；2-向上；3-向左；4-向上或向左。
charlcs[maxsize];intlen=0;
*函数名：lcs_len
功能：自底向上进行递推计算c[i][j],并确定b中的搜索方向。
若i=0或j=0则c[i][j]=0;
若i,j>0且x[i]=y[j]则c[i][j]=c[i-1][j-1]+1;若i,j>0且x[i]!=y[j]则c[i][j]=max
elseif(c[i-1][j]c[i][j]=c[i][j-1];b[i][j]=3;}
else/*c[i-1][j]==c[i][j-1]*/
函数名：fine_all_lcs功能：回溯法递归输出所有的lcs参数说明：
direction:记录搜索方向的二维数组，1-对角线方向；2-向上；3-向左；4-向上或。
向左。x:一个序列。
i,j:待搜索的下标，初始值为两个序列的长度len:记录当前lcs的长度lcslen:lcs的长度。
lcs:记录当前得到的lcs字符*/
voidfind_all_lcs(intdirection[maxsize][maxsize],char*x,inti,intj,intcurlen,intlcslen)
/回溯。elseif(direction[i][j]==2)
elseif(direction[i][j]==3)
find_all_lcs(direction,x,i,j-1,curlen,lcslen);}
else//递归调用find_all_lcs分别沿两个不同的方向搜索}}}
intmain()
5课程设计总结。
5.1程序运行结果。
5.2课程设计体会。
本次程序满足了lcs问题程序设计的基本要求，它最大的特色在于运行起来十分简便，避免了有些程序的繁琐，让人一目了然，就算是初学者也知道它的运行方法以及它的作用；它的不足在于该程序所选择的过程太过于繁琐，有些地。
方只能只能找规定的选择，未能给运行者主动权。程序整体让人看了有种吃不透的感觉，但还好有许多的注释帮助我们理解该程序。c语言的要求是言简意赅，精益求精，把最精华的部分呈现给读者，让读者能够一目了然。
当然其前提条件是该程序能够正确运行，由于能力有限，知识面还不够完善，所以该程序还存在着某些漏洞，以及需要改进的地方，在接下来的学习里我相信我一定能够学习到更好的方法来解决lcs问题。通过这些天的课程设计，使我对《c语言》这门课程有了更深刻的了解。它毕竟是我们计算机科学与技术专业的基础课程。
所以我们一定会认真贯彻，落实这种程序设计思想。当然，如果要要学好这门课程，那就需要知识+实践双结合。只有知识，没有实践，那就是纸上谈兵。
如果没有知识的理论指导，光实践的结果也会是一事无成。此次课程设计充分反应了这个道理。因此我十分感谢学校给与我这个参加程序设计的机会，我相信在以后的时光里这个机会能给我带来丰富的经验。
参考文献。1）、黄同成，周红波。程序设计基础教程（c语言）［m］.
湖南人民出版社，2011（2)、黄同成，黄磊。程序设计实践教程(c语言)［m］.湖南人民出版社，2011（3)、谭浩强。
c程序设计（第三版）［m］.北京：清华大学出版社，2005（4)、李志求。
实用c语言程序设计教程［m］.北京：电子工业出版社，1999（5)、顾元刚。
数据结构简明教程［m］.南京：东南大学出版社，2003
致谢。我能够顺利完成这次课程设计必须感谢李仲生老师，是他带领着我们如何进行程序设计。以及感谢我们班c语言课程教师成娅辉老师。
如果没有这两位老师的帮助，我们就不能即快又好地完成本次的程序设计。最后还要感谢我们班的同学们，他们乐于助人，帮助我启发设计该程序的思想。感谢大家！
c语言课程设计报告 课程设计报告
周口师范学院。课程设计报告。院 系 计算机科学与技术学院 班级。学生姓名学号。设计题目 职工工资管理系统。完成日期 年月日 课程设计任务书。设计题目 工资管理系统 教研室主任指导教师 年月日。摘要11设计内容 任务及具体要求2 1.1设计内容2 1.2设计任务及具体要求2 2概要设计3 2.1该系统...
C语言课程设计报告
华中科技大学计算机科学与技术学院。题目 专业 班级 学号 姓名 成绩 指导教师 完成日期 2016年月日。目录。一 系统需求分析 1 二 总体设计 2 三 数据结构设计 3 四 详细设计 4 五 系统实现 5 六 运行测试与结果分析 6 七 总结 7 八 参考文献 8 九 指导教师评语 9 对所要解...
C语言课程设计报告
c语言。课程设计。商业销售管理系统。学号 121407210 姓名 宋军。班级 软件1202 指导老师 邹姝稚。成绩 2013年6月。一 任务描述。编写一个商品销售管理系统，是其能够拥有商品买卖和库存管理功能。在顾客选购时，需给出输入商品名称，或商品型号，或选择列表进而输入商品编号三种选择，在顾客选...