**fig10_46.txt** /* 1*/ // Compute optimal ordering of matrix multiplication. /* 2*/ // C contains number of columns for each of the N matrices. /* 3*/ // C[ 0 ] is the number of rows in matrix 1. /* 4*/ // Minimum number of multiplications is left in M[ 1 ][ n ]. /* 5*/ // Actual ordering can be computed via. /* 6*/ // Another procedure, using Last_Change. /* 7*/ // M and Last_Change are indexed starting at 1, instead of zero. /* 8*/ void /* 9*/ Opt_Matrix( long int C[ ], unsigned int N, /*10*/ Two_D_Array M, Two_D_Array Last_Change ) /*11*/ { /*12*/ long int i, k, Left, Right, This_M; /*13*/ for( Left = 1; Left <= N; Left++ ) /*14*/ M[ Left ][ Left ] = 0; /*15*/ for( k = 1; k < N; k++ ) // K is Right-Left. /*16*/ for( Left = 1; Left <= N-k; Left++ ) // For each position. /*17*/ { /*18*/ Right = Left + k; /*19*/ M[ Left ][ Right ] = Int_Max; /*20*/ for( i = Left; i < Right; i++ ) /*21*/ { /*22*/ This_M = M[ Left ][ i ] + M[ i+1 ][ Right ] /*23*/ + C[ Left-1 ] * C[ i ] * C[ Right ]; /*24*/ if( This_M < M[ Left ][ Right ] ) // Update min. /*25*/ { /*26*/ M[ Left ][ Right ] = This_M; /*27*/ Last_Change[ Left ][ Right ] = i; /*28*/ } /*29*/ } /*30*/ } /*31*/ }