Question

谁知道用C程序写个 矩阵连乘的算法，

最好能用递归的方法

Answer 1

这里我们用两种方式做一比较：
假设原来相乘的3个矩阵为如下方式（为了区别，特选择大写和小写两种表示方式）：
A*B B*C C*D
前两个先乘：
A*B B*C
a*b*c次乘法
a*(b-1)*c次加法
结果为A*C，然后再与C*D相乘：
A*C C*D
a*c*d次乘法
a*(c-1)*d次加法
共a*b*c+a*c*d=a*c*(b+d)次乘法
共a*(b-1)*c+a*(c-1)*d=a*c*(b+d)-a*(c+d)次加法
实际上：乘法的执行时间远远大于加法的执行时间，故略去加法时间不计。

如果换一种方式：
A*B B*C C*D
先后两者相乘：
B*C C*D = B*D
乘法：b*c*d
再与前者相乘：
A*B B*D
乘法：a*b*d
共(a+c)*b*d次乘法
这里只需要比较
a*c*(b+d)和(a+c)*b*d谁大谁小的问题
当 a*c*(b+d)>(a+c)*b*d 时说明前者更浪费机时，反之便是后者更浪费机时。
因此3个矩阵相乘时的选择策略函数就是比较他们的阶数关系。

对于A1=35*40 A2=40*20 A3=20*10
因为
a = 35, b = 40, c = 20, d = 10
a*c*(b+d) = 35*20*(40+10) = 35000
(a+c)*b*d = (35+20)*40*10 = 22000
前者大于后者，说明选择先将前两个相乘不如选择先将后两个相乘节省机时。