fork(2) download
copy 
  1. // See the Cormen book for details of the following algorithm
  2. #include<stdio.h>
  3. #include<limits.h>
  4.  
  5. // Matrix Ai has dimension p[i-1] x p[i] for i = 1..n
  6. int MatrixChainOrder(int p[], int n)
  7. {
  8.  
  9.     /* For simplicity of the program, one extra row and one extra column are
  10.        allocated in m[][].  0th row and 0th column of m[][] are not used */
  11.     int m[n][n];
  12.  
  13.     int i, j, k, L, q;
  14.  
  15.     /* m[i,j] = Minimum number of scalar multiplications needed to compute
  16.        the matrix A[i]A[i+1]...A[j] = A[i..j] where dimention of A[i] is
  17.        p[i-1] x p[i] */
  18.  
  19.     // cost is zero when multiplying one matrix.
  20.     for (i = 1; i < n; i++)
  21.         m[i][i] = 0;
  22.  
  23.     // L is chain length.  
  24.     for (L=2; L<n; L++)   
  25.     {
  26.         for (i=1; i<=n-L+1; i++)
  27.         {
  28.             j = i+L-1;
  29.             m[i][j] = INT_MAX;
  30.             for (k=i; k<=j-1; k++)
  31.             {
  32.                 // q = cost/scalar multiplications
  33.                 q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
  34.                 if (q < m[i][j])
  35.                     m[i][j] = q;
  36.             }
  37.         }
  38.     }
  39.  
  40.     return m[1][n-1];
  41. }
  42.  
  43. int main()
  44. {
  45.     int arr[] = {1, 2, 3, 4};
  46.     int size = sizeof(arr)/sizeof(arr[0]);
  47.  
  48.     printf("Minimum number of multiplications is %d ",
  49.                        MatrixChainOrder(arr, size));
  50.  
  51.     getchar();
  52.     return 0;
  53. }
Success #stdin #stdout 0s 2116KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Minimum number of multiplications is 18
https://ideone.com/5ezfkL
language:
C (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!