Search This Blog

Friday 7 October 2016

matrix chain multiplication using dynamic

#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;
}

No comments:

Post a Comment