给定n格矩阵的大小为B[0]xB[1],B[1]xB[2],...,B[n-1]xB[n]。找出使用最少的乘法来完成计算这n格矩阵乘积的方法。
例子:比如说3个矩阵(A,B,C)大小为8x4,4x1,1x5。我们有两种乘法:
(1) (AB)C: 需要用841 (AB) + 815 ((AB)C) = 72次乘法。
(2) A(BC): 需要用415 (BC) + 845 (A(BC)) = 180次乘法。
显然前者比较好。
写出下列函数来解决上述问题:
int minOpMatrixMult(int* sizes, int n):
前置条件:没有
输入:n为矩阵的数量,sizes[0]xsizes[1]为第0个矩阵的大小、sizes[1]xsizes[2]为第1个矩阵的大小、...、sizes[n-1]xsizes[n]为最后一个矩阵的大小。
功能:找出如何放置括号来把乘法使用次数降到最低,并打印出括号放置的方法(具体输出格式见下面)
输出:回传最小要用的乘法次数。
后置条件:没有
输出格式:第n个矩阵我们用n-1来表示。首先每一个矩阵用括号()包围,然后每两个要乘的矩阵就再用括号包围。最后换行。
例子:两个矩阵的话,我们的输出为:
((0)(1))
比如说上面的例子,sizes将会为{8,4,1,5},n为3。
我们输出的打印为:
(((0)(1))(2))
比如有三个矩阵,我们想先把后面两个乘了才乘前面的话,那输出的会是:
((0)((1)(2)))