输入:矩阵链Ai…j的输入为向量P=<Pi-1,Pi,…,Pj>，其中:1<=i<=j<=n。输出:计算Ai…j的所需最小乘法运算次数m[i,j]和最后一次运算位置s[i,j]。输出C语言完整程序

矩阵链乘法（Matrix Chain Multiplication, MCM）是一个经典的问题，用于优化多层矩阵相乘的操作序列。给定一组矩阵A1,A2,...,An及其大小，目标是最小化它们相乘所需的总乘法次数。这个问题可以使用动态规划（Dynamic Programming）解决。

以下是用C语言实现矩阵链乘法的一个简化版的示例代码：

#include <stdio.h>

// 函数声明
int minMult(int P[], int n);
void printResult(int m[], int s[], int n);

int main() {
    int A[] = {10, 20, 30, 40, 50}; // 示例矩阵的维度
    int n = sizeof(A) / sizeof(A[0]);
    
    // 计算并存储最小乘法次数和操作位置
    int m[n * n], s[n * n];
    minMult(A, n);
    
    // 输出结果
    printResult(m, s, n);
    
    return 0;
}

// 动态规划函数 - 计算最小乘法次数
int minMult(int P[], int n) {
    for (int l = 2; l <= n; ++l) {
        for (int i = 1; i + l <= n; ++i) {
            int j = i + l - 1;
            m[i][j] = INT_MAX; // 初始化为最大值
            for (int k = i; k < j; ++k) {
                int q = m[i][k] + m[k+1][j] + P[i-1] * P[k] * P[j+1]; // 动态规划公式
                if (q < m[i][j]) {
                    m[i][j] = q;
                    s[i][j] = k; // 最后一次操作的位置
                }
            }
        }
    }
    return m[1][n-1]; // 返回整个矩阵链的最小乘法次数
}

// 打印结果函数
void printResult(int m[], int s[], int n) {
    printf("Minimum number of multiplications: %d\n", m[1][n-1]);
    printf("Final operation position: ");
    for (int i = 1; i < n; ++i) {
        if (s[1][n-1] == i)
            printf("(%d,%d)\t", i+1, n);
    }
    printf("\n");
}

这个代码首先定义了两个辅助数组`m[]`和`s[]`来存储最小乘法次数和最后一次操作位置，然后通过三层嵌套循环计算这些值。最后，它打印出最小乘法次数以及最后一个操作的位置。