算法分析与设计-作业九-最大子列和问题

1、问题

求解两个序列x,y的最大公共子列问题

2、解析

3、设计

void Max(int c[100][100], int B[100][100], char x[], char y[], int xn, int yn) {
//i表示数组x的下标，j表示数组y的下标
//B[i][j] o表示删除x的末尾一位，1表示删除末尾一位，2表示删除x,y数组末尾两位
int i, j;
//temp1,temp2分别表示x，y数组的元素的下标
char temp1, temp2;
for (i = 1; i <= xn; i++) {
for (j = 1; j <= yn; j++) {
//如果x[i]=y[j]，那么c[i][j]=c[i-1][j-1]+1,B[i][j]=2
//如果不相等，就为从max{c[i][j-1],c[i-1][j]},B为1/0
if (x[i] == y[j]) {
c[i][j] = c[i - 1][j - 1] + 1;
B[i][j] = 2;
}
else {
if (c[i][j - 1] >= c[i - 1][j]) {
c[i][j] = c[i][j - 1];
B[i][j] = 1;
}
else {
c[i][j] = c[i - 1][j];
B[i][j] = 0;
}
}
}
}
stack s = creatStack();
temp1 = xn, temp2 = yn;
//B[i][j]=0，x下标减一，=1，y数组下标减一，=2，x,y数组下标同时减1，并且将元素push到堆栈里
while (temp1 > 0 && temp2 > 0) {
if (B[temp1][temp2] == 2) {
push(s, x[temp1]);
temp1 -= 1;
temp2 -= 1;
}
else if (B[temp1][temp2] == 1) {
temp2 -= 1;
}
else {
temp1 -= 1;
}
}

for (i = 0; i <= xn; i++) {
for (j = 0; j <= yn; j++) {
printf("%d “, c[i][j]);
}
printf(”\n");
}
for (i = 1; i <= xn; i++) {
for (j = 1; j <= yn; j++) {
printf("%d “, B[i][j]);
}
printf(”\n");
}
//将最大子列从堆栈里pop出来
for (int k= 0; k < c[xn][yn];k++) {
if (k != c[xn][yn] - 1)
printf("%c “, pop(s));
else printf(”%c\n", pop(s));
}
}

4、分析

m=xn,n=yn时间复杂度为：O（mn)

5、源码

源码地址：https://github.com/ACynj/lcs.git