tceic.com
学霸学习网 这下你爽了
赞助商链接
当前位置:首页 >> 学科竞赛 >>

矩阵链乘法


回专题模式 回学习阶段模式 【题目名称、来源】 最优 矩阵链乘法 (经典问题) 【问题描述】 7、矩阵链乘法 已知两个矩阵 A,B 的行列分别为 n*m 和 m*p 时才可以相乘,得到新的矩阵 AB,行 列值为 n*p,相乘时进行乘法的总次数为 n*m*p 次。 现 在 给 定 N 个 可 以 相 乘 的 矩 阵 构 成 一 个 链 A1,A2,…,An , 矩 阵 的 行 列 值 为 p0,p1,p2….,pn-1,pn,其中 p0,p1 为 A1 的行列值,p1,p2 为 A2 的行列值,pn-1,pn 为 An 的 行列值。 例如有 3 个矩阵组成的矩阵链 A1,A2,A3,他们的行列值为 10,100, 5 ,50,就是说 A1 的行列值为 10,100 A2 的行列值为 100,5 A3 的行列值为 5 ,50 如果按照( (A1A2)A3)的顺序做乘法, A1*A2 的乘法次数 10*100*5=5000,新矩阵 行列为 10,5。再和 A3 相乘,乘法次数为 10*5*50=2500,所以矩阵链乘法总次数为 5000+2500=7500 次。 如果按照(A1(A2A3) )的顺序做乘法,A2*A3 的乘法次数为 100*5*50=25000,新矩 阵行列为 100,50,然后用 A1 再乘以它,乘法次数为 10*100*50=50000,所以矩阵链乘法 总次数为 25000+50000=75000。是上一种方法的 10 倍。 你现在的任务是对于给定行列值的 n 个矩阵 A1A2…An, 找到一种乘法顺序, 使得总的 乘法次数最少。 输入: N 矩阵的个数 p0 p1 ……pn n+1 个数,代表 n 个矩阵的行列值 输出: 最小乘法次数 输入样例: 3 10 100 5 50 输出样例: 7500 【所属专题】 动态规划 【适合学习阶段】 第二阶段 【解题思路】 问题分析: 存储结构: 【测试数据】 【源程序】



推荐相关:

8皇后矩阵链乘

实验步骤:1.明确实验目标和实验任务 2.理解实验所涉及到动态规划法的思想 3.编写程序实现求矩阵链乘法的最优解。 4.设计实验数据数据并运行程序,记录运行的结果 ...


阵列乘法

矩阵乘法 24页 免费 矩阵乘法 8页 1下载券 矩阵乘法 3页 1下载券 矩阵...为了进一步提高乘法运算的 运算速度,可以采用类似于人工计算的方法,用阵列乘法器...


矩阵乘法

关于矩阵关于矩阵隐藏>> 矩阵乘法 [编辑] 一般矩阵乘积矩阵相乘最重要的方法当然是一般矩阵乘积了,它只有在第一个矩阵 的列数(column)和第二个矩阵的行数(row)...


算法练习题-1

用动态规划解决矩阵链乘法问题时,它的最优子结构(问题)是什么? 简述矩阵链乘法问题的动态规划算法. 并求解以下实例。 四、分析、计算题 1.考虑矩阵链乘法问题。...


八皇后 矩阵链乘 快速排序 合并排序 代码和实验报告

日月 实验指导老师 曹霑懋 实验评分 实验步骤: 实验步骤:1.明确实验目标和实验任务 2.理解实验所涉及到动态规划法的思想 3.编写程序实现求矩阵链乘法的最优解。...


算法设计与分析 关于矩阵乘法

关于矩阵乘法假定 A, B 都是 n×n 矩阵,它们的 i 行 j 列元素分别记为 A(i,j)和 B(i,j)。 如果用 S 和 C 分别记 A+B 和 A*B, 则有 S (...


矩阵乘法

矩阵乘法 24页 免费 对称矩阵 3页 1财富值 书法——行书课件 76页 免费 矩阵 71页 免费 行书笔画 35页 免费如要投诉违规内容,请到百度文库投诉中心;如要提...


矩阵乘法

矩阵运算及其应用 68页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 矩阵乘法 矩阵乘法矩阵乘法隐藏>> 矩阵乘法 ...


矩阵乘法

C++矩阵乘法源程序 15页 5财富值 动态规划实现矩阵连乘 C++ 7页 2财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。...


矩阵乘法

18页 20财富值 矩阵 9页 2财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 矩阵乘法 隐藏>> 矩阵乘法 C++源码:...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com