Go语言视频零基础入门到精通

admin

1. #include <iostream>
2. #include <vector>
3. #define MAXVALUE 100000;
4. using namespace std;
7. void matrix_chain_order(vector<int>p,vector<vector<int>>&m,vector<vector<int>>&s)
8. {
9.         int i, j, k, t;
10.         int N = p.size() - 1;
11.         for (i = 0; i <= N; ++i)
12.                 m[i][i] = 0;
13.         for (t = 2; t <= N; t++)  //当前链乘矩阵的长度
14.         {
15.                 for (i = 1; i <= N - t + 1; i++)  //从第一矩阵开始算起，计算长度为t的最少代价
16.                 {
17.                         j = i + t - 1;//长度为t时候的最后一个元素
18.                         m[i][j] = MAXVALUE;  //初始化为最大代价
19.                         for (k = i; k <= j - 1; k++)   //寻找最优的k值，使得分成两部分k在i与j-1之间
20.                         {
21.                                 int temp = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
22.                                 if (temp < m[i][j])
23.                                 {
24.                                         m[i][j] = temp;   //记录下当前的最小代价
25.                                         s[i][j] = k;      //记录当前的括号位置，即矩阵的编号
26.                                 }
27.                         }
28.                 }
29.         }
30. }
32. //s中存放着括号当前的位置
33. void print_optimal_parents(vector<vector<int>>&s, int i, int j)
34. {
35.         if (i == j)
36.                 cout << "A" << i;
37.         else
38.         {
39.                 cout << "(";
40.                 print_optimal_parents(s, i, s[i][j]);
41.                 print_optimal_parents(s, s[i][j] + 1, j);
42.                 cout << ")";
43.         }
45. }
47. int main()
48. {
49.         int P[7] = { 30, 35, 15, 5, 10, 20, 25 };
50.         vector<int>p(P, P + 7);
51.        
52.         vector<int>tmp(p.size(), 0);
53.         vector<vector<int>>m(p.size(), tmp);
54.         vector<vector<int>>s(p.size(), tmp);
56.         int i, j;
57.         matrix_chain_order(p, m, s);
58.         cout << "m value is: " << endl;
59.         for (i = 1; i <= 6; ++i)
60.         {
61.                 for (j = 1; j <= 6; ++j)
62.                         cout << m[i][j] << " ";
63.                 cout << endl;
64.         }
65.         cout << "s value is: " << endl;
66.         for (i = 1; i <= 6; ++i)
67.         {
68.                 for (j = 1; j <= 6; ++j)
69.                         cout << s[i][j] << " ";
70.                 cout << endl;
71.         }
72.         cout << "The result is:" << endl;
73.         print_optimal_parents(s, 1, 6);
74.         return 0;
75. }

复制代码