文档介绍：实验课程:算法分析与设计实验名称:实验3动态规划算法(综合性/设计性)实验目标: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的最长公共子序列。 实验设备及环境:PC;C/C++的编程环境VisualC++。实验主要步骤:明确实验目标和具体任务;理解实验所涉及的动态规划算法;编写程序并实现动态规划算法;设计实验数据并运行程序、记录运行的结果;实验数据及运行结果、实验结果分析及结论:(学生填写)#include<>#include<>voidLcsLength(char*x,char*y,intm,intn,intc[][100],intb[][100]){puts(x);puts(y);inti,j;for(i=0;i<=m;i++) c[i][0]=0; for(j=1;i<=n;j++) c[0][j]=0; for(i=1;i<=m;i++) for(j=1;j<=n;j++) { if(x[i-1]==y[j-1]) { c[i][j]=c[i-1][j-1]+1;b[i][j]=0;} elseif(c[i-1][j]>=c[i][j-1]) { c[i][j]=c[i-1][j]; b[i][j]=1;} else { c[i][j]=c[i][j-1];b[i][j]=-1; }}}voidPrintLCS(intb[][100],char*x,inti,intj){if(i==0||j==0)return;if(b[i][j]==0) {PrintLCS(b,x,i-1,j-