C语言实现，已知5个矩阵并可连乘,编写程序输出矩阵连乘的最优计算次序

实现矩阵连乘的最优计算次序，可以使用动态规划的方法。

首先，我们需要定义一个二维数组m和一个二维数组s来存储最优计算次序和最优计算代价。其中，m[i][j]表示矩阵Ai到Aj的最优计算次序，s[i][j]表示矩阵Ai到Aj的最小计算代价。

接下来，我们可以使用以下的动态规划算法来计算m和s数组：

1. 初始化m和s数组的对角线，即当i=j时，m[i][j]=0，s[i][j]=0。

2. 对于每个长度为l的子问题，从左到右依次计算s[i][i+l]和m[i][i+l]，其中i表示子问题的起始下标，l表示子问题的长度，即i+l<=n。

3. 在计算s[i][i+l]时，我们需要枚举Ai到Ak和Ak+1到Aj的所有可能划分，计算每个划分的代价，并选择最小的代价作为s[i][i+l]的值。具体地，我们可以使用以下的公式来计算s[i][i+l]：

s[i][i+l] = min{s[i][k] + s[k+1][i+l] + p[i-1]*p[k]*p[i+l]}，其中i<=k<i+l，p[i-1]表示矩阵Ai-1的行数，p[k]表示矩阵Ak的列数，p[i+l]表示矩阵Ai+l的列数。

4. 在计算m[i][i+l]时，我们可以利用上一步计算得到的s数组来确定最优的计算次序。具体地，我们可以使用以下的公式来计算m[i][i+l]：

m[i][i+l] = k，其中i<=k<i+l，且s[i][i+l] = s[i][k] + s[k+1][i+l] + p[i-1]*p[k]*p[i+l]。

5. 最终，我们可以输出m[1][n]来得到矩阵连乘的最优计算次序。

下面是使用C语言实现上述算法的示例代码：

#include <stdio.h>
#include <stdlib.h>

#define MAXN 5  // 矩阵的个数

int p[MAXN+1];  // 存储矩阵的行列数
int m[MAXN+1][MAXN+1];  // 存储最优计算次序
int s[MAXN+1][MAXN+1];  // 存储最小计算代价

void matrix_chain_order(int n) {
    int i, j, k, l, q;

    // 初始化对角线
    for (i = 1; i <= n; i++) {
        m[i][i] = 0;
        s[i][i] = 0;
    }

    // 计算子问题的最小计算代价和最优计算次序
    for (l = 2; l <= n; l++) {
        for (i = 1; i <= n-l+1; i++) {
            j = i + l - 1;
            s[i][j] = 0x7fffffff;  // 初始化为最大值
            for (k = i; k <= j-1; k++) {
                q = s[i][k] + s[k+1][j] + p[i-1]*p[k]*p[j];
                if (q < s[i][j]) {
                    s[i][j] = q;
                    m[i][j] = k;
                }
            }
        }
    }
}

void print_optimal_parens(int i, int j) {
    if (i == j) {
        printf("A%d", i);
    } else {
        printf("(");
        print_optimal_parens(i, m[i][j]);
        print_optimal_parens(m[i][j]+1, j);
        printf(")");
    }
}

int main() {
    int i, n;

    // 读入矩阵的行列数
    printf("请输入%d个矩阵的行列数：\n", MAXN);
    for (i = 0; i <= MAXN; i++) {
        scanf("%d", &p[i]);
    }

    // 计算最优计算次序
    n = MAXN;
    matrix_chain_order(n);

    // 输出最优计算次序
    printf("矩阵连乘的最优计算次序为：");
    print_optimal_parens(1, n);
    printf("\n");

    return 0;
}