矩阵连乘备忘录算法.doc

湖南涉外经济学院 计算机科学与技术专业算法设计与分析课程 矩阵连乘备忘录算法 实 验 报 告班级： 学号： 姓名： 教师： 成绩： 2012年5月【实验目的】1 掌握动态规划算法和备忘录方法；2 利用动态规划备忘录思想实现矩阵连乘；3 分析实验结果，总结算法的时间和空间复杂度。思考是否能将算法的时间复杂度提高到O(nlgn)【系统环境】Windows 07 平台【实验工具】VC+6.0中文企业版【问题描述】 描述： 给定n个矩阵A1，A2，An，其中Ai与Ai+1可乘的，i=1,2，n-1。找出这个n个矩阵的连乘A1A2An所需相乘的最少次数的方式。例：矩阵连乘积A1A2A3A4可以有一下五种不同的完全加括号方式：（A1（A2（A3A4）（A1（A2A3）A4）（A1A2）（A3A4）（A1（A2A3）A4）（A1A2）A3）A4）【实验原理】原理：1、矩阵连乘满足结合律，且不同的结合方式，所需计算的次数不同。 2、利用备忘录方法，用表格保存以解决的子问题答案，降低重复计算，提高效率。思路：m初始化为0，表示相应的子问题还位被计算。在调用LookupChain时，若mij0，则表示其中储存的是所要求子问题的计算结果，直接返回此结果即刻。否则与直接递归算法一样，自顶而下的递归计算，并将计算结果存入mij后返回。因此，LookupChain总能返回正确的值，但仅在它第一次被调用时计算，以后调用就直接返回计算结果。方法：用MemorizedMatrixChain函数将已经计算的数据存入表中，用LookupChain函数配合MemorizedMatrixChain函数递归调用计算。【源程序代码】#include#include#include#define N 10int pN,mNN,sNN;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;j0)return mij;if(i=j)return 0;int u=LookupChain(i,i)+LookupChain(i+1,j)+pi-1*pi*pj;sij=i;for(int k=i+1;kj;k+) int t=LookupChain(i,k)+LookupChain(k+1,j)+pi-1*pk*pj; if(tu) u=t; sij=k; mij=u; return u;/输出格式函数void Print(int sN,int i,int j) if(i=j) printf(A);printf(%d,i); else printf(); Print(s,i,sij); Print(s,sij+1,j); printf(); /主函数int main()srand(time(NULL);for(int i=0;iN;i+)pi=rand()%100;/随机生成；for(i=0;iN;i+)printf(%4d,pi);printf(n);int result=LookupChain(1,N-1);printf(最少次数：n);printf(%dnnn,result);printf(最优次序：n);Print(s,1,N-