算法实验之矩阵连乘-实验报告.doc

1、 攀枝花学院实验报告册课程名称 计算机算法设计与分析 院 系 数学与计算机学院 班 级 2012级信息与计算科学 姓 名 杨腾佼 学 号 201210802025 授课教师 鄢莉 教 务 处 制算法设计与分析实 验 报 告 （三）学号： 201210802025 姓名：杨腾佼 班级： 信本 成绩：实验名称：矩阵连乘问题实验地点：6a-2所使用的开发工具及环境：Visual c+6.0,windows 7一、 实验目的 熟悉掌握动态规划法设计技术二、实验要求1、按教材所授内容要求，完成“矩阵连乘问题”算法。得到一个完整正确的程序。2、问题规模：不少于203、输出最终结果。三、算法实现#inclu

2、de #include #define MAX_MATRIXNUM 100#define MAX_VALUE 32767Int pMAX_MATRIXNUM+1, mMAX_MATRIXNUM+1MAX_MATRIXNUM+1, sMAX_MATRIXNUM+1MAX_MATRIXNUM+1;static void matrix_chain(int num);static void traceback(int i, int j);int main(int argc, char *argv) int i, num; printf(Input matrix num: ); scanf(%d, &n

3、um); getchar(); printf(Input matrix subscript: ); for(i = 0; i = num; i+) scanf(%d, &pi); getchar(); matrix_chain(num); traceback(1, num); printf(n); return 0;static void matrix_chain(int num) int i, j, l, k, n, temp; n = num; for(i = 1; i = n; i+) mii = 0; for(l = 2; l = n; l+) for(i = 1; i = n-l+1

4、; i+) j = i + l - 1; mij = MAX_VALUE; for(k = i; k j; k+) temp= mik + mk+1j + pi-1*pk*pj; if(temp mij) mij = temp; sij = k; printf(The lowest compute times = %dn, m1num);static void traceback(int i, int j) if(i = j) printf(A%d, i); if(i j) printf(); traceback(i, sij); traceback(sij+1, j); printf(); 运行结果如下： 四、算法思想 矩阵乘法满足结合律，所以计算矩阵的连乘积可以有不同的计算次序，若一个矩阵的计算次序完全确定，那么矩阵连乘积可以递归地定义为：单个矩阵是完全加括号的；矩阵连乘积A是完全加括号的，则A可以表示成2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=（BC）五、实验结论 本次实验是动态规划的一个应用，矩阵连乘问题主要就是确定矩阵连乘的次序，使得矩阵连乘的次数最少。 指导教师签名： 2014 年 12 月 11 日