matrixchain.cpp

用动态规划法 对连乘矩阵求解最少相乘次数 并求出解

#include <iostream.h>

void Traceback(int i,int j,int **s)
{
	if(i == j)
	{
		cout<<"A"<<i;
	}
	else if(i+1 == j)
	{
		cout<<"(A"<<i<<"A"<<j<<")";
	}
    else
	{
		cout<<"(";
        Traceback(i,s[i][j],s);
        Traceback(s[i][j]+1,j,s);
        cout<<")";
	}
}


void matrixChain(int *p, int **m, int **s,int n)
{
      int j;
      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++) 
         {   
			 j=i+r-1;
             m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j];
             s[i][j] = i;
             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;
                     s[i][j] = k;    
				 }
             }

		 }
		 
          		     cout<<m[1][6]<<"="<<m[1][3]<<"+"<<m[4][6]
		     <<"+"<<p[0]<<"*"<<p[1]<<"*"<<p[6]<<endl;
         
}
void main()
{
	int r[6],c[6],p[7];
	int **m=new int *[7];
	for(int k=1;k<=6;k++)
		m[k]=new int[7];
	int **s=new int *[7];
	for(int j=1;j<=6;j++)
		s[j]=new int[7];

	for(int i=0;i<6;i++)
	{
		cout<<"请输入矩阵A"<<i+1<<"的行列数：";
		cin>>r[i]>>c[i];
		cout<<endl;
	}
    p[0]=r[0];
	for(int l=1;l<7;l++)
	{
		p[l]=c[l-1];
	}
	matrixChain(p,m,s,6);
  
    Traceback(1,6,s);

}