矩阵连乘备忘录算法.doc

矩阵连乘备忘录算法.doc

ID:25763341

大小:56.00 KB

页数:6页

时间:2018-11-22

矩阵连乘备忘录算法.doc_第1页
矩阵连乘备忘录算法.doc_第2页
矩阵连乘备忘录算法.doc_第3页
矩阵连乘备忘录算法.doc_第4页
矩阵连乘备忘录算法.doc_第5页
资源描述:

《矩阵连乘备忘录算法.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)。

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。