问 题：矩阵连乘问题
描 述：给定n 个矩阵｛A1, A2,...,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。
考察这n个矩阵的连乘积A1A2...An。矩阵A 和B 可乘的条件是矩阵A的列数
等于矩阵B 的行数。若A 是一个p x q矩阵，B是一个q * r矩阵，则其乘积C=AB
是一个p * r矩阵,需要pqr次数乘。
矩阵连乘积的最优计算次序问题，即对于给定的相继n 个矩阵{A1,A2,...,An}
(其中矩阵Ai的维数为 pi-1 * pi，i=1，2，…，n)，确定计算矩阵连乘积
A1A2...An 的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。 编程任务：对于给定的相继n个矩阵{A1, A2, ..., An }及其维数，编程计算矩阵连
乘积A1A2...An 需要的最少数乘次数。
数据输入：由文件input.txt 给出输入数据。第1 行是给定的正整数n，表示有n 个矩阵
连乘。第2行是n+1个正整数P0 , P1, ..., Pn ，表示矩阵Ai 的维数
为pi-1 * pi ，i=1，2，…，n。
结果输出：将计算出的最少数乘次数输出到文件output.txt。-------------------------------------------------------------------*/#include <iostream.h>
#include <fstream.h>
#include <stdio.h>
//--------------------- 变量、函数定义 开始 ------------------ofstream myoutf("output.txt"); //输出到文件,全局变量
/*----------------- MatrixChain函数定义 ----------------------
* 函 数 名: MatrixChain *
* 返回类型: void 无返回值 *
* 参数说明: p[] 矩阵的维数 *
* n 矩阵连乘的个数 *
* m 保存矩阵最少连乘个数的二维数组 *
* 功 能: 输出 n个矩阵连乘的最优值 *
* 调用示例: MatrixChain(p,n,m); *
*-----------------------------------------------------------*/void MatrixChain(int * p,int n,int * * m);//--------------------- 变量、函数定义 结束 ------------------//--------------------- 主函数 开始 --------------------------
void main()
{
int MatrixNum; //定义连乘的矩阵数
int i , j;
int * p;
int * * m; //保存最优值数组 ifstream myinf("input.txt",ios::nocreate); //读取文件
if (myinf.fail())
{
cerr << "读入文件时，出错！";
return; //如果没有输入文件，则返回错误
}//if (myinf.fail())
myinf >> MatrixNum; //读取矩阵个数
cout << MatrixNum << endl;
if (MatrixNum <= 0)
{
cerr << "矩阵连乘个数不合法，出错！";
return; //如果没有输入文件，则返回错误
}// if (MatrixNum > 0)
p = new int[MatrixNum + 1]; //分配矩阵维数数组空间
if (p == NULL)
{
cerr << "数组空间分配不成功，出错！";
return;
}// if (p != NULL)
for (i = 0;i < MatrixNum +1 ; i++)//读入矩阵维数
{
myinf >> p[i];
cout << p[i] << " ";
}//for i <= MatrixNum
cout << endl; //----------- 定义二维动态数组 开始 --------------
m = new int * [MatrixNum + 1]; //给一维数组动态分配内存
for (i=0 ; i < MatrixNum +1; i++)
{
m[i] = new int[MatrixNum +1];
}//for 分配二维数组空间 for (i=0 ; i < MatrixNum + 1;i++) //给数组初始化
for (j = 0; j < MatrixNum +1;j++)
{
m[i][j] = 0;
}//for
//----------- 定义二维动态数组 结束 --------------
MatrixChain(p,MatrixNum, m); //调用动态规划矩阵连乘算法 //--------释放数组---------
for(i=0;i < MatrixNum +1 ; i++) delete[] m[i]; delete[] m; //释放二维数组空间
delete[] p; //释放矩阵维数数组空间
myinf.close(); //关闭输入文件
myoutf.close(); //关闭输出文件
}//void main()//--------------------- 主函数 结束 --------------------------
/*----------------- move函数定义 ----------------------
函 数 名: MatrixChain
返回类型: void 无返回值
参数说明:
功 能:
调用示例: 编程思路: 1、分析最优的结构 将矩阵连乘积Ai,Ai+1,…,Aj简记为Ai…j。我们来看计算A1…n的一个最优次序。
设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，1 <= k < n，则完全加括号
方式为((A1…Ak)(Ak+1…An))。照此，我们要先计算A1…k和Ak+1…n，然后，
将所得的结果相乘才得到A1…n。显然其总计算量为计算A1…k的计算量加上
计算Ak+1…n的计算量，再加上A1…k与Ak+1…n相乘的计算量。 2、建立递归关系
对于矩阵连乘积的最优计算次序问题，设计算Ai…j ,1≤i≤j≤n，所需的最少数
乘次数为m[i,j]，原问题的最优值为m[1,n]。 当i=j时，Ai…j=Ai为单一矩阵，无需计算，因此m[i,i]=0，i=1,2,…,n ； 当i<j时，可利用最优子结构性质来计算m[i,j]。事实上，若计算Ai…j的最优次序
在Ak和Ak+1之间断开，i≤k<j，则：m[i,j]=m[i,k]+m[k+1,j]+pi-1*pk*pj 3、计算最优值
用动态规划算法解此问题，可依据递归式(2.1)以自底向上的方式进行计算，在计算
过程中，保存已解决的子问题答案，每个子问题只计算一次，而在后面需要时只要
简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法。下面所给出
的计算m[i,j]动态规划算法中，输入是序列P={p0,p1,…,pn}，输出除了最优值
m[i,j]外，还有使m[i,j] = m[i,k] + m[k+1,j] + pi-1*pk*pj达到最优的断开位置
k=s[i,j]，1≤i≤j≤n 。 总 结:
算法首先设定m[i][i]=0(i=1,2,...,n)。然后再根据递归式按矩阵链长
的递增方式依此计算出各个m[i][j]，在计算某个固定的m[i][j]时，
只用到已计算出的m[i][k]和m[k+1][j]。
-------------------------------------------------------------*/void MatrixChain(int * p,int n,int * * m)
{
for (int i =1; i <= n; i++) m[i][i] = 0;//当i=j时，m[i][j]=0
for (int r =2; r <= n; r++)
for (int i =1; i <= n-r+1; i++)
{
int j = i + r -1;
// 因为不知道k的位置，所以m[i][j]递归的看作
// m[i][i] + m[i+1][j] + p[i-1] * p[i] * p[j];
// 然后通过下面的循环，找到k的位置
m[i][j] = m[i+1][j] + p[i-1] * p[i] * p[j];
//s[i][j] = i;
//假设在k位置断开，然后计算最少乘数，
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;
}//if
//=================================================
}//for k
}//for i myoutf << m[1][n] << endl; //输出结果到文件}//void MatrixChain
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
#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;
}