矩阵连乘备忘录算法4.docVIP

湖南涉外经济学院 计算机科学与技术专业 《算法设计与分析》课程 矩阵连乘备忘录算法 实 验 报 告 班级： 学号： 姓名： 教师： 成绩： 2012年5月 【实验目的】1 掌握动态规划算法和 2 利用动态规划思想实现3 分析实验结果，总结算法的时间和空间复杂度。思考是否能将算法的时间复杂度提高到O(nlgn) 【系统环境】Windows 07 平台 【实验工具】VC++6.0中文企业版【】描述： …，An}，其中Ai与Ai+1可乘的，i=1,2，…，n-1。找出这个n个矩阵的连乘A1A2…An所需相乘的最少次数的方式。 例： 【实验原理】LookupChain时，若m[i][j]0，则表示其中储存的是所要求子问题的计算结果，直接返回此结果即刻。否则与直接递归算法一样，自顶而下的递归计算，并将计算结果存入m[i][j]后返回。因此，LookupChain总能返回正确的值，但仅在它第一次被调用时计算，以后调用就直接返回计算结果。 方法：用MemorizedMatrixChain函数将已经计算的数据存入表中，用LookupChain函数配合MemorizedMatrixChain函数递归调用计算。 【】#includestdio.h #includestdlib.h #includectime #define N 10 int p[N],m[N][N],s[N][N]; int LookupChain(int i,int j); //备忘录算法函数 int MemorizedMatrixChain(int n,int **m,int **s) { for(int i=1;i=n;i++) for(int j=i;j=n;j++) m[i][j]=0; return LookupChain(1,n); } //递归调用函数 int LookupChain(int i,int j) { if(m[i][j]0) return m[i][j]; if(i==j) return 0; int u=LookupChain(i,i)+LookupChain(i+1,j)+p[i-1]*p[i]*p[j]; s[i][j]=i; for(int k=i+1;kj;k++) { int t=LookupChain(i,k)+LookupChain(k+1,j)+p[i-1]*p[k]*p[j]; if(tu) { u=t; s[i][j]=k; } } m[i][j]=u; return u; } //输出格式函数 void Print(int s[][N],int i,int j) { if(i==j) { printf(A); printf(%d,i); } else { printf((); Print(s,i,s[i][j]); Print(s,s[i][j]+1,j); printf()); } } //主函数 int main() { srand(time(NULL)); for(int i=0;iN;i++) p[i]=rand()%100;//随机生成； for(i=0;iN;i++) printf(%4d,p[i]); printf(\n); int result=LookupChain(1,N-1); printf(最少次数：\n); printf(%d\n\n\n,result); printf(最优次序：\n); Print(s,1,N-1); printf(\n); return 0; }【实验结果】运行结果图 【】MemorizedMatrixChain耗时O（n^3）。