实验四：动态规划法求最长子序列.docVIP

实验四：动态规划法求两个序列的最长公共子序列及其长度 姓名：刘桂莲 班级：计科2班（数字媒体） 学号：1025113018 实验内容 应用第8章的动态规划法求出两个序列中最长的公共子序列及其长度。分析时间复杂度。例如，”123”和”132”的最长公共子序列是”12”（不一定是连续的）。 算法思想 动态规划的思想： 对较小的子问题进行一次求解，并把结果记录下来，然后利用较小问题的解，求解出较大问题的解，直到求解出最大问题的解。 引进一个二维数组ch[MAX][MAX]，用ch[i][j]记录CH1与CH2的LCS 的长度，b[i][j]记录ch[i][j]是通过哪一个子问题的值求得的，以决定有哪些信誉好的足球投注网站的方向。我们是自底向上进行递推计算，那么在计算ch[i,j]之前，ch[i-1][j-1]，ch[i-1][j]与ch[i][j-1]均已计算出来。此时我们根据CH1 [i] = CH2[j]还是CH1[i] != CH2[j]，就可以计算出ch[i][j]。 算法 length(string CH1,string CH2,int b[MAX][MAX]) //用于构建动态数组 //输入：两字符窜 //输出：最长公共子序列 for(i=1;i=ch1Len;i++)//二重循环求解 for(int j=1;j=ch2Len;j++) { if(CH1[i-1]==CH2[j-1])//相等字符 { ch[i][j]=ch[i-1][j-1]+1; b[i][j]=0; } else if(ch[i-1][j]=ch[i][j-1])//上比较大 { ch[i][j]=ch[i-1][j]; b[i][j]=1; } else//左比较大 { ch[i][j]=ch[i][j-1]; b[i][j]=-1; } } printCS(int b[MAX][MAX],string x,int i,int j) //回溯求出最长子序列输出 //输入：标记数组 //输出：最长子序列 if(i == 0 || j == 0)//边界，返回 return; if(b[i][j] == 0) { printCS(b, x, i-1, j-1);//左上 coutx[i-1] ; } else if(b[i][j] == 1) printCS(b, x, i-1, j);//上 else printCS(b, x, i, j-1);//左 源程序 #includeiostream #includecstring #includestring using namespace std; #define MAX 100 //**************打印二维数组函数************************************** void print(int a[MAX][MAX],int b,int c) { for(int i=0;i=b;i++) { for(int j=0;j=c;j++) { couta[i][j] ; } coutendl; } } //*******************求最长子序列长度************************** int length(string CH1,string CH2,int b[MAX][MAX]) { int ch[MAX][MAX],max=1; int ch1Len=CH1.length(),ch2Len=CH2.length();//求字符窜长度 for(int i=0;i=ch1Len;i++)//初始化动态数组为0 for(int j=0;j=ch2Len;j++) { ch[i][j]=0; } for(i=1;i=ch1Len;i++)//二重循环填充动态数组 for(int j=1;j=ch2Len;j++) { if(CH1[i-1]==CH2[j-1])//相等字符 { ch[i][j]=ch[i-1][j-1]+1; b[i][j]=0; } else if(ch[i-1][j]=ch[i][j-1])//上比较大 { //ch[i][j]=Max(ch[i][j-1] , ch[i-1][j]); ch[i][j]=ch[i-1][j]; b[i][j]=1; } else//左比较大