矩阵连乘问题(动态规划)_第1页
矩阵连乘问题(动态规划)_第2页
矩阵连乘问题(动态规划)_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

矩阵连乘问题（动态规划）一、 实验目的与要求1、明确矩阵连乘的概念。2、利用动态规划解决矩阵连乘问题。二、实验题：问题描述：给定n个矩阵A1,A2,.,An，其中Ai与Ai+1是可乘的，i=1，2.，n-1。确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。输入数据为矩阵个数和每个矩阵规模，输出结果为计算矩阵连乘积的计算次序和最少数乘次数。三、实验代码#includeusing namespace std;const int MAX = 100;/p用来记录矩阵的行列，main函数中有说明/mij用来记录第i个矩阵至第j个矩阵的最优解/s用来记录从哪里断开的才可得到该最优解int pMAX+1,mMAXMAX,sMAXMAX;int n;/矩阵个数int matrixChain()for(int i=0;i=n;i+)mii=0;for(int r=2;r=n;r+)/对角线循环for(int i=0;i=n-r;i+)/行循环int j = r+i-1;/列的控制/找mij的最小值，先初始化一下，令k=imij=mi+1j+pi+1*pi*pj +1;sij=i;/k从i+1到j-1循环找mij的最小值for(int k = i+1;kj;k+)int temp=mik+mk+1j+pi*pk+1*pj+1;if(tempmij)mij=temp;/s用来记录在子序列i-j段中，在k位置处/断开能得到最优解sij=k;return m0n-1;/最终结果/根据s记录的各个子段的最优解，将其输出void traceback(int i,int j)if(i=j)coutAi;return ;if(isij)cout(;traceback(i,sij);if(isij)cout);if(sij+1j)cout(;traceback(sij+1,j);if(sij+1j)cout);void traceback()cout(;traceback(0,n-1);cout);coutendl;int main()cout请输入矩阵的个数：n;cout输入矩阵（形如a*b,中间用空格隔开）:endl;for(int i=0;ipi;/测试数据可以设为六个矩阵分别为/A130*35,A235*15,A315*5,A45*10,A510*20,A620*25/则p0-6=30,35,15,5,10,20,25cout输出结果如下：endl;matrixChain(
人人文库> 全部分类> 行业资料 > 管理策划

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论