यह एक C++ प्रोग्राम है जो डायनामिक प्रोग्रामिंग का उपयोग करके इष्टतम पैरेंथेसाइज़ेशन (Optimal Parenthesization) करता है।
एल्गोरिदम
Begin लंबाई n और मैट्रिक्स के डायमेंशन को इनपुट के रूप में लें। MatrixChain() न्यूनतम मल्टीप्लिकेशन खोजने के लिए: Arguments: a[i][j]=न्यूनतम स्केलर मल्टीप्लिकेशन की संख्या जो मैट्रिक्स A[i]A[i+1]...A[j] = A[i..j] की गणना के लिए आवश्यक है जहां A[i] का डायमेंशन p[i-1] x p[i] है। a[i][j] का अर्थ है लागत शून्य जब एक मैट्रिक्स को मल्टीप्लाई किया जाता है। L चेन की लंबाई है। m = लागत / स्केलर मल्टीप्लिकेशन। फंक्शन का बॉडी: i = 1 से n-1 तक a[i][i] = 0 इनिशियलाइज़ करें L = 2 से n-1 तक i = 1 से n - L + 1 तक j = i + L - 1 a[i][j] = INT_MAX k = i से j - 1 तक m = a[i][k] + a[k + 1][j] + p[i - 1] * p[k] * p[j]; if (m < a[i][j]) a[i][j] = m b[i][j] = k return a[1][n - 1] End
उदाहरण
#include<limits.h> #include<iostream> using namespace std; int MatrixChain(int p[], int n) { int a[n][n]; int b[n][n]; int i, j, k, L, m; for (i = 1; i < n; i++) a[i][i] = 0; for (L = 2; L < n; L++) { for (i = 1; i <= n - L + 1; i++) { j = i + L - 1; a[i][j] = INT_MAX; for (k = i; k <= j - 1; k++) { m = a[i][k] + a[k + 1][j] + p[i - 1] * p[k] * p[j]; if (m < a[i][j]) { a[i][j] = m; b[i][j] = k; } } } } return a[1][n - 1]; } int main() { cout << "Enter the length:"; int n; cin >> n; int a[n]; cout << "Enter the dimensions: "; for (int v = 0; v < n; ++v) { cin >> a[v]; } cout << "Minimum number of multiplications is: " << MatrixChain(a,n); return 0; }
आउटपुट
Enter the length:5 Enter the dimensions: 2 3 7 6 4 Minimum number of multiplications is: 174
