求取最长公共递增子序列LICS并打印（C++)

是老师的作业，只是无情的完成作业机器罢了（

题目：

输入：由n个数组成的一个序列S：a1,a2,…,an, 

           由m个数组成的一个序列T: b1,b2,…bm.

输出：S和T的公共子序列X=c1c2,…,ck ，满足：

            (1) c1<=c2 <= … <= ck ，

            (2) |X|最大

解法：首先是错误解法！！！

哭了，写了半天的代码结果老师说是错误的，不甘心还是放上来以此为鉴，反正也是LCS和LIS的思路

错误解法是笨方法，就是先求取最长公共子序列（LCS, Longest Common String)，再求取其最长递增子序列（LIS, Longest Increasing String)，建议先了解LCS和LIS的各自的思路再看代码。

求取最长递增子序列（LIS）：

int findLIS(int x[], int* d, int length_x){                 // 求取并存储最长递增子序列d[0] = x[0];                                            // d为存储的器具int len = 1;                                            // LIS的长度，初始为1for(int i=1; ix[i])d[0] = x[i];else{d[1] = x[i];len++;}}else if (x[i]=d[len-2]){          // 发现当前元素可替换LIS最后一个元素，有点像贪心算法d[len-1] = x[i];}else if (x[i]>=d[len-1]){                           // 比LIS最后一个元素大，纳入其中d[len] = x[i];len++;}  }return len;                                             // 返回LIS的长度
}

求取最长公共子序列（LCS）：

#define max_length 100                                      // 规定求取的数组的最大长度void findLCS(int C_choice[][max_length], int x[], int* LCS_store, int i, int j, int k){  // 存储最长公共子序列if (i==0 || j==0){}else if (C_choice[i][j] == 1){                          // 第一种收录方式，从对角线获取LCS_store[--k] = x[i-1];                            // LCS_store是存储器具findLCS(C_choice, x, LCS_store, i-1, j-1, k);}else if (C_choice[i][j] == 2){                          // 分别是第二种、第三种收录方式findLCS(C_choice, x, LCS_store, i, j-1, k);}else{findLCS(C_choice, x, LCS_store, i-1, j, k);}
}int main(){int C[max_length][max_length];                          // 最长公共子序列求取int C_choice[max_length][max_length];                   // 存储LCS的收录方式int LCS_store[max_length];                              // 用于存储最长公共子序列for (int i=0; iC[i-1][j]){                   // 继承左边或者上边较大的LCS的length并记录收录方式C[i][j] = C[i][j-1];C_choice[i][j] = 2;                         // 收录方式2// cout << C[i][j] << ' ';}else{C[i][j] = C[i-1][j];C_choice[i][j] = 3;                         // 收录方式3// cout << C[i][j] << ' ';}}// cout << '\n';}findLCS(C_choice, x, LCS_store, length_x, length_y, C[length_x][length_y]);     // 求取LCS的LIS，即LICS
}

 总代码：

#include 
#include 
#include 
#include 
using namespace std;#define max_length 100                                      // 规定求取的数组的最大长度void findLCS(int C_choice[][max_length], int x[], int* LCS_store, int i, int j, int k){  // 存储最长公共子序列if (i==0 || j==0){}else if (C_choice[i][j] == 1){                          // 第一种收录方式，从对角线获取LCS_store[--k] = x[i-1];                            // LCS_store是存储器具findLCS(C_choice, x, LCS_store, i-1, j-1, k);}else if (C_choice[i][j] == 2){                          // 分别是第二种、第三种收录方式findLCS(C_choice, x, LCS_store, i, j-1, k);}else{findLCS(C_choice, x, LCS_store, i-1, j, k);}
}int findLIS(int x[], int* d, int length_x){                 // 求取并存储最长递增子序列d[0] = x[0];                                            // d为存储的器具int len = 1;                                            // LIS的长度，初始为1for(int i=1; ix[i])d[0] = x[i];else{d[1] = x[i];len++;}}else if (x[i]=d[len-2]){          // 发现当前元素可替换LIS最后一个元素，有点像贪心算法d[len-1] = x[i];}else if (x[i]>=d[len-1]){                           // 比LIS最后一个元素大，纳入其中d[len] = x[i];len++;}  }return len;                                             // 返回LIS的长度
}int LICS(int x[], int y[], int* d, int length_x, int length_y){                        // 求LCS，进而求LICS，算法关键函数int C[max_length][max_length];                          // 最长公共子序列求取int C_choice[max_length][max_length];                   // 存储LCS的收录方式int LCS_store[max_length];                              // 用于存储最长公共子序列for (int i=0; iC[i-1][j]){                   // 继承左边或者上边较大的LCS的length并记录收录方式C[i][j] = C[i][j-1];C_choice[i][j] = 2;                         // 收录方式2// cout << C[i][j] << ' ';}else{C[i][j] = C[i-1][j];C_choice[i][j] = 3;                         // 收录方式3// cout << C[i][j] << ' ';}}// cout << '\n';}findLCS(C_choice, x, LCS_store, length_x, length_y, C[length_x][length_y]);     // 求取LCS的LIS，即LICSreturn findLIS(LCS_store, d, C[length_x][length_y]);    // 返回最终LICS的长度，便于打印// return C[length_x][length_y];
}int main(){int x[5] = {5, 2, 1, 3, 4};int y[7] = {9, 5, 2, 5, 3, 4, 1};int d[max_length];   int len = LICS(x, y, d, 5, 7);cout << "LICS: ";for(int i=0; i

#include
#includeint f[1005][1005];                              // 存储当前LICS的最大值
int a[1005], b[1005];                           // 两个目标数组
int i, j;                                       // 用于for循环的工具变量
int n, m, max;                                  // 两个目标数组的长度以及每行所匹配的最大值
int result[1005];                               // 用于存储最终的LICS结果int main()
{printf("请输入两个数组的长度："); scanf("%d%d", &n, &m);printf("数组1：");for (i=1; i<=n; i++) scanf("%d", &a[i]);printf("数组2：");for (i=1; i<=m; i++) scanf("%d", &b[i]);memset(f, 0, sizeof(f));                    // 初始化f，将所有元素置为0for(i=1; ib[j] && max收录进当前的LICSf[i][j] = max+1;                // 因为收录了新的元素，所以在max的基础上+1if (max+1 == f[i-1][j]) max++;  // 为了防止出现LICS中末尾元素等于倒数第二个元素的情况，这里需要增加max}}}max = 0;int len = 0;                                // 记录最终的LICS的长度for(j=1; j<=m; j++)                         // 将最后一行单独分析，因为最终的结果就出自最后一行{f[n][j] = f[n-1][j];if (a[n]>b[j] && max f[n-1][j]){result[len] = b[j];len++;}}}// for (i=0; i<=n; i++){                    // 如果还是看不太懂可以取消这里的注释//     for (j=0; j<=m; j++){                // 看看f是如何计算的，这样会比较直观一点//         printf("%d ", f[i][j]);//     }//     printf("\n");// }printf("最长公共递增子序列为：");for(i=0; i

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！