矩阵连乘.cpp

矩阵连乘的应用

#include <iostream.h> 
#include <fstream.h>
#include <stdio.h> 
ofstream myoutf("output.txt");            //输出到文件,全局变量
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()
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