matrix.cpp

确定计算矩阵连乘积的计算次序

#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>

void MatrixChain(int *p,int n,int **m)
	{
	  for(int i=1;i<=n;i++)  m[i][i]=0;
	  for(int r=2;r<=n;r++)
                     for(int i=1;i<=n-r+1;i++)
	         {
	            int j=i+r-1;
	            m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];
	            for(int k=i+1;k<j;k++)
		   {
		    int t =m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
		    if(t<m[i][j])
		    m[i][j]=t;
	              }
                   }
	  }
int main()
{
    int n,i;
    int *p,**m;
    ifstream fin("input.txt",ios::nocreate);
    if(fin.fail())
    {
        cerr<<"the input.txt is not exist!"<<endl;
        exit(-1);
   }
  ofstream out("output.txt");
  fin>>n;
  p=new int[n+1];
  if(!p) 
     {    cerr<<"insufficient memory!"<<endl;
          exit(-1); 
	     }
for(i=0;i<n+1;i++)
      fin>>p[i];
  m = new int * [n+1];
  if(!m)
  {
    cerr<<"insufficient memory!"<<endl;
   exit(-1); 
	  }
  for (i = 1;i <= n; i++) 
     {
       m[i] = new int[n+1]; 
       if(!m[i])
        {    
          cerr<<"insufficient memory!"<<endl;
   
         exit(-1);  
         }
	  }
MatrixChain(p,n,m);
   out<<m[1][n]<<endl;
   cout<<"最小数乘次数："<<m[1][n]<<endl;
  fin.close();
  out.close();
  delete []p;
  for(i=1;i<n+1;i++)
       delete []m[i]; 
  delete []m;
  return 0;
	   }