矩阵连乘方案.txt

算法设计与分析源代码算法设计与分析源代码

#include<iostream> 
#include<string> 
using namespace std; 
int w[31][2],way[31][31],trace[31][31],q=1; 
char *trail(int a,int b) 
{ 
  char *ch=new char [70]; 
  if(a==b) 
  { 
    sprintf(ch,"A%d",q++); 
    return ch; 
  } 
  else 
  { 
    int y=trace[a][b]; 
    char *o=trail(a,y); 
    char *o1=trail(y+1,b); 
    sprintf(ch,"(%s*%s)",o,o1); 
    delete[]o; 
    delete []o1; 
    return ch; 
  } 
} 
void main() 
{ 
  int n,ci,j,t,tem,poi; 
  cin>>n;//输入矩阵个数// 
  for(int i=1;i<=n;i++) 
  { 
  cin>>w[i][0];//用以纪录第i个矩阵的行数// 
  cin>>w[i][1];//纪录列数// 
  way[i][i]=0; 
  } 
  for(ci=2;ci<=n;ci++) 
  { 
  for(i=1;i<=n-ci+1;i++) 
  { t=100000000; 
  poi=i; 
  for(j=i;j<=i+ci-2;j++) 
  { 
  tem=way[i][j]+way[j+1][i+ci-1]+w[i][0]*w[j][1]*w[i+ci-1][1]; 
  if(tem<t) 
  {
   t=tem; 
   poi=j; 
  } 
 } 
 way[i][i+ci-1]=t;//动态规划部分，way[i][j]用来记录第i到j个矩阵的最小相乘数 
 trace[i][i+ci-1]=poi;//纪录路径 
 } 
 } 
 cout<<way[1][n]<<endl; 
 string s=trail(1,n); 
 if(s[0]=='(') 
 { 
 int r=s.size(); 
 s.erase(r-1,1); 
 r=0; 
 s.erase(r,1); 
 } 
 cout<<s<<endl; 
}