1 #include <iostream>
  2 #include <vector>
  3 #include <algorithm>
  4 #include <limits.h>
  5 #include <string>
  6 
  7 using namespace std;
  8 
  9 int* uncertainInput(int& inputNum);
 10 
 11 //计算矩阵的分割方案（基于数组）
 12 int calculate_M1(int*data, int matrixNum, vector<vector<int> >&num, vector<vector<int> > &points) {
 13     
 14     int span;//起止点间隔距离，表示跨度 最大跨度比总的矩阵数小1
 15     int start;//起点
 16     int end;//终点
 17     int spiltPoint;//分割点 分割线在分割点与下一点之间
 18     int multiplyTimes;//临时存储子式的乘法运算次数
 19     int rows, columns, interfaces;//行 列 接口
 20 
 21     for (span = 1; span < matrixNum-1; span++) {                ///间隔距离 相邻矩阵的间隔距离为1
 22         for (start = 1; start + span < matrixNum; start++) {    ///起点从第一个矩阵的列开始
 23             //子式确立，下面开始计算这个子式的最少乘法运算次数，初值先设为最大整数
 24             end = start + span;
 25             num[start][end] = INT_MAX;
 26             for (spiltPoint = start; spiltPoint < end; spiltPoint++) {
 27                 rows = *(data + start-1);
 28                 columns = *(data + end);
 29                 interfaces = *(data + spiltPoint);
 30 
 31                 multiplyTimes = num[start][spiltPoint] + num[spiltPoint + 1][end] + rows * interfaces * columns;
 32                 if (multiplyTimes < num[start][end]) {
 33                     points[start][end] = spiltPoint;  ///记录分割点
 34                     num[start][end] = multiplyTimes;   ///记录最少乘法次数
 35                 }
 36             }
 37         }
 38     }
 39     return 0;
 40 }
 41 
 42 //根据记录的分割点，生成最后的矩阵相乘表达式
 43 string make_result(vector<vector<int> > &points, int t1, int t2) {
 44     if (t1 == t2)
 45         return string(1, 'A' + t1 -1);
 46     int split = points[t1][t2];
 47     return "(" + make_result(points, t1, split) + "*" + make_result(points, split + 1, t2) + ")";
 48 }
 49 
 50 
 51 int main()
 52 {
 53     int matrixNum = 0;///连乘的矩阵个数
 54     vector<pair<int, int>> data; ///存储矩阵的尺寸
 55 
 56     //手动输入
 57     //输入的第一个值是第一个矩阵的行，其余是各矩阵的列
 58     int* matrixSizeSeq;
 59     matrixSizeSeq = uncertainInput(matrixNum);
 60     if (matrixSizeSeq == NULL)
 61         return false;
 62     
 63     //重构为向量
 64     /*for (int ptrOffset = 0; ptrOffset < matrixNum - 1; ptrOffset++)    ///遍历到倒数第二个输入
 65         data.push_back(make_pair(*(matrixSizeSeq + ptrOffset), *(matrixSizeSeq + ptrOffset + 1)));*/
 66 
 67     //为记录乘法次数和分割点的n阶矩阵分配空间并初始化
 68     vector<vector<int> > num(matrixNum, vector<int>(matrixNum));
 69     vector<vector<int> > points(matrixNum, vector<int>(matrixNum));
 70     for (int i = 0; i < matrixNum; i++) {
 71         for (int j = 0; j < matrixNum; j++) {
 72             points[i][j] = -1;
 73             num[i][j] = 0;
 74         }
 75     }
 76 
 77     calculate_M1(matrixSizeSeq, matrixNum, num, points);
 78     cout << make_result(points, 1, matrixNum - 1) << "\t最少乘法次数为:" << num[1][matrixNum - 1] << endl;
 79     cin >> matrixNum;
 80     return 0;
 81 }
 82 
 83 int* uncertainInput(int& inputNum)
 84 {
 85     //输入0表示输入完成 输入负数认为手误
 86     using namespace std;
 87 
 88     int allocateSpace = 5;
 89     int* in