矩阵连乘问题.txt

1.能实现不同的个数的矩阵连乘. 2.最后矩阵大小是8X8. 3是最优的矩阵相乘. 描 述：给定n 个矩阵｛A1, A2,...,An｝

/*----------------------------文件头--------------------------

问 题：矩阵连乘问题

描 述：给定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