编程实现5个矩阵连乘问题的备忘录算法利用C语言

在C语言中，我们可以使用备忘录算法（也称为动态规划）来优化矩阵连乘的问题，特别是当递归计算过程中存在重复子问题时。以下是简单的步骤：

1. 定义结构体或全局变量存储中间结果矩阵，以便在后续计算中复用。

typedef struct {
    int m1[10][10], m2[10][10], m3[10][10]; // 根据实际矩阵大小调整数组大小
    int n1, n2, n3;
} MatrixMultiplicationResult;

2. 创建一个函数`matrixMultiply`，接受三个矩阵作为输入，并检查是否已经计算过这个组合。如果有，则直接返回结果；否则计算并保存结果。

MatrixMultiplicationResult* memoMatrixMultiply(int m1, int n1, int n2, MatrixMultiplicationResult** cache) {
    if (cache[m1 * n1 + n2] != NULL) {
        return cache[m1 * n1 + n2];
    }
    
    // 矩阵乘法的逻辑
    MatrixMultiplicationResult* result = malloc(sizeof(MatrixMultiplicationResult));
    for (int i = 0; i < m1; i++) {
        for (int j = 0; j < n2; j++) {
            for (int k = 0; k < n1; k++) {
                result->m3[i][j] += matrix[m1 - 1][i][k] * matrix[n2 - 1][k][j];
            }
        }
    }

    // 存储结果并返回
    cache[m1 * n1 + n2] = result;
    return result;
}

3. 调用该函数时传递一个足够大的缓存数组，并初始化递归深度的边界情况。

int main() {
    int matrices[5][3][3] = { ... }; // 输入的5个矩阵数据
    MatrixMultiplicationResult** cache = malloc(sizeof(MatrixMultiplicationResult*) * (10 * 10 * 5)); // 假设每个矩阵最大尺寸为10x10
    for (int i = 0; i < 5; i++) {
        cache[i * 100] = NULL; // 初始化边界
    }

    MatrixMultiplicationResult* finalResult = memoMatrixMultiply(matrices[4][0][0], matrices[4][0][1], matrices[4][1][0], cache); // 从最后一个矩阵开始连乘

    // 输出最终结果
    for (int i = 0; i < finalResult->n3; i++) {
        for (int j = 0; j < finalResult->n3; j++) {
            printf("%d ", finalResult->m3[i][j]);
        }
        printf("\n");
    }

    // 清理内存
    free(cache);
    return 0;
}