



全文预览已结束
下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
矩阵连乘问题问题:给定的n个矩阵A1,A2,A3,A4,An,其中Ai与Ai+1是可乘的,i=1,2,3,n-1。考察这n个矩阵连乘积A1A2A3A4An。分析:由于矩阵乘法满足结合律,故计算矩阵的乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式确定。若一个矩阵的连乘次序完全确定,也就是说该连乘积已经完全加括号,则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可以递归的定义为:(1) 单个矩阵是完全加括号的(2) 矩阵连乘积A是完全加括号的,则A可表示为2个完全加括号的连乘积B和C的乘积并加括号,级A=(BC)。伪代码:1 计算最优值,依据其递归式以自底向上的方式进行计算。void matrixChain() for(int i=1;i=n;i+)mii=0; for(int r=2;r=n;r+)/对角线循环 for(int i=1;i=n-r+1;i+)/行循环 int j = i+r-1;/列的控制 /找mij的最小值,先初始化一下,令k=i mij=mi+1j+pi-1*pi*pj; sij=i; /k从i+1到j-1循环找mij的最小值 for(int k = i+1;kj;k+) int t=mik+mk+1j+pi-1*pk*pj; if(tmij) mij=t; /s用来记录在子序列i-j段中,在k位置处 /断开能得到最优解 sij=k; 2.按算法matrixChain计算,以加括号方式输出计算Ai:j的最优计算次序。void traceback(int i,int j) static int a=0; int x=0; int y=0; if(i=j)return ; traceback(i,sij); traceback(sij+1,j); for(int p=0;pa;p+) for(int q=0;qijpq)x+; if(jijpq)y+; insert(i+x,j+y,n);ija0=i;ija1=j;a+;n=n+2;/数组每次增加2/即增加了左右括号 3,在原数组ABC间插入括号void insert(int i,int j,int m)/插入括号 int x=m; for(;x=i;x-) linex+1=linex; linex+1=(; x=m+1; j+; for(;xj;x-) linex+1=linex; linex+1=); 程序:#include using namespace std; const int MAX = 100; /p用来记录矩阵的行列,main函数中有说明 /mij用来记录第i个矩阵至第j个矩阵的最优解 /s用来记录从哪里断开的才可得到该最优解 int pMAX+1,mMAXMAX,sMAXMAX; char lineMAX; int n;/矩阵个数 int ijMAX2;/存放每次调用时,i,j的值 void insert(int i,int j,int m)/插入括号 int x=m; for(;x=i;x-) linex+1=linex; linex+1=(; x=m+1; j+; for(;xj;x-) linex+1=linex; linex+1=); void matrixChain() for(int i=1;i=n;i+)mii=0; for(int r=2;r=n;r+)/对角线循环 for(int i=1;i=n-r+1;i+)/行循环 int j = i+r-1;/列的控制 /找mij的最小值,先初始化一下,令k=i mij=mi+1j+pi-1*pi*pj; sij=i; /k从i+1到j-1循环找mij的最小值 for(int k = i+1;kj;k+) int t=mik+mk+1j+pi-1*pk*pj; if(tmij) mij=t; /s用来记录在子序列i-j段中,在k位置处 /断开能得到最优解 sij=k; /根据s记录的各个子段的最优解,将其输出 void traceback(int i,int j) static int a=0; int x=0; int y=0; if(i=j)return ; traceback(i,sij); traceback(sij+1,j); for(int p=0;pa;p+) for(int q=0;qijpq)x+; if(jijpq)y+; insert(i+x,j+y,n);ija0=i;ija1=j;a+;n=n+2;/数组每次增加2/即增加了左右括号 int main() coutn; int k=n; for(int i=1;i=n;i+)linei=A+i-1; cout第一个矩阵行数和以后矩阵列数:; for(i=0;ipi; matrixChain(); traceback(
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 职业道德模范课件
- 电力安全工作规程线路变电配电部分知识试卷
- 铁路客运必知必会站务综合安全管理知识试卷
- 给媳妇的保证书范本
- 职业道德与法治中职课件教学
- 职业道德与法律第二课件
- 高空作业坐板及吊绳维护保养措施
- 人教版三年级数学课时教学计划
- 三年级部编版语文下册第八单元课程计划
- 沥青混凝土路面寿命缩短质量通病及预防措施
- 2025年拍卖师资格(纸笔作答)高频题库新版
- 【高考模拟】山东省春季高考研究联合体2024-2025学年高三上学期第一次联合考试数学试题(含解析)
- 体育社会学(高教版)第十章《社会体育的社会学分析》
- 2024年河北唐山国控港口管理有限公司招聘笔试真题
- 2025新七年级语文下册期末字音字形专题复习课件
- 妊娠合并贫血护理课件
- 左美马嗪行业深度研究分析报告(2024-2030版)
- 旅游景区船舶管理制度
- 脑机接口硬件优化-洞察及研究
- 2025年山东省中考数学试卷真题及答案详解(精校打印)
- 2025至2030年中国有源相控阵雷达行业市场发展态势及前景战略研判报告
评论
0/150
提交评论