Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<stdio.h>
- #include<stdlib.h>
- #include<limits.h>
- void input();
- int Matrix_Chain_Order(int [],int);
- void Print_Optimal_Parents(int [100][100], int, int);
- int i,j,k,l,n,q,val,length,numofmatrix,firstValue,count=1;
- int mat[100], m[100][100],s[100][100],p[100];
- void input()
- {
- printf("Number of matrix:");
- scanf("%d", &numofmatrix);
- int index = 0;
- for(i=1; i<=(numofmatrix*2); i=i+2)
- {
- printf("MATRIX A%d\n", count++);
- printf("number of row:");
- scanf("%d",&mat[i]);
- printf("number of column:");
- scanf("%d", &mat[i+1]);
- }
- firstValue = mat[1];
- for(i=2; i<=(numofmatrix*2); i=i+2)
- {
- index = index+1;
- p[index] = mat[i];
- }
- p[0] = firstValue;
- length = index;
- printf("\nElements in P array: ");
- for(i=0; i<=length; i++)
- {
- printf("%d ", p[i]);
- }
- }
- int Matrix_Chain_Order(int p[], int length)
- {
- n = length;
- for (i=1; i<=n; i++)
- {
- m[i][i] = 0;
- }
- for (l=2; l<=n+1; l++)
- {
- for (i=1; i<=n-l+1; i++)
- {
- j = i+l-1;
- m[i][j] = 1000000;
- 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;
- }
- }
- }
- }
- return m[i][j];
- }
- void Print_Optimal_Parents(int s[100][100],int i, int j)
- {
- if(i==j)
- {
- printf(" A%d",i);
- }
- else
- {
- printf("( ");
- Print_Optimal_Parents(s,i,s[i][j]);
- Print_Optimal_Parents(s,s[i][j]+1,j);
- printf(" )");
- }
- }
- int main()
- {
- input();
- val = Matrix_Chain_Order(p,length);
- printf("\n\nCost: %d", val);
- printf("\n\nOptimal Path:\n ");
- Print_Optimal_Parents(s,1,length);
- printf("\n");
- return 0;
- }
Add Comment
Please, Sign In to add comment