实验四 动态规划算法

实验四动态规划算法一、实验目的与要求1、熟悉最长公共子序列问题的算法；2、初步掌握动态规划算法；二、实验题若给定序列X=x1,x2,xm，则另一序列Z=z1,z2,zk，是X的子序列是指存 在一个严格递增下标序列i1,i2,ik使得对于所有j=1,2,k有：zj=xij。例如，序列 Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相应的递增下标序列为2, 3， 5， 7。给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X 和Y的公共子序列。给定2个序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最长公共子序列。三、实验提示include stdlib.h#include string.hvoid LCSLength(char *x ,char *y,int m,int n, int *c, int *b)int i ,j;for (i = 1; i = m; i+) ci0 = 0;for (i = 1; i = n; i+) c0i = 0;for (i = 1; i = m; i+)for (j = 1; j =cij-1)cij=ci-1j;bij=2;elsecij=cij-1;bij=3;void LCS(int i ,int j, char *x ,int *b)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);else LCS(i,j-1,x,b);实现思路：设序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列为Z=z1,z2,，zk，则(1) 若xm=yn，zk=xm=yn，且zk-1是xm-1和yn-1的最长公共子序 列。(2) 若xm/yn且zk/xm，则Z是xm-1和Y的最长公共子序列。(3) 若xm/yn且zk/yn，则Z是X和yn-1的最长公共子序列。由此可见，2个序列的最长公共子序列包含了这2个序列的前缀 的最长公共子序列。因此，最长公共子序列问题具有最优子结 构性质。实验代码：#include stdafx.h”#include #include #include#includeusing namespace std;#define N 105int dpN+1N+1;char str1N , str2N;int maxx(int a , int b)if(a b)return a ;return b ;int LCSL(int len1 , int len2)int i , j ;int len = maxx(len1 , len2);for ( i = 0 ; i = len; i+ ) dpi0 = 0dp0i = 0for ( i = 1 ; i= lenl ; i+)for( j = 1 ; j dpij-1)LCS(i-1,j);elseLCS(i,j-1);int main()while (cin str1 str2)int len1 = strlen(str1) ;int len2 = strlen(str2) ;coutLCSL(len1 , len2)endl;LCS(len1,len2);return 0;实验结果：由茴户目录我的文档Vi号启 Studio 2010Projert5C_plusDehuabcdefrgabdefre6a b d e f r