- #include <iostream>
- #define INFTY 2147483647
- /*
- *计算输出连乘方案的括号位置和数目
- *parameter:brackets 长度为2n用来保存每个矩阵的左右括号数量,如brackets[0],brackets[1]分别保存第一个矩阵的左右括号数量;
- * 辅助矩阵 flag,其大小和矩阵 C 等同, flag[i,j]表示求解 C[i,j]时所得到的最佳分割 k 值,如计算 C[2,5]时,使 C[2,5]值最小的 k 的值为 4,
- * 则 flag[2,5]=4,利用 flag 数组可以计算 brackets 数组的值。
- * k为分割位置,low和high为带分割的矩阵下标范围。
- */
- void kuohao(int* brackets, int** flag, int k, int low, int high){
- if (high - low != 0){
- brackets[2 * low]++;
- brackets[2 * high + 1]++;
- }
- if (high - low > 1){
- kuohao(brackets, flag, flag[low][k - 1], low, k - 1);
- kuohao(brackets, flag, flag[k][high], k, high);
- }
- }
- int matChain(int r[], int n){
- int **C, **flag;
- int *brackets;
- brackets = new int[2 * n];
- C = new int*[n];
- flag = new int*[n];
- for (int i = 0; i < 2 * n; i++)
- brackets[i] = 0;
- for (int i = 0; i < n; i++){
- C[i] = new int[n];
- flag[i] = new int[n];
- }
- for (int i = 0; i < n; i++)
- for (int j = 0; j < n; j++){
- C[i][j] = 0;
- flag[i][j] = 0;
- }
- for (int d = 1; d<n; d++)
- for (int i = 0; i<n - d; i++){
- int j = i + d;
- C[i][j] = INFTY;
- for (int k = i + 1; k <= j; k++)
- if (C[i][j] > C[i][k - 1] + C[k][j] + r[i] * r[k] * r[j + 1]){
- flag[i][j] = k;
- C[i][j] = C[i][k - 1] + C[k][j] + r[i] * r[k] * r[j + 1];
- }
- }
- printf("计算得到C[i][j]矩阵为:\\n");
- for (int i = 0; i < n; i++){
- for (int j = 0; j < n; j++)
- if (i != j&&C[i][j] == 0)
- printf("%8c", 32);
- else
- printf("%8d", C[i][j]);
- printf("\\n");
- }
- /*
- for (int i = 0; i < n; i++){
- for (int j = 0; j < n; j++)
- if (i != j&&C[i][j] == 0)
- printf("%8c", 32);
- else
- printf("%8d", flag[i][j]);
- printf("\\n");
- }
- */
- kuohao(brackets, flag, flag[0][n - 1], 0, n - 1);
- brackets[0]--;
- brackets[2 * n - 1]--;
- printf("\\n矩阵连乘的方案为:\\n");
- for (int i = 0; i < n; i++){
- for (int j = 0; j < brackets[2 * i]; j++)
- printf("%c", '(');
- printf("M%d", i+1);
- for (int j = 0; j < brackets[2 * i + 1]; j++)
- printf("%c", ')');
- }
- printf("\\n");
- return C[0][n - 1];
- }
- int main__(int argc, char** argv) {
- int r[] = { 4, 5, 3, 6, 4, 5 };
- int m = matChain(r, 5);
- printf("矩阵连乘所需要的最少数量乘法次数为:%d \\n", m);
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/0805201512526.html
来源: http://www.codesnippet.cn/detail/0805201512526.html