《矩阵连乘问题《算法分析与设计》》由会员分享，可在线阅读，更多相关《矩阵连乘问题《算法分析与设计》（5页珍藏版）》请在金锄头文库上搜索。
1、本文格式为Word版，下载可任意编辑矩阵连乘问题算法分析与设计 设计性测验报告 课程名称： 测验题目： 组 长： 成 员 一： 成 员 二： 成 员 三： 系 别： 专业班级： 指导教师： 测验日期： 算法分析与设计 矩阵连乘问题 数学与计算机科学系 一、测验目的和要求 测验目的 熟谙动态规划算法设计思想和设计步骤，掌管根本的程序设计方法，培养学生用计算机解决实际问题的才能。 测验要求 1、根据测验内容，专心编写源程序代码、上机调试程序，书写测验报告。 2、本测验工程考察学生对教材中核心学识的掌管程度和解决实际问题的才能。 3、测验工程可以采用集中与分散测验相结合的方式举行，学生利用平日测验课
2、时间和课外时间举行测验，要求在学期末形成完整的工程程序设计报告。 二、测验内容提要 矩阵连乘问题 给定n个矩阵A1,A2,An， 其中，Ai与Ai+1是可乘的，i=1,2，n-1。测验这n 个矩阵的连乘积A1,A2,An。由于矩阵乘法得志结合律，故计算矩阵的连乘积可以有大量不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，那么可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为： （1）单个矩阵是完全加括号的； （2）矩阵连乘积A是完全加括号的，那么A可表示为2个完全加括号的矩阵连
3、乘积B和C的乘积并加括号，即A=（BC）。 三、测验步骤 下面考虑矩阵连乘积的最优计算次序问题的动态规划方法。 （1）分析最优解的布局（最优子布局性质） 设计求解概括问题的动态规划算法的第一步是刻画该问题的最优解布局特征。对于矩阵乘积的最优计算次序问题也不例外。首先，为便当起见，降矩阵乘积Ai Ai+1Aj简记为Ai:j。测验计算A1：n的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，1 #define N 100/定义最大连乘的矩阵个数为100个 void matrixChain (int p,int mN+1N+1,int sN+1N+1)/*用mij二维数组来存储Ai
4、*.Aj的最小数乘次数，用sij来存储使Ai.Aj获得最小数乘次数对应的断开位置k，需要留神的是此处的N+1分外关键，虽然只用到的行列下标只从1到N但是下标0对应的元素默认也属于该数组，所以数组的长度就理应为N+1*/ int n=N;/定义m,s数组的都是n*n的，不用行列下标为0的元素，但包括在该数组中 for (int i=1;i=n;i+) mii=0; /*将矩阵m的对角线位置上元素全部置0，此时应是r=1的处境，表示先计 算第一层对角线上个元素的值*/ for (int r=2;r=n;r+)/r表示斜对角线的层数，从2取到n - 3 - for (int i=1;i=n-r+1;
5、i+)/i表示计算第r层斜对角线上第i行元素的值 int j=i+r-1;/j表示当斜对角线层数为r，行下标为i时的列下标 mij=mi+1j+pi-1*pi*pj;/计算当断开位置为i时对应的数乘次数 sij=i;/断开位置为i for (int k=i+1;kj;k+) int t=mik+mk+1j+pi-1*pk*pj;/*计算当断开位置k为从i到j（不包if (tmij) mij=t;/将Ai*.Aj的最小数乘次数存入mij sij=k;/将对应的断开位置k存入sij 括i和j）的全体取值对应的(Ai*.*Ak)*(Ak+1*.Aj)的数乘次数*/ void traceback (i
6、nt i,int j,int sN+1)/用递归来实现输出得到最小数乘次数的表达式 void main () 连乘*/ int mN+1N+1;/ 用mij二维数组来存储Ai*.Aj的最小数乘次数 int sN+1N+1;/ 用sij来存储使Ai.Aj获得最小数乘次数对应的断开位置k - 4 - int n;/用来存储矩阵的个数 int q2*N;/*用q数组来存储最原始的输入（各矩阵的行和列），主要目的是为了检验这Nint pN+1,flag=1;/*用pi-1,pi数组来存储A的阶数，flag用来判断这N个矩阵是否得志if (i=j) else printf ( traceback (i,sij,s); traceback(sij+1,j,s); printf ( printf ( 个矩阵是否得志连乘的条件*/ 5
