矩阵链乘法的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 小红书生日祝福语简短