马航飞-5.5.txt

这是很不错的计算机算法

#include <stdio.h>
#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())
		   {
	      	cout<<"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;
	  fin.close();
	  out.close();
	  delete []p;
      for(i=1;i<n+1;i++)
		  delete []m[i]; 
      delete []m;
	  return 0;
	   }