#include<stdio.h>
int p[10],m[10][10],s[10][10];
void matrix_chain_order(int n)
{
int i,j,k,l,q;
// n=p.length-1;
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;
//printf("%d\t%d\t%d\n",i,l,j);
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;
s[i][j]=k;
//printf("%d\t%d\t%d\t%d\n",i,j,k,m[i][j]);
}
}
}
}
for(i=0;i<n;i++)
{
for(j=n;j>i;j--)
{
printf("%d %d\t",m[i][j],s[i][j]);
}
printf("\n");
}
printf("\n\n\n");
}
void PRINT_OPTIMAL_PARENS(i,j)
{
if(i == j)
printf("A%d",i);
else
{
printf("(");
PRINT_OPTIMAL_PARENS(i,s[i][j]);
PRINT_OPTIMAL_PARENS(s[i][j]+1,j);
printf(")");
}
}
int main()
{
int i,n;
printf("enter no. of matrices");
scanf("%d",&n);
printf("enter sizes of matrix");
for(i=0;i<=n;i++)
scanf("%d",&p[i]);
matrix_chain_order(n);
PRINT_OPTIMAL_PARENS(1,6);
return 0;
}
int p[10],m[10][10],s[10][10];
void matrix_chain_order(int n)
{
int i,j,k,l,q;
// n=p.length-1;
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;
//printf("%d\t%d\t%d\n",i,l,j);
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;
s[i][j]=k;
//printf("%d\t%d\t%d\t%d\n",i,j,k,m[i][j]);
}
}
}
}
for(i=0;i<n;i++)
{
for(j=n;j>i;j--)
{
printf("%d %d\t",m[i][j],s[i][j]);
}
printf("\n");
}
printf("\n\n\n");
}
void PRINT_OPTIMAL_PARENS(i,j)
{
if(i == j)
printf("A%d",i);
else
{
printf("(");
PRINT_OPTIMAL_PARENS(i,s[i][j]);
PRINT_OPTIMAL_PARENS(s[i][j]+1,j);
printf(")");
}
}
int main()
{
int i,n;
printf("enter no. of matrices");
scanf("%d",&n);
printf("enter sizes of matrix");
for(i=0;i<=n;i++)
scanf("%d",&p[i]);
matrix_chain_order(n);
PRINT_OPTIMAL_PARENS(1,6);
return 0;
}
No comments:
Post a Comment