C Program For Chain Matrix Multiplication

#include< stdio.h>
#include< conio.h>
void MatrixChain(long*,long);

void pop(long[10][10],long,long);
long s[10][10],m[10][10];


void main()
{
 long *p,n,i,j,str,end;
 clrscr();
 printf("\n Enter number of element for p Matrix:");
 scanf("%ld",&n);
 printf("\n Enter dimension for P matrix:");

 for(i=0;i< =n;i++)
 {
  scanf("%ld",&p[i]);
 }
 MatrixChain(p,n+1);
 printf("\n-------------------------------------------");
 printf("\nEnter starting and Ending matrix:");
 scanf("%ld %ld",&str,&end);
 printf("\n-------------------------------------------");
 printf("\n Parenthesization order for Matrix Chained Multiplication(MCM) is:");
 printf("\n-------------------------------------------\n");
 pop(s,str,end);
 printf("\n-------------------------------------------");

getch();
}

void MatrixChain(long p[10],long len)
{
 long n,i,j,l,q,k;
 n=len-1;

 for(i=0;i< =n;i++)
  for(j=0;j< n;j++)
   m[i][j]=-1;
 for(i=0;i< =n;i++)
  for(j=0;j< =n;j++)
   s[i][j]=-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]=32767;

   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("\n--------------------M matrix--------------------");


 for(i=1;i< =n;i++)
 {
  printf("\n");
  for(j=1;j< =n;j++)
   printf("%7d",m[i][j]);

 }
  printf("\n--------------------S matrix--------------------");

 for(i=1;i< =n;i++)
 {
  printf("\n");
  for(j=1;j< =n;j++)
   printf("%7d",s[i][j]);

 }
}

void pop(long s[10][10],long i,long j)
{

 if(i==j)
  printf("A%d",i);
 else
 {
  printf("(");
  pop(s,i,s[i][j]);
  pop(s,s[i][j]+1,j);
  printf(")");
 }

}


OUTPUT



Enter number of element for p Matrix:6

 Enter dimension for P matrix:30 3 15 5 10 20 8

--------------------M matrix--------------------
      0   1350    675   1275   2775   2175
     -1      0    225    375    975   1455
     -1     -1      0    750   2500   2400
     -1     -1     -1      0   1000   1800
     -1     -1     -1     -1      0   1600
     -1     -1     -1     -1     -1      0
--------------------S matrix--------------------
     -1      1      1      1      1      1
     -1     -1      2      3      4      5
     -1     -1     -1      3      3      3
     -1     -1     -1     -1      4      5
     -1     -1     -1     -1     -1      5
     -1     -1     -1     -1     -1     -1
-------------------------------------------
Enter starting and Ending matrix:1 6

-------------------------------------------
 Parenthesization order for Matrix Chained Multiplication(MCM) is:
-------------------------------------------
(A1((((A2A3)A4)A5)A6))
-------------------------------------------