矩阵链乘法的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 虎年喝酒拜年祝福语简短
18 教师闺蜜祝福语简短