ম্যাট্রিক্স চেইন গুণনের জন্য সি প্রোগ্রাম

এই সমস্যায়, আমাদের মেট্রিক্সের একটি ক্রম (অ্যারে) দেওয়া হয়েছে। আমাদের কাজ হল একটি ম্যাট্রিক্স চেইন গুণনের জন্য C প্রোগ্রাম তৈরি করা . আমাদের এই ম্যাট্রিক্সগুলিকে গুণ করার একটি উপায় খুঁজে বের করতে হবে যাতে, গুণের ন্যূনতম সংখ্যা প্রয়োজন৷

ম্যাট্রিক্সের অ্যারেতে n উপাদান থাকবে, যা ম্যাট্রিক্সের মাত্রাগুলিকে arr[i-1] X arr[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