1、1、最长公共子序列问题1）程序代码：#includevoid length(int m,int n,char *x,char *y,int c20,int b20);void lcs(int i,int j,char *x,int b20); void main() char x20,y20;int c2020,b2020;int m=1,n=1;printf(“ * * * * * * * * * * * * * * * * * * n“);printf(“ 求最长公共子序列问题 n“);printf(“ * * * * * * * * * * * * * * * * * * n“);pri
2、ntf(“ 请输入 X 序列：“); /输入 x 序列while(1)scanf(“%c“,if(xm!=n) m+;else break;m- =1;printf(“ 请输入 Y 序列：“); /输入 y 序列while(1)scanf(“%c“,if(yn!=n) n+;else break;n- =1;length(m,n,x,y,c,b);printf(“ x 和 y 的最长公共子序列为： “);lcs(m,n,x,b);printf(“ 其长度为： %dn“,cmn);void length(int m,int n,char *x,char *y,int c20,int b20) i
3、nt i,j;for (i = 0; i =cij-1) /最后一值不等的情况，找 xm-1和 y 及 x 和 yn-1中较长的公共子序列，并记录是由哪一个子问题得到的 cij=ci-1j; bij=2;else cij=cij-1; bij=3; void lcs(int i,int j,char *x,int b20)if (i=0|j=0) return ; /无值时返回if (bij=1) lcs(i-1,j-1,x,b); printf(“ %c “,xi); /根据某值是由哪个子问题的到的，循环调用求其最长公共子序列else if (bij=2) lcs(i-1,j,x,b);el
4、se lcs(i,j-1,x,b);2）运行成功，截图如下：二、最大子段和问题（分治算法）1）程序代码：#includeint maxsubsum(int a6,int left,int right);void main()int k;3int a6=-2,11,-4,13,-5,-2;k=maxsubsum(a,0,5);printf(“ * * * * * * * * * * * * * * * * * * * * * * * * * n“);printf(“ 求整数序列的最大子段和问题（分治算法） n“);printf(“ * * * * * * * * * * * * * * * *
5、* * * * * * * * * n“);printf(“ 整数序列 -2,11,-4,13,-5,-2 的最大子段和为：%d“,k);int maxsubsum(int a6,int left,int right)int sum=0;if(left=right) sum=aleft0?aleft:0; /当数列只有一个元素时，若为负数，则将 sum 赋为 0，否则输出 sum 值elseint center=(left+right)/2; /取中间数int leftsum=maxsubsum(a,left,center); /对数组左半段递归求和int rightsum=maxsubsum
6、(a,center+1,right); /对数组右半段递归求和int s1=0; /左右两段均包含最大子段和中数的情况int lefts=0;for(int i=center;i=left;i-) /求左半段中的最大子段和lefts+=ai;if(leftss1) s1=lefts;int s2=0;int rights=0;for(i=center+1;is2) s2=rights;sum=s1+s2; /第三种情况中的最大子段和if(sumint maxsum(int n, int a6);void main()int k;int a6=-2,11,-4,13,-5,-2;k=maxsum
7、(6,a);printf(“ * * * * * * * * * * * * * * * * * * * * * * * * * n“);printf(“ 求整数序列的最大子段和问题（动态规划算法） n“);printf(“ * * * * * * * * * * * * * * * * * * * * * * * * * n“);printf(“ 整数序列 -2,11,-4,13,-5,-2 的最大子段和为：%d“,k);int maxsum(int n, int a6)int sum=0, b=0;for (int i=0; i0) b+=ai; /当 ai0 时，b=ai+ai+1;else b=ai; /否则， b=ai;if (bsum) sum=b; /将大值赋给 sumreturn sum; /返回最大子段和2）运行成功，截图如下：5
