矩阵链乘法的C程序
在这个问题中，我们得到了一个度量的序列（数组）。我们的任务是为矩阵链乘法创建一个C程序。我们需要找到一种方法来对这些矩阵进行乘法运算，以便需要最少的乘法运算次数。
矩阵数组将包含n个元素，这些元素将矩阵的维度定义为arr[i-1]Xarr[i]。
让我们举个例子来了解这个问题，
输入项
array[] = {3, 4, 5, 6}输出结果
说明
矩阵将为-
Mat1 = 3X4, Mat2 = 4X5, Mat3 = 5X6
对于这三个矩阵，可以通过两种方式相乘，
mat1*(mat2*mat3) -> (3*4*6) + (4*5*6) = 72 + 120 = 192 (mat1*mat2)*mat3 -> (3*4*5) + (3*5*6) = 60 + 90 = 150
在（mat1*mat2）*mat3的情况下，最小乘法数为150。
使用动态规划可以解决该问题，因为它具有动态规划中的最优子结构和重叠子结构这两个属性。
所以这是使用动态编程的矩阵链乘法的C程序
示例
#include <stdio.h>
int MatrixChainMultuplication(int arr[], int n) {
int minMul[n][n];
int j, q;
for (int i = 1; i < n; i++)
minMul[i][i] = 0;
for (int L = 2; L < n; L++) {
for (int i = 1; i < n - L + 1; i++) {
j = i + L - 1;
minMul[i][j] = 99999999;
for (int k = i; k <= j - 1; k++) {
q = minMul[i][k] + minMul[k + 1][j] + arr[i - 1] * arr[k] * arr[j];
if (q < minMul[i][j])
minMul[i][j] = q;
}
}
}
return minMul[1][n - 1];
}
int main(){
int arr[] = {3, 4, 5, 6, 7, 8};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Minimum number of multiplications required for the matrices multiplication is %d ", MatrixChainMultuplication(arr, size));
getchar();
return 0;
}输出结果
Minimum number of multiplications required for the matrices multiplication is 444
热门推荐
10 生日摆摊祝福语简短独特
11 父亲婚礼祝福语经典简短
12 姐妹生日祝福语女孩简短
13 学校生日祝福语简短独特
14 写春节祝福语简短的
15 精简祝福语简短小故事
16 节日祝福语简短中秋暧昧
17 升班祝福语简短10字
18 伴娘祝福语长文案简短