动态规划算法应用.docVIP

宁夏师范学院数学与计算机科学学院 《》实验报告 实验序号：　　　　　　　　　　实验项目名称：学　　号 姓　　名 专业、班 实验地点 指导教师 时间 2013-4-18 (1)、熟悉最长公共子序列问题的算法； (2)、初步掌握动态规划算法； 二、实验设备（环境）及要求 1、环境要求： 硬件：PC（PII以上，128M以上内存）、因特网接入； 软件：Windows XP操作系统、Office2003、多媒体播放软件。 三、实验内容与步骤 给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。 给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。 四、实验结果与数据处理 #includestdio.h #define M 6 #define N 6 int c[N][M]; int b[N][M]; int IcsLength(char x[],char y[]) { int m=M-1; int n=N-1; int i,j; for(i=1;i=M;i++) c[i][0]=0; for(i=1;i=N;i++) c[0][i]=0; for(i=1;i=M;i++) for(j=1;j=N;j++) { if(x[i]==y[j]) { c[i][j]=c[i-1][j-1]+1; b[i][j]=1; } else if(c[i-1][j]=c[i][j-1]) { c[i][j]=c[i-1][j]; b[i][j]=2; } else{ c[i][j]=c[i][j-1]; b[i][j]=3; } } return c[m][n]; } int Ics(int i,int j,char x[]) { if(i==0||j==0) return 0; if(b[i][j]==1) { Ics(i-1,j-1,x); printf(%c\n,x[i]); } else if(b[i][j]==2) Ics(i-1,j,x); else Ics(i,j-1,x); return 0; } void main() { char x[]={A,0,C,B,D,A,B}; char y[]={0,B,D,C,A,B,A}; int i,j; printf(长度为%d\n,IcsLength(x,y)); for(i=0;iM;i++) { for(j=0;jN;j++) { printf(%d\t,c[i][j]); } printf(\n); } for(i=0;iM;i++) { for(j=0;jN;j++) { printf(%d\t,c[i][j]); } printf(\n); } Ics(M-1,N-1,x); } 五、分析与讨论 建立子问题最优值的递归关系。用c[i][j]记录序列Xi和Yi的最长公共子序列的长度。其中，Xi={x1,x2,…,xi};Yi={y1,y2,….yj}.当i=0或j=0时，空序列是Xi和Yi的最长公共子序列，故此时c[i][j]=0 输出两个数组c和b。其中，c[i][j] 存储Xi和Yj的最长公共子序列的长度，b[i][j]记录c[i][j]的值是由哪一个子问题的解得到的，这在构造最长公共子序列时要用到 结论： 由于每个数组单元的计算耗费O（1）时间，算法lcsLength耗时O（mn） 六、教师评语 成绩