矩阵连乘问题实验报告
一、 问题描述
给定n 个矩阵{A1,A2,…An}，其中Ai与Ai+1是可乘的，i=1，2…，n-1。考察这n个矩阵
的连乘积A1A2…An。矩阵A 和B 可乘的条件是矩阵A的列数等于矩阵B 的行数。若A 是一
个p�q矩阵，B是一个q�r矩阵，则其乘积C=AB是一个p�r矩阵,需要pqr 次数乘。
由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。例如，设
3 个矩阵{A1,A2,A3}的维数分别为10�100，100�5，和5�50。若按加括号方式((A1A2)A3)
计算，3 个矩阵连乘积需要的数乘次数为10�100�5+10�5�50 = 7500。若按加括号方式
(A1(A2A3))计算，3 个矩阵连乘积总共需要10�5�50+10�100 �50 = 75000 次数乘。由此可
见，在计算矩阵连乘积时，加括号方式，即计算次序对计算量有很大影响。
矩阵连乘积的最优计算次序问题，即对于给定的相继n 个矩阵{A1A2…An}(其中矩阵Ai
的维数为pi-1*pi，i=1，2，…，n)，确定计算矩阵连乘积A1A2…An的计算次序，使得依此
次序计算矩阵连乘积需要的数乘次数最少。
二、 编程任务
对于给定的相继n个矩阵{A1,A2,…An}及其维数，编程计算矩阵连乘积A1A2…A3需要的
最少数乘次数。
三、基本算法及运行环境
本算法的实现源代码见文本文档。
运行环境为VC++6.0，使用控制台程序即可。
四、 测试情况
数据输入：由文件input.txt 给出输入数据。第1 行是给定的正整数n，表示有n 个矩阵
连乘。第2行是n+1个正整数p0,p1,…pn,表示矩阵Ai的维数为pi-1*pi ，i=1，2，…，n。
结果输出：将计算出的最少数乘次数输出到文件output.txt,并在屏幕上显示出来。
输入文件示例：input.exe
3
10 100 5 50
输出文件示例：output.exe
7500
