c语言矩阵乘法计算量估算

1.题目描述

矩阵乘法的运算量与矩阵乘法的顺序强相关。
例如：

A是一个50×10的矩阵，B是10×20的矩阵，C是20×5的矩阵

计算ABC有两种顺序：（（AB）C）或者（A（BC）），前者需要计算15000次乘法，后者只需要3500次。

编写程序计算不同的计算顺序需要进行的乘法次数。

2.输入输出

输入多行，先输入要计算乘法的矩阵个数n，每个矩阵的行数，列数，总共2n的数，最后输入要计算的法则
计算的法则为一个字符串，仅由左右括号和大写字母（'A'~'Z'）组成，保证括号是匹配的且输入合法！
输出需要进行的乘法次数

3.解题思路

[m,n] x [n,p] 共会有npm次乘法运算，运算后的矩阵为 [m,p]

4.源码实现

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

int mul_with_brackets(int *a, char *buf)
{
    int b[128][3];
    int m = strlen(buf);
    int u = 0;
    int v = 0;
    int i;
    int k;
    int j = 0;

    for(i=0; i<m; i++)
    {
        if(buf[i] >= 'A' && buf[i] <= 'Z')
        {
            k = buf[i] - 'A';

            /*printf("u=%d, a[%d]=%d, a[%d]=%d\n", u, 2*k, a[2*k], 2*k+1, a[2*k+1]);*/

            if(!v)
            {
                v = 1;
            }

            if(u)
            {
                b[j][0] = a[2*k];
                b[j][1] = a[2*k+1];
                b[j][2] = 0;

                /*printf("b[%d][0]=%d, b[%d][1]=%d, b[%d][1]=%d\n", j-1, b[j-1][0], j-1, b[j-1][1], j, b[j][1]);*/

                b[j-1][2] += b[j-1][0] * b[j-1][1] * b[j][1];
                b[j-1][1] = b[j][1];

                u = 2;
            }
            else
            {
                b[j][0] = a[2*k];
                b[j][1] = a[2*k+1];
                b[j][2] = 0;
                u = 1;
                j++;
            }
        }
        else if(buf[i] == '(')
        {
            if(u == 1 || u == 2)
            {

            }
            else if(u == 0)
            {
                b[j][0] = -1;
                b[j][1] = -1;
                b[j][2] = 0;
                j++;
            }

            u = 0;
        }
        else if(buf[i] == ')')
        {
            if(u == 2 || u == 1)
            {
                if(b[j-2][0] == -1 && b[j-2][1] == -1)
                {
                    j--;

                    b[j-1][0] = b[j][0];
                    b[j-1][1] = b[j][1];
                    b[j-1][2] = b[j][2];

                    /*printf("b[%d][0]=%d, b[%d][1]=%d, b[%d][2]=%d\n", j-1, b[j-1][0], j-1, b[j-1][1], j-1, b[j-1][2]);*/

                    u = 1;
                }
                else
                {
                    j--;

                    b[j-1][2] += b[j][2];

                    /*printf("b[%d][0]=%d, b[%d][1]=%d, b[%d][2]=%d\n", j-1, b[j-1][0], j-1, b[j-1][1], j-1, b[j-1][2]);*/

                    b[j-1][2] += b[j-1][0] * b[j-1][1] * b[j][1];
                    b[j-1][1] = b[j][1];

                    u = 2;
                }
            }
        }
    }

    if(!v)
    {
        return 0;
    }

    return b[0][2];
}

int main()
{
    char buf[1024];
    int a[26*2];
    int n;
    int b;
    int i;

    while(scanf("%d", &n) != EOF)
    {
        for(i=0; i<n; i++)
        {
            scanf("%d %d", a+2*i, a+2*i+1);
        }
    
        scanf("%s", buf);
    
        b = mul_with_brackets(a, buf);
    
        printf("%d\n", b);
    }

    return 0;
}

5.编译源码

$ gcc -o example examle.c -std=c89

6.运行及其结果

$ ./example
3
50 10
10 20
20 5
(A(BC))
3500