Trong bài toán này, chúng ta được cung cấp một chuỗi (mảng) số liệu. nhiệm vụ của chúng tôi là tạo chương trình C cho phép nhân chuỗi Ma trận . Chúng ta cần tìm cách nhân các ma trận này sao cho có số phép nhân tối thiểu.
Mảng ma trận sẽ chứa n phần tử, xác định kích thước của ma trận là arr [i-1] X arr [i] .
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
array[] = {3, 4, 5, 6} Đầu ra
Giải thích
các ma trận sẽ có thứ tự -
Mat1 = 3X4, Mat2 = 4X5, Mat3 = 5X6
Đối với ba ma trận này, có thể có hai cách để nhân,
mat1*(mat2*mat3) -> (3*4*6) + (4*5*6) = 72 + 120 = 192 (mat1*mat2)*mat3 -> (3*4*5) + (3*5*6) = 60 + 90 = 150
Số lượng đa dạng tối thiểu sẽ là 150 trong trường hợp (mat1 * mat2) * mat3.
Vấn đề có thể được giải quyết bằng cách sử dụng lập trình động vì nó có cả hai thuộc tính tức là cấu trúc con tối ưu và cấu trúc con chồng chéo trong lập trình động.
Vì vậy, đây là Chương trình C cho phép nhân chuỗi ma trận sử dụng lập trình động
Ví dụ
#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;
} Đầu ra
Minimum number of multiplications required for the matrices multiplication is 444