矩阵连乘和最长公共子序列问题算法设计 - 图文

.

师学院数学与计算机科学学院 《算法分析与设计》实验报告

实验序号：5实验项目名称：矩阵连乘和最长公共子序列问题算法设计 学 号 实验地点 一、实验目的及要求 （1） 掌握使用动态规划方法设计最优值问题的方法； （2） 能够使用动态规划算法设计策略设计矩阵连乘和最长公共子序列问 姓 名 指导教师 专业、班 时间 2014年4月28日 题的算法； 二、实验设备（环境）及要求 1、环境要求： 硬件：PC（PII以上，128M以上存）、因特网接入； 软件：Windows XP操作系统、VC++6.0编程环境。 2、实验要求： (1) 独立完成实验，源代码书写规； (2) 程序运行结果以屏幕截图的方式粘贴在对应位置，截图必须清晰准确； (3) 实验完成后必须有实验结果的分析及本次实验的总结。 三、实验容与步骤 (1) 设计求解n个矩阵连乘的最优计算次序问题的程序，并将在最优计算次序下所需的乘法次数及最优计算次序在屏幕上显示。n个矩阵的维数从键盘输入。 #include #define N 5 //此处N值为存储矩阵行列数的数组的元素个数 int matrixchain(int p[N],int m[N][N],int s[N][N]) { int i,j,r,t,k,n=N-1; for(i=1;i<=n;i++) .

.

m[i][i]=0; for(r=2;r<=n;r++) } void traceback(int s[N][N],int i,int j) { if(i==j) for(i=1;i<=n-r+1;i++) { } return m[i][n]; j=r+i-1; m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];; s[i][j]=i; for(k=i+1;k

.

printf(\ else if(i+1==j) printf(\ else { } } void display(int a[N][N]) { int i,j; printf(\ \ for(i=1;i

.

} } for(j=1;j

.

printf(\ matrixchain(p,m,s); printf(\最优解如下：\\n\ printf(\矩阵：\\n\ display(m); printf(\矩阵：\\n\ display(s); printf(\个矩阵连乘的最优乘法次数：%d\ printf(\个矩阵连乘的最优计算次序：\ traceback(s,1,N-1); return 0; } (2) 设计求解x和y两个序列的最长公共子序列问题的程序，并将最长公共子序列的长度及最长公共子序列在屏幕上显示。 #include #define M 8 #define N 7 int lcslength(char x[M+1],char y[N+1],int b[M+1][N+1]); void lcs(int i,int j,char x[M+1],int b[M+1][N+1]); int main( ) { char x[M+1],y[N+1]; .

.

int b[M+1][N+1],maxlen; printf(\输入长度为M=%d序列x:\gets(x); printf(\输入长度为N=%d序列y:\gets(y); maxlen=lcslength(x,y,b); printf(\最长公共子序列的长度：%d\\n\ } int lcslength(char x[M+1],char y[N+1],int b[M+1][N+1]) { int m=M,n=N,i,j,c[M+1][N+1]; for(i=1;i<=m;i++) c[i][0]=0; printf(\最长公共子序列：\lcs(M,N,x,b); printf(\return 0; for(j=1;j<=n;j++) c[0][j]=0; for(i=1;i<=m;i++) { for(j=1;j<=n;j++) { .

.

} } } if(x[i]==y[j]) { } else if(c[i-1][j]>c[i][j-1]) { } else { } c[i][j]=c[i][j-1]; b[i][j]=3; c[i][j]=c[i-1][j]; b[i][j]=2; c[i][j]=c[i-1][j-1]+1; b[i][j]=1; return c[m][n]; void lcs(int i,int j,char x[M+1],int b[M+1][N+1]) { if(i==0 || j==0) .

.

return; if(b[i][j]==1) { } else if(b[i][j]==2) lcs(i-1,j,x,b); lcs(i-1,j-1,x,b); printf(\else lcs(i,j-1,x,b); }四、实验结果与数据处理 1. 2.最长公共子序列长度： .

.

五、分析与讨论 1、比较备忘录方法和动态规划方法求矩阵连乘问题的特点。 备忘录方法是动态规划算法的变形。与动态规划算法一样，备忘录方法用表格保存已解决的子问题的答案，在下次需要解此子问题时，只要简单地查看该子问题的解答，而不必重新计算。与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上递归的。因此，备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。 2. 分析求最长公共子序列长度和构造最长公共子序列两种算法的时间复杂度。 最长公共子序列长度算法的时间复杂度为：O（MN）； 构造最长公子序列算法的时间复杂度为：O（M+N）。 六、教师评语 成绩 签名： 日期： 年 月 日

.