**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*/	}