An array P is given of n+1 positive integers, p[0],..,p[n]. This array should be viewed as a representation of the orders of the n matrices. In particular, A1 is a matrix of order p[0] X p[1], and A2 is a matrix of order p[1] X p[2]. In general, for each i in the range 1 <= i < = n, the order of Ai is p[i-1] X p[i].
Write a program to find the minimum number of multiplication operations to compute the product A1 X A2 X … X An.
Input: First line contains n, the size of the array. Second line contains elements of p separated by spaces.
Output: Minimum number of multiplications to multiply the chain.
Write a program to find the minimum number of multiplication operations to compute the product A1 X A2 X … X An.
Input: First line contains n, the size of the array. Second line contains elements of p separated by spaces.
Output: Minimum number of multiplications to multiply the chain.
#include<stdio.h> #include<limits.h> #include<stdlib.h> int MatrixChainOrder(int p[],int n); int main() { int n,i; scanf("%d",&n); int *p = (int *)malloc(sizeof(int)*n); for(i=0;i<n;i++) scanf("%d",&p[i]); printf("%d",MatrixChainOrder(p, n)); return 0; }
nt MatrixChainOrder(int p[], int n)
{
int i,j,k,l,q,m[n][n];
for(i=1;i<=n;i++)
{
m[i][i]=0;
}
for(l=2;l<=n;l++)
{
for(i=1;i<=n-l+1;i++)
{
j=i+l-1;
m[i][j] = 99999;
for(k=i;k<=j-1;k++)
{
q=m[i][k] + m[k+1][j] + (p[i-1]*p[k]*p[j]);
if(q<m[i][j])
{
m[i][j]=q;
}
}
}
}
return m[1][n-1];
}
No comments:
Post a Comment