matrix.cpp

给定n个矩阵{A1,A2,…,An}

#include  <iostream>
#include <stdio.h>

using namespace std;

//////////////////////////////////////////////////////////////////////////////

//MatrixChain计算m[i][j]所需的最少数乘次数

//并记录断开位置s[i][j]

//////////////////////////////////////////////////////////////////////////////

void MatrixChain(int *p,int n,int **m,int **s)

{

     for(int i=0;i<n;i++)

         m[i][i]=0;//单个矩阵相乘，所需数乘次数为

     for(int r=1;r<n;r++)

     {

         for(int i=0;i<n-r;i++)

         {

              int j=i+r;

              //首先在i断开，即（Ai*（Ai+1...Aj））

              m[i][j]=m[i][i]+m[i+1][j]+p[i]*p[i+1]*p[j+1];

              s[i][j]=i;

              for(int k=i+1;k<j;k++)

              {

                   //然后在k（从i+1开始遍历到j-1）断开，即（（Ai...Ak)*（Ak+1...Aj））

                   int t=m[i][k]+m[k+1][j]+p[i]*p[k+1]*p[j+1];

                   if(t<m[i][j])//找到更好的断开方法

                   {

                       m[i][j]=t;//记录最少数乘次数

                       s[i][j]=k;//记录断开位置

                   }

              }

         }

     }

    

  
}


void result(int i,int j,int **s)

{ 

   if (i == j) 
   {
     cout<<"A"<<i;
     return;
   }
   else if (i < j) 
   {
     cout<<"(";
     result(i,s[i][j],s);
     result(s[i][j]+1,j,s);
     cout<<")";
   }

  return;
}

void Traceback(int i,int j,int **s)

{ 

    //s[i][j]记录了断开的位置，即计算A[i:j]的加括号方式为：

     //(A[i:s[i][j]])*(A[s[i][j]+1:j])

     if(i==j)return;

     Traceback(i,s[i][j],s);//递归打印A[i:s[i][j]]的加括号方式

     Traceback(s[i][j]+1,j,s);//递归打印A[s[i][j]+1:j]的加括号方式

 

     //能走到这里说明i等于s[i][j]，s[i][j]+1等于j

     //也就是说这里其实只剩下两个矩阵，不必再分了

     cout<<"A"<<i<<"和A"<<(s[i][j]+1)<<"相乘"<<endl;  
	

return;
}


 

int main(int argc, char * argv[])

{

     int n,i;//矩阵的个数
	 cout<<"请输入矩阵的个数:"<<endl;

	 scanf("%d",&n);
	 cout<<"请按顺序输入所有矩阵的行数和最后一个矩阵的列数,以空格为间隔，如：30 20 10 "<<endl;

     int *p=new int[n+1];

     //p[0]:第一个矩阵的行数

     //p[1]:第一个矩阵的列数，第二个矩阵的行数

     //p[2]:第二个矩阵的列数，第三个矩阵的行数

	
	 for(i=0;i!=n+1;i++)
	 {
		 scanf("%d",&p[i]);
	 }
     

     int **m,**s;

     m=new int*[n];

     for( i=0;i<n;i++)
         m[i]=new int[n];
 
     s=new int*[n];

     for(i=0;i<n;i++)

         s[i]=new int[n];   

     cout<<endl<<"最佳矩阵连乘顺序为："<<endl;

     MatrixChain(p,n,m,s);
     Traceback(0,n-1,s);
	 cout<<endl<<"即：";
	 result(0,n-1,s);
	 cout<<endl;

     for(i=0;i<n;i++)   
	 {   
		delete []m[i];
		m[i]=NULL; 
		delete []s[i];
		s[i]=NULL; 
	 }   
		delete []m;   
        m=NULL;  
		delete []s;   
		s = NULL; 
		delete []p;   
		p = NULL;  
        return 0;

}