MATRIX CHAIN MULTIPLICATION
#include<iostream.h>
#include<conio.h>
long int m[50][50],p[50],s[50][50] ;
void display(long int s[50][50],int i,int j);
void matrixchain(int);
void matrixchain(int n)
{
long int i,j,k,l,q;
for(i=1;i<=n;i++)
{
for(i=1;i<=n-1;i++)
{
j=i+l-1;
m[i][j]=20000;
for(k=i;k<j;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;
s[i][j]=k;
}
}
}
}
}
void display(long int s[50][50],int i,int j)
{
if(i==j)
cout<<"A"<<"";
else
{
cout<<"(";
display(s,i,s[i][j]) ;
display(s,s[i][j]+1,j);
cout<<")";
}
}
void main()
{
clrscr();
long int n,i,j;
clrscr();
cout<<"enter the no. of matrices";
cin>>n;
cout<<"enter the order array";
for(i=0;i<=n;i++)
{
cin>>p[i];
}
matrixchain(n);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cout<<m[i][j]<<"";
}
cout<<"\n" ;
}
cout<<"\n";
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cout<<s[i][j] <<"";
}
cout<<"\n" ;
}
display(s,1,n);
getch();
}
Comments
Post a Comment