矩阵连乘备忘录算法.doc

《矩阵连乘备忘录算法.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、湖南涉外经济学院计算机科学与技术专业《算法设计与分析》课程矩阵连乘备忘录算法实验报告班级：学号：姓名：教师：成绩：2012年5月【实验目的】1掌握动态规划算法和备忘录方法；2利用动态规划备忘录思想实现矩阵连乘；3分析实验结果，总结算法的时间和空间复杂度。思考是否能将算法的时间复杂度提高到O(nlgn)【系统环境】Windows07平台【实验工具】VC++6.0中文企业版【问题描述】描述：给定n个矩阵{A1，A2，…，An}，其中Ai与Ai+1可乘的，i=1,2，…，n-1。找出这个n个矩阵的连乘A1A2…An所需相乘的最少次数的方式

2、。例：矩阵连乘积A1A2A3A4可以有一下五种不同的完全加括号方式：（A1（A2（A3A4）））（A1（（A2A3）A4））（（A1A2）（A3A4））（（A1（A2A3））A4）（（（A1A2）A3）A4）【实验原理】原理：1、矩阵连乘满足结合律，且不同的结合方式，所需计算的次数不同。2、利用备忘录方法，用表格保存以解决的子问题答案，降低重复计算，提高效率。思路：m初始化为0，表示相应的子问题还位被计算。在调用LookupChain时，若m[i][j]>0，则表示其中储存的是所要求子问题的计算结果，直接返回此结果即刻。否则与直接递

3、归算法一样，自顶而下的递归计算，并将计算结果存入m[i][j]后返回。因此，LookupChain总能返回正确的值，但仅在它第一次被调用时计算，以后调用就直接返回计算结果。方法：用MemorizedMatrixChain函数将已经计算的数据存入表中，用LookupChain函数配合MemorizedMatrixChain函数递归调用计算。【源程序代码】#include#include#include#defineN10intp[N],m[N][N],s[N][N];intLooku

4、pChain(inti,intj);//备忘录算法函数intMemorizedMatrixChain(intn,int**m,int**s){for(inti=1;i<=n;i++)for(intj=i;j<=n;j++)m[i][j]=0;returnLookupChain(1,n);}//递归调用函数intLookupChain(inti,intj){if(m[i][j]>0)returnm[i][j];if(i==j)return0;intu=LookupChain(i,i)+LookupChain(i+1,j)+p[i-1]

5、*p[i]*p[j];s[i][j]=i;for(intk=i+1;k

6、j]+1,j);printf(")");}}//主函数intmain(){srand(time(NULL));for(inti=0;i

7、n0;}【实验结果】运行结果图【时间复杂度】备忘录算法MemorizedMatrixChain耗时O（n^3）。