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

《矩阵连乘和最长公共子序列问题算法设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.宁夏师范学院数学与计算机科学学院《算法分析与设计》实验报告实验序号：5　　实验项目名称：矩阵连乘和最长公共子序列问题算法设计学　　号姓　　名专业、班实验地点指导教师时间2014年4月28日一、实验目的及要求（1）掌握使用动态规划方法设计最优值问题的方法；（2）能够使用动态规划算法设计策略设计矩阵连乘和最长公共子序列问题的算法；二、实验设备（环境）及要求1、环境要求：硬件：PC（PII以上，128M以上内存）、因特网接入；软件：WindowsXP操作系统、VC++6.0编程环境。2、实验要求：(1)独立完成实验，源代码书写规范；(2)程序运行结果以屏幕截

2、图的方式粘贴在对应位置，截图必须清晰准确；(3)实验完成后必须有实验结果的分析及本次实验的总结。三、实验内容与步骤(1)设计求解n个矩阵连乘的最优计算次序问题的程序，并将在最优计算次序下所需的乘法次数及最优计算次序在屏幕上显示。n个矩阵的维数从键盘输入。#include#defineN5//此处N值为存储矩阵行列数的数组的元素个数intmatrixchain(intp[N],intm[N][N],ints[N][N]){inti,j,r,t,k,n=N-1;for(i=1;i<=n;i++)m[i][i]=0;for(r=2;r<=n;

3、r++)for(i=1;i<=n-r+1;i++)..{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

4、",i,j);else{printf("(");traceback(s,i,s[i][j]);traceback(s,s[i][j]+1,j);printf(")");}..}voiddisplay(inta[N][N]){inti,j;printf("");for(i=1;i

5、p[N],m[N][N],s[N][N];printf("Thenumbersofmaxtri:%d",N-1);for(i=0;i

6、优解如下：");printf("m[%d][%d]矩阵：",N-1,N-1);display(m);printf("s[%d][%d]矩阵：",N-1,N-1);display(s);printf("%d个矩阵连乘的最优乘法次数：%d",N-1,m[1][N-1]);printf("%d个矩阵连乘的最优计算次序：",N-1);traceback(s,1,N-1);return0;}(2)设计求解x和y两个序列的最长公共子序列问题的程序，并将最长公共子序列的长度及最长公共子序列在屏幕上显示。#include#defin

7、eM8#defineN7intlcslength(charx[M+1],chary[N+1],intb[M+1][N+1]);voidlcs(inti,intj,charx[M+1],intb[M+1][N+1]);intmain(){charx[M+1],y[N+1];intb[M+1][N+1],maxlen;printf("输入长度为M=%d序列x:",M);..gets(x);printf("输入长度为N=%d序列y:",N);gets(y);maxlen=lcslength(x,y,b);printf("最长公共子序列的长度：%d",max

8、len);printf("最长公共子序列：");lcs(M,N,x,b);pri