ম্যাট্রিক্স চেইন গুন

যদি ম্যাট্রিক্সের একটি চেইন দেওয়া হয়, তাহলে গুণ করার জন্য আমাদের ম্যাট্রিক্সের সঠিক ক্রমটির ন্যূনতম সংখ্যা খুঁজে বের করতে হবে।

আমরা জানি যে ম্যাট্রিক্স গুণনটি সহযোগী, তাই চারটি ম্যাট্রিক্স ABCD, আমরা এই ক্রমগুলিতে A(BCD), (AB)(CD), (ABC)D, A(BC)D, গুণ করতে পারি। এই সিকোয়েন্সের মতো, আমাদের কাজ হল কোন ক্রমটি গুণ করার জন্য কার্যকর তা খুঁজে বের করা।

প্রদত্ত ইনপুটে একটি অ্যারে বলা আছে arr, যাতে রয়েছে arr[] ={1, 2, 3, 4}। এর মানে ম্যাট্রিক্সগুলি ক্রম অনুসারে (1 x 2), (2 x 3), (3 x 4)।

ইনপুট এবং আউটপুট

ইনপুট:ইনপুট ম্যাট্রিক্সের অর্ডার। {1, 2, 3, 4}। এর অর্থ হল ম্যাট্রিক্স হল{(1 x 2), (2 x 3), (3 x 4)}। আউটপুট:ন্যূনতম সংখ্যক অপারেশন এই তিনটি ম্যাট্রিক্সকে গুণ করতে হবে। এখানে ফলাফল 18।

অ্যালগরিদম

matOrder(অ্যারে, n)

ইনপুট - ম্যাট্রিক্সের তালিকা, তালিকায় ম্যাট্রিকের সংখ্যা।

আউটপুট - ম্যাট্রিক্স গুণের ন্যূনতম সংখ্যা।

n x n আকারের সারণি minMul সংজ্ঞায়িত করা শুরু করুন, প্রথমে দৈর্ঘ্যের জন্য সমস্ত 0s দিয়ে পূরণ করুন :=2 থেকে n, ডু fir i:=1 থেকে n-দৈর্ঘ্য, ডু j :=i + দৈর্ঘ্য – 1 minMul[i, j] :=∞ k :=i থেকে j-1 এর জন্য, q করুন :=minMul[i, k] + minMul[k+1, j] + array[i-1]*array[k]*array[j] যদি q

উদাহরণ

#includeনেমস্পেস ব্যবহার করে std;int matOrder(int array[], int n) { int minMul[n][n]; // (int i=1; i আউটপুট
 ম্যাট্রিক্স গুণের সর্বনিম্ন সংখ্যা:18