最长公共子序列问题

《最长公共子序列问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、一、最长公共子序列问题1）程序代码：#includevoidlength(intm,intn,char*x,char*y,intc[][20],intb[][20]);voidlcs(inti,intj,char*x,intb[][20]);voidmain(){charx[20],y[20];intc[20][20],b[20][20];intm=1,n=1;printf("******************");printf("求最长公共子序列问题");printf("******************");printf("请输入X序列：");//

2、输入x序列while(1){scanf("%c",&x[m]);if(x[m]!='')m++;elsebreak;}m--=1;printf("请输入Y序列：");//输入y序列while(1){scanf("%c",&y[n]);if(y[n]!='')n++;elsebreak;}n--=1;length(m,n,x,y,c,b);printf("x和y的最长公共子序列为：");lcs(m,n,x,b);printf("其长度为：%d",c[m][n]);}voidlength(intm,intn,char*x,char*y,intc[][20],intb[][20]

3、){inti,j;for(i=0;i<=m;i++)c[i][0]=0;//令矩阵c第一列全为0for(i=1;i<=n;i++)c[0][i]=0;//令矩阵c第一行全为0for(i=1;i<=m;i++)for(j=1;j<=n;j++){if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}5//当x与y序列最后一值相等时，其公共子序列是n-1序列的公共子序列加最后一值，并记录是由哪一个子问题得到的elseif(c[i-1][j]>=c[i][j-1])//最后一值不等的情况，找x[m-1]和y及x和y[n-1]中较长的公共子序列，并记录

4、是由哪一个子问题得到的{c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=3;}}}voidlcs(inti,intj,char*x,intb[][20]){if(i==0

5、

6、j==0)return;//无值时返回if(b[i][j]==1){lcs(i-1,j-1,x,b);printf("%c",x[i]);}//根据某值是由哪个子问题的到的，循环调用求其最长公共子序列elseif(b[i][j]==2)lcs(i-1,j,x,b);elselcs(i,j-1,x,b);}1）运行成功，截图如下：二、最大子段和问

7、题（分治算法）1）程序代码：#includeintmaxsubsum(inta[6],intleft,intright);voidmain(){intk;5inta[6]={-2,11,-4,13,-5,-2};k=maxsubsum(a,0,5);printf("*************************");printf("求整数序列的最大子段和问题（分治算法）");printf("*************************");printf("整数序列-2,11,-4,13,-5,-2的最大子段和为：%d",k);}intmaxsub

8、sum(inta[6],intleft,intright){intsum=0;if(left==right)sum=a[left]>0?a[left]:0;//当数列只有一个元素时，若为负数，则将sum赋为0，否则输出sum值else{intcenter=(left+right)/2;//取中间数intleftsum=maxsubsum(a,left,center);//对数组左半段递归求和intrightsum=maxsubsum(a,center+1,right);//对数组右半段递归求和ints1=0;//左右两段均包含最大子段和中数的情况intlefts=0;for(inti=

9、center;i>=left;i--){//求左半段中的最大子段和lefts+=a[i];if(lefts>s1)s1=lefts;}ints2=0;intrights=0;for(i=center+1;i<=right;i++){//求右半段中的最大子段和rights+=a[i];if(rights>s2)s2=rights;}sum=s1+s2;//第三种情况中的最大子段和if(sum