



下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、矩阵链最小乘法次数的上机报告实验名称:矩阵链相乘问题;实验内容与要求:用动态规划策略求矩阵链相乘的最小乘法次数及乘法方式;代码浅析:定义矩阵链大小SIZE为6,以rSIZE+1存储各行大小及末尾矩阵列大小、cSIZESIZE作矩阵存储上三角求解的最小乘法次数结果,pointSIZESIZE存储对应C(i,j)=minC(I,k-1)+C(k,j)+ri*rk*rj最小时的k值;/当然可以用一维数组存储上三角矩阵,此处为容易编程先不考虑空间优化;主体函数照搬书上,为适配C+语言将数组下标及循环上界分别修改为0/SIZE-d,另外用选择的思想设置临时变量temp与最小的C(i,j)进行交换,并同时
2、设置pointij=k,此时最后修改的k即是最小乘法的分割点;用递归调用的方法进行加括号打印,递归终点是对角线上的元素,此时为Mi;而任意上三角的cij=cik-1*ckcj,此时k即为pointij;附:为打印漂亮,附加添加t的函数,不过实际效果并不漂亮:测试用例:上机PPT上例子测试:分别调整M1-6的行大小来比较最终最小乘法次数的变化:M1:?*500 M2:500*10 M3:10*300 M4:300*1000 M5:1000*100 M6:100*500M1最小乘法次数乘法方式1458000(M1M2)M3)M4)M5)M6)104560000(M1M2)(M3M4)M5)M6)1
3、005500000(M1M2)(M3M4)M5)M6)100014500000(M1M2)(M3M4)M5)M6)10000-1787967296(溢出)(M1M2)(M3M4)M5)M6)M1:300*? M2:?*10 M3:10*300 M4:300*1000 M5:1000*100 M6:100*500M2最小乘法次数乘法方式1603000(M1(M2M3)M4)M5)M6)106010000(M1(M2(M3M4)M5)M6)1006300000(M1M2)(M3M4)M5)M6)10009000000(M1M2)(M3M4)M5)M6)1000036000000?(M1M2)(M3
4、M4)M5)M6)M1:300*500 M2:500*? M3:?*300 M4:300*1000 M5:1000*100 M6:100*500M3最小乘法次数乘法方式1570000(M1M2)(M3M4)M5)M6)105700000(M1M2)(M3M4)M5)M6)10031500000(M1(M2(M3(M4(M5M6)1000程序崩溃10000程序崩溃总结:由动态规划递推式可知,该算法为O(n3)时间和O(n2)空间的复杂度;观察程序求取结果,可知在矩阵过大时乘法次数超过int所表示的231-1的上界而溢出,因此也无法给出正确的乘法方式;而在远超过其他矩阵数量级并不引起程序崩溃时,最
5、小乘法次数有比较良好的线性性质,并且乘法方式不会改变;当n极小时有”洼地效应“,即乘法方式向最小维的矩阵倾斜,通常在多重括号的里面;对比自然矩阵链相乘与最小乘法次数的运行时间差异:/为防止溢出,采用-5,+5区间生成的随机数进行实验M1:?*500 M2:500*10 M3:10*300 M4:300*1000 M5:1000*100 M6:100*500M1自然链乘/ms最小乘法/ms100101.51.510015.61.910004.9M1:300*? M2:?*10 M3:10*300 M4:300*1000 M5:1000*100 M6:100*500M2自然链乘/ms最小乘法/ms100.21046.22.010047.32.110003.1M1:300*500 M2:500*? M3:?*300 M4:300*1000 M5:1000*100 M6:100*500M3自然链乘/ms最小乘法/ms146.00.21046.81.910054.110.71000由上述表格可以看出,自然链乘时,除非首部行
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 保护嗓子的课件
- 视觉导视设计核心要素与应用规范
- 心机病的健康宣教
- 二零二五年度知识产权常年法律顾问服务协议
- 二零二五年茶叶茶具品牌销售代理合同
- 二零二五年度电动车辆使用权及所有权转移合同
- 2025班组劳务分包合同书-智能工厂建设专用范本
- 2025年度旅游景区环境清洁与维护服务协议
- 二零二五年度P2P投资咨询与市场分析服务协议
- 二零二五年度4S店汽车销售与汽车美容保养及维修服务合同
- 2025房县事业单位笔试真题
- DBJ50T-195-2025 混凝土抗压强度检测技术标准
- 《南昌市海绵城市建设规划设计导则》
- 牙齿漂白治疗技术操作指南
- 道路施工工艺培训
- 2025-2030全球及中国乙酰柠檬酸三丁酯(ATBC)行业市场现状供需分析及市场深度研究发展前景及规划可行性分析研究报告
- 克罗恩病诊断与治疗课件
- 2025济宁市泗水县泗河街道社区工作者考试真题
- 初二化学全套试题及答案
- 核心素养教学落地四大关键策略
- 融资代建合同模板5篇
评论
0/150
提交评论