#include<iostream>
using namespace std;
int input_matrix_num;
int p[100];
int m_Matrix(int i, int j);
void print_optimal(int i, int j);
int m[100][100];
int a = 0;
int b = 0;
int c = 0;
int d = 0;
int s[100][100];
int main() {
    cout << "輸入矩陣的個(gè)數(shù)：";
    cin >> input_matrix_num;
    cout << "請(qǐng)輸入" << input_matrix_num + 1 << "個(gè)正整數(shù)，分別是各個(gè)矩陣的行列數(shù)" << endl;
 
    for (int i = 0;i < input_matrix_num + 1;i++) {
        cin >> p[i];
    }
 
    cout << "原始數(shù)據(jù)為以下矩陣：" << endl;
    for (int i = 0;i < input_matrix_num;i++) {
        cout << "\t" << p[i] << " * " << p[i + 1] << endl;
    }
 
    cout << "m矩陣" << endl;
    for (int i = 1;i <= input_matrix_num;i++) {
        for (int j = 1;j <= input_matrix_num;j++) {
            m[i][j] = m_Matrix(i, j);
        }
    }
 
    for (int i = 1;i <= input_matrix_num;i++) {
        for (int j = 1;j <= input_matrix_num;j++) {
            cout << m[i][j] << "\t";
        }
        cout << endl;
    }
 
    cout << endl;
    cout << "s矩陣" << endl;
    for (int i = 1;i <= input_matrix_num;i++) {
        for (int j = 1;j <= input_matrix_num;j++) {
            cout << s[i][j] << "\t";
        }
        cout << endl;
    }
 
    cout << endl;
    cout << "最優(yōu)的運(yùn)算方式的乘法次數(shù)為：" << m_Matrix(1, 6) << endl;
 
    cout << "加括號(hào)的方式為：" << endl;
 
    print_optimal(1, input_matrix_num);
    cout << endl << endl;
 
}
 
int m_Matrix(int i, int j) {
    int small;
    int sum[100];
    if (j - i == 1) {
        s[i][j] = i;
    }
    while (j - i == 1) {
        return p[i - 1] * p[i] * p[j];
        break;
    }
    while (i >= j) {
        return 0;
        break;
    }
    //把所有的段點(diǎn)k存到一個(gè)數(shù)組，再利用數(shù)組進(jìn)行比較，篩選出最小的那個(gè)          
    for (int k = i;k <= j - 1;k++) {
        sum[k] = m_Matrix(i, k) + m_Matrix(k + 1, j) + p[i - 1] * p[k] * p[j];
    }
 
    int a = i;
    int b = i + 1;
 
    //篩選出運(yùn)算次數(shù)最少的那個(gè)
    while (b <= j - 1) {
        if (sum[a] <= sum[b]) {
            small = sum[a];
            b++;
            s[i][j] = a;
        }
        else {
            small = sum[b];
            a = b;
            b++;
            s[i][j] = a;
        }
    }
 
    return small;
}
 
 
void print_optimal(int i, int j) {
    if (i == j) {
        cout << " A[" << p[i - 1] << "," << p[i] << "]";
    }
    else {
        cout << " ( ";
        print_optimal(i, s[i][j]);
        print_optimal(s[i][j] + 1, j);
        cout << " ) ";
    }
}

運(yùn)行結(jié)果示例