林斌-5.5.txt

这是很不错的计算机算法

/*----------------------------文件头--------------------------------
  作者:林斌
  Email:[e-mail]
  作业名称：矩阵连乘问题
  
  问    题：矩阵连乘问题
  描    述：给定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