void MatrixChain(int *p,int n,int **m,int **s)
{
for(int i=1i<=ni++)
m[i][i]=0
for(int r=2r<=nr++)
for( i=1i<=n-r+1i++)
{
int 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+1k<jk++)
{
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
}
}
}
}
void Traceback(int i,int j,int **s)
{
if(i==j)return
Traceback(i,s[i][j],s)
Traceback(s[i][j]+1,j,s)
cout<<"让 A"<<i//<<","<<s[i][j]
cout<<"和 A"<<(s[i][j]+1)<<"相乘"<<endl//<<","<<j<<"相乘"<<endl
}
void main()
{
int n,*p
int j=1
cout<<"请输入矩阵的个数"<<endl
cin>>n
p=new int[n+1]
cout<<"请输入第一个矩阵的行数，然后按回车键"<<endl
cin>>p[0]
cout<<"第"<<j<<"个矩阵是"<<endl
cout<<p[0]<<"*"
cin>>p[1]
// cout<<p[1]<<endl
cout<<endl
for(int i=2i<n+1i++)
{
cout<<"第"<<i<<"个矩阵是:"
cout<<p[i-1]<<"*"
cin>>p[i]
}
// int p[]={30,35,15,5,10,20,25}
// int m[6][6],s[6][6]
int **m,**s
m=new int*[n]
for( i=1i<=ni++)
m[i]=new int[n]
s=new int*[n]
for( i=1i<=ni++)
s[i]=new int[n]
MatrixChain(p,n,m,s)
Traceback(1,n,s)
}
这是矩阵连乘
这里我们用两种方式做一比较：假设原来相乘的3个矩阵为如下方式（为了区别，特选择大写和小写两种表示方式）：
A*B B*C C*D
前两个先乘：
A*B B*C
a*b*c次乘法
a*(b-1)*c次加法
结果为A*C，然后再与C*D相乘：
A*C C*D
a*c*d次乘法
a*(c-1)*d次加法
共a*b*c+a*c*d=a*c*(b+d)次乘法
共a*(b-1)*c+a*(c-1)*d=a*c*(b+d)-a*(c+d)次加法
实际上：乘法的执行时间远远大于加法的执行时间，故略去加法时间不计。
如果换一种方式：
A*B B*C C*D
先后两者相乘：
B*C C*D = B*D
乘法：b*c*d
再与前者相乘：
A*B B*D
乘法：a*b*d
共(a+c)*b*d次乘法
这里只需要比较
a*c*(b+d)和(a+c)*b*d谁大谁小的问题
当 a*c*(b+d)>(a+c)*b*d 时说明前者更浪费机时，反之便是后者更浪费机时。
因此3个矩阵相乘时的选择策略函数就是比较他们的阶数关系。
对于A1=35*40 A2=40*20 A3=20*10
因为
a = 35, b = 40, c = 20, d = 10
a*c*(b+d) = 35*20*(40+10) = 35000
(a+c)*b*d = (35+20)*40*10 = 22000
前者大于后者，说明选择先将前两个相乘不如选择先将后两个相乘节省机时。
#include "iostream.h"void MatrixChain(int *p,int n,int **m,int **s)
{
for(int i=1i<=ni++)
m[i][i]=0
for(int r=2r<=nr++)
for( i=1i<=n-r+1i++)
{
int 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+1k<jk++)
{
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
}
}
}
}
void Traceback(int i,int j,int **s)
{
if(i==j)return
Traceback(i,s[i][j],s)
Traceback(s[i][j]+1,j,s)
cout<<"让 A"<<i//<<","<<s[i][j]
cout<<"和 A"<<(s[i][j]+1)<<"相乘"<<endl//<<","<<j<<"相乘"<<endl
}
void main()
{
int n,*p
int j=1
cout<<"请输入矩阵的个数"<<endl
cin>>n
p=new int[n+1]
cout<<"请输入第一个矩阵的行数，然后按回车键"<<endl
cin>>p[0]
cout<<"第"<<j<<"个矩阵是"<<endl
cout<<p[0]<<"*"
cin>>p[1]
// cout<<p[1]<<endl
cout<<endl
for(int i=2i<n+1i++)
{
cout<<"第"<<i<<"个矩阵是:"
cout<<p[i-1]<<"*"
cin>>p[i]
}
// int p[]={30,35,15,5,10,20,25}
// int m[6][6],s[6][6]
int **m,**s
m=new int*[n]
for( i=1i<=ni++)
m[i]=new int[n]
s=new int*[n]
for( i=1i<=ni++)
s[i]=new int[n]
MatrixChain(p,n,m,s)
Traceback(1,n,s)
}
这是矩阵连乘
