首页 > 试题广场 >

矩阵乘法计算量估算

[编程题]矩阵乘法计算量估算
  • 热度指数：79322 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
\hspace{15pt}对于给定的 a 行 b 列的矩阵：
A = \begin{bmatrix} A_{1,1} & A_{1,2} & \cdots & A_{1,b} \\ A_{2,1} & A_{2,2} & \cdots & A_{2,b} \\ \vdots & \vdots & \ddots & \vdots \\ A_{a,1} & A_{a,2} & \cdots & A_{a,b} \end{bmatrix}
\hspace{15pt}和 b 行 c 列的矩阵：
B = \begin{bmatrix} B_{1,1} & B_{1,2} & \cdots & B_{1,c} \\ B_{2,1} & B_{2,2} & \cdots & B_{2,c} \\ \vdots & \vdots & \ddots & \vdots \\ B_{b,1} & B_{b,2} & \cdots & B_{b,c} \end{bmatrix}
\hspace{15pt}和 c 行 d 列的矩阵：
C = \begin{bmatrix} C_{1,1} & C_{1,2} & \cdots & C_{1,d} \\ C_{2,1} & C_{2,2} & \cdots & C_{2,d} \\ \vdots & \vdots & \ddots & \vdots \\ C_{c,1} & C_{c,2} & \cdots & C_{c,d} \end{bmatrix}
\hspace{15pt}在计算 A \times B \times C 时，不同的运算顺序会带来不同的运算量。例如，(A \times B) \times C 的运算量是 a \times b \times c + a \times c \times d，而 A \times (B \times C) 的运算量是 b \times c \times d + a \times b \times d。

\hspace{15pt}现在，对于给定的 n 个矩阵的大小与运算式，请你计算出所需要的运算量。

输入描述:
\hspace{15pt}第一行输入一个整数 n \left(1 \leqq n \leqq 15\right) 代表矩阵的个数。
\hspace{15pt}此后 n 行，第 i 行输入两个整数 a_i 和 b_i \left(1 \leqq a_i, b_i \leqq 100\right) 代表第 i 个矩阵的行数和列数。
\hspace{15pt}最后一行输入一个长度为 1 \leqq {\rm len}(s) \leqq 10^3 的字符串 s 代表运算式。运算式中只包含前 n 个大写字母与括号，第 i 个大写字母对应输入的第 i 个矩阵，括号成对出现，保证运算式合法且正确。


输出描述:
\hspace{15pt}在一行上输出一个整数，代表计算需要的运算量。
示例1

输入

3
50 10
10 20
20 5
(A(BC))

输出

3500
示例2

输入

3
50 10
10 20
20 5
((AB)C)

输出

15000

备注:
\hspace{15pt}本题数据已进行修复（2025/01/09）。
算法知识视频讲解
添加回答
C
牛客937765135号头像 牛客937765135号
S -> '(' P ')'
P -> EE
E -> S | '[A-Z]'
然后递归下降解决 
#include <stdio.h>

int cnt;
char order [64];
char * p = order;
int matr [16][2];

struct rtv {
  char r;
  char c;
};

int S (struct rtv *);
int P (struct rtv *);
int E (struct rtv *);
int A (struct rtv *);

int 
S (struct rtv * r)
{
  p += 1;
  int xx = P (r);
  p += 1;
  return xx;
}

int
P (struct rtv * r)
{
  struct rtv o1, o2;
  int calc = 0;
  calc += E (&o1);
  calc += E (&o2);
  r->r = o1.r;
  r->c = o2.c;
  calc += r->r * r->c * o1.c;
  return calc;
}

int
E (struct rtv * r)
{
  int cc;
  if (*p == '(')
    cc = S (r);
  else
    cc = A (r);
  return cc;
}

int
A (struct rtv * r)
{
  r->r = matr [*p - 'A'][0];
  r->c = matr [*p - 'A'][1];
  p += 1;
  return 0;
}

int main() {
  int n;
  scanf ("%d", &n);
  for (int i = 0; i < n; i++)
  {
    scanf ("%d", matr[i]);
    scanf ("%d", matr[i] + 1);
  }

  fgets (order, 64, stdin);
  fgets (order, 64, stdin);
  printf ("%d\n", S (&(struct rtv){}));
    
  return 0;
}


发表于 2024-07-25 21:10:52 回复(0)
C
_前路漫漫亦灿灿_头像 _前路漫漫亦灿灿_ 
//与四则运算有相同的思想，只不过这里的运算情况只有一种，所以符号栈可以省略
#include <stdio.h>
#include <string.h>
struct node{
    int x;
    int y;
};
int main() {
    int n;
    scanf("%d", &n);
    // int a[16][2] = {0};
    struct node juzhen[16] = {0};
    char str[45] = {0};
    for(int i = 0; i < n; i++){
        scanf("%d %d", &juzhen[i].x, &juzhen[i].y);
    }
    scanf("%s", str);

    // char stack1[46] = {0}; //括号栈
    // int top1 = -1;
    
    struct node stack2[46] = {0} ; //矩阵栈
    int top2 = -1;
    int sum = 0;

    for(int i = 0; i < strlen(str); i++){
        if(str[i] == '('){
            //stack1[++top1] = str[i];
        }else if(str[i] >= 'A' && str[i] <= 'Z'){
            stack2[++top2] = juzhen[str[i] - 'A'];
        }else if(str[i] == ')'){
            //stack2连续pop出两个矩阵，并计算
            struct node pop1, pop2;
            pop1 = stack2[top2--];
            pop2 = stack2[top2--];
            sum += pop2.x * pop2.y * pop1.y;
              //入栈
            struct node tmp;
            tmp.x = pop2.x;
            tmp.y = pop1.y;
            stack2[++top2] = tmp;
            //stack1 pop出一个(
            //top1--;
        }
    }
    printf("%d", sum);


    return 0;
}

发表于 2024-03-03 12:31:18 回复(0)
C
牛客741101912号头像 牛客741101912号 
#include <stdio.h>
#include <ctype.h>
#define ROW(m) (m >> 16)
#define COL(m) (m & 0xFFFF)
#define ROW_ADDR(r) (((unsigned short*)&(r))+1)
#define COL_ADDR(c) ((unsigned short*)&(c))
/* 用一个 unsigned int 同时存储矩阵的行数和列数
默认了 int 是 32 位，short 是 16 位，其实应该用 uint32_t 之类的 */

unsigned
cal(unsigned mat1, unsigned mat2, unsigned *out_mat)
{
    /* 返回值是矩阵 mat1 * mat2 的乘法次数 */
    /* out_mat 存储新矩阵的行数和列数 */
    unsigned r1, r2, c2;
    r1 = ROW(mat1); /* 矩阵 mat1 的行数 */
    r2 = COL(mat1); /* 矩阵 mat1 的列数等于矩阵 mat2 的行数 */
    c2 = COL(mat2); /* 矩阵 mat2 的列数 */
    *out_mat = (mat1 & 0xFFFF0000) | (mat2 & 0xFFFF);
    /* 新矩阵的行数是 mat1 的行数，新矩阵的列数是 mat2 的列数 */
    return r1 * r2 * c2;
}

int main(void) {
    unsigned i, n, c, top;  /* 不涉及负数，所以用 unsigned 没问题 */
    unsigned cnt;           /* 存储最终结果 */
    while (scanf("%d", &n) == 1) {
        unsigned mats[n];   /* 存储逐行输入的矩阵行数和列数 */
        unsigned st[n];     /* 最后一行输入字母时，将相应的矩阵入栈 */
        for (i = 0; i != n; i++) {
            scanf("%hu%hu\n",    /* hu 指明读取 unsigned short 类型 */
            /* \n 不能漏掉，否则后面第一个 getchar() 会读取换行符 */
            ROW_ADDR(mats[i]),  /* 将行数存储在 unsigned int 的高 16 位 */
            COL_ADDR(mats[i])); /* 将列数存储在 unsigned int 的低 16 位 */
        }
        i = cnt = 0;
        top = -1;
        do {
            c = getchar();
            if (isupper(c)) {   /* 若为大写字母，则将矩阵入栈 */
                st[++top] = mats[i++];
            }
            else if (c == ')') {/* 题目指明括号匹配且输入合法，可以只考虑')' */
                top--;
                cnt += cal(st[top], st[top+1], st+top);
                /* 先出栈的是 mat2，即右边的矩阵
                   后出栈的是 mat1，即左边的矩阵
                   这里 st[top] 是 mat1
                   st[top+1] 是 mat2 */
            }
        }while (c != '\n' && c != EOF);
        printf("%u\n", cnt);
    }
    return 0;
}

发表于 2024-01-01 17:16:25 回复(0)
C
ezdoes头像 ezdoes 
#include <stdio.h>
#include <string.h>
/*
因为都是乘法，且计算次数为矩阵数-1

循环（n=计算次数）次：
    直接遍历字符串中AB型子串
    计算结果AB相乘次数answer 
    并将AB改变为A ， A的列数改为B的列数
    字符串的子串部分由AB改为A

*/
int sqrs[15][2];
int count;
char order[50];

void input() {
    scanf("%d", &count);
    for (int i = 0; i < count; i++) {
        scanf("%d %d", &sqrs[i][0], &sqrs[i][1]);
    }
    scanf("%s", order);
}

int calc(int r1, int c1, int c2) {
    return (r1 * c1 * c2);
}

/**
AB->A
(AB)->A
*/
void strchange(int start) {
    if (order[start] >= 'A' && order[start] <= 'P') {
        sqrs[order[start] - 'A'][1] = sqrs[order[start + 1] - 'A'][1];
        strcpy(order + start + 1, order + start + 2);
    } else {
        sqrs[order[start + 1] - 'A'][1] = sqrs[order[start + 2] - 'A'][1];
        order[start] = order[start + 1];
        strcpy(order + start + 1, order + start + 4);
    }
}

int calculate() {
    int answer;
    int idx = 0;
    while (order[idx] != 0) {
        if (order[idx] >= 'A' && order[idx] <= 'P' &&
                order[idx + 1] >= 'A' && order[idx + 1] <= 'P') {
            answer = calc(sqrs[order[idx] - 'A'][0], sqrs[order[idx] - 'A'][1],
                          sqrs[order[idx + 1] - 'A'][1]);
            if (idx > 0 && order[idx - 1] == '(' && order[idx + 2] == ')') {
                strchange(idx - 1);
            } else {
                strchange(idx);
            }
            return answer;
        }
        idx++;
    }
    return 0;
}



int main() {
    int result=0;
    input();
    for(int i=0;i<count;i++){
        result+=calculate();
    }
    printf("%d",result);
    return 0;
}

编辑于 2023-12-05 22:31:41 回复(0)
C
牛客364244344号头像 牛客364244344号 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct{
    int top;
    char content[100];
} Stack;

void push(Stack* stack, char c)
{
    stack->content[++stack->top] = c;
}

char pop(Stack* stack)
{
    char c = 0;
    if(stack->top > -1){
        c = stack->content[stack->top];
        stack->top--;
    }
    return c;
}

int Calculate(int a1[2], int a2[2], int* k, Stack* stack, int a[][2], int n)
{
    int sum = 0;
    sum = a1[0] * a2[1] * a1[1];
    *k += 1;
    push(stack, 'A'+n+*k-1);
    a[n+*k-1][0] = a1[0];
    a[n+*k-1][1] = a2[1];
    return sum;
}

int main()
{
    int n;
    char matchrRule[100];
    int len = 0;
    int total = 0;
    scanf("%d", &n);
    int a[2*n][2];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < 2; j++){
            scanf("%d", &a[i][j]);
        }
    }
    scanf("%s", matchrRule);
    len = strlen(matchrRule);
    Stack stack;
    stack.top = -1;
    int k = 0;
    for(int i = 0; i < len; i++){
        if(matchrRule[i] != ')'){
            push(&stack, matchrRule[i]);
        }else{
            char c1 = pop(&stack);
            char c2 = pop(&stack);
            char c3 = pop(&stack);
            int *test1 = a[c2-'A'];
            int *test2 = a[c1-'A'];
            total += Calculate(a[c2-'A'], a[c1-'A'], &k, &stack, a, n);
        }
    }
    printf("%d\n", total);
    return 0;
}

发表于 2023-10-29 14:32:44 回复(0)
C
初牛小客头像 初牛小客 
#include <stdio.h>
#include <string.h>

typedef struct matrix{
    int row;
    int col;
}Matrix;

typedef struct stack{
    Matrix m[100];
    int top;
}Stack;

int main() {
    int n;
    int count = 0;
    char str[100] = {};
    Matrix m[15] = {0};
    scanf("%d", &n);
    for(int i=0; i<n; i++)
        scanf("%d %d", &m[i].row, &m[i].col);
    scanf("%s", str);

    int index = 0;          //记录矩阵下标
    Stack s = {{0},-1};     //初始化栈
    int len = strlen(str);
    for(int i=0; i<len; i++)
    {
        if(str[i] != ')')   //入栈
        {
            if(isalpha(str[i]))
                memcpy(&s.m[++s.top],&m[index++],sizeof(Matrix));
        }
        else                //出栈,遇到')'就弹出两个矩阵，并把新矩阵压入栈中
        {
            Matrix m1,m2,m3;
            memcpy(&m1, &s.m[s.top--], sizeof(Matrix));
            memcpy(&m2, &s.m[s.top--], sizeof(Matrix));
            m3.row = m2.row;
            m3.col = m1.col;
            memcpy(&s.m[++s.top],&m3,sizeof(Matrix));
            count += m2.col*m2.row*m1.col;
        }
    }
    printf("%d", count);
    return 0;
}

发表于 2023-03-05 00:45:43 回复(0)
C
躺平大师头像 躺平大师 
#include <stdio.h>
#include <ctype.h>

int mpos = 0, spos = 0;

int matrix_calc(char *str, int *matrix, int *row, int *col)
{
    int calc_num = 0;
    int matrixr_r = 0, matrixr_c = 0;
    int matrixl_r = 0, matrixl_c = 0;
    
    if (isupper(str[spos])) {
        matrixl_r = matrix[mpos++];
        matrixl_c = matrix[mpos++];
        spos++;
    } else if (str[spos] == '(') {
        spos++;
        calc_num += matrix_calc(str, matrix, &matrixl_r, &matrixl_c);
    }
    
    while (str[spos]) {
        if (str[spos] == '(') {
            spos++;
            calc_num += matrix_calc(str, matrix, &matrixr_r, &matrixr_c);
            calc_num += matrixl_r * matrixl_c * matrixr_c;
            matrixl_c = matrixr_c;
        }
        if (isupper(str[spos])) {
            matrixr_r = matrix[mpos++];
            matrixr_c = matrix[mpos++];
            calc_num += matrixl_r * matrixl_c * matrixr_c;
            matrixl_c = matrixr_c;
        }

        if (str[spos++] == ')')
            break;
    };
    
    *row = matrixl_r;
    *col = matrixl_c;
    return calc_num;
}

int main()
{
    int matrix[30], index = 0;
    int count, row, col;
    char str[128] = {0};
    scanf("%d", &count);
    while (count--) {
        scanf("%d %d", &row, &col);
        matrix[index++] = row;
        matrix[index++] = col;
    }
    scanf("%s", str);
    row = col = 0;
    printf("%d", matrix_calc(str, matrix, &row, &col));
    return 0;
}

发表于 2022-06-23 11:25:41 回复(0)
C
已注销头像 已注销 
#include <stdio.h>
int main()
{
    int n,input[15][2],stack[15][2],cnt=0,i,j=0;
    char str[50];
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d%d",&input[i][0],&input[i][1]);
    }
    scanf("%s",str);
    i=0;
    while(str[i]!='\0')
    {
        if(str[i]>='A'&&str[i]<='Z')
        {
            stack[j][0]=input[str[i]-'A'][0];
            stack[j][1]=input[str[i]-'A'][1];
            j++;
        }
        else if(str[i]==')')
        {
            cnt+=stack[j-1][0]*stack[j-1][1]*stack[j-2][0];
            stack[j-2][1]=stack[j-1][1];
            j--;
        }
        i++;
    }
    printf("%d\n",cnt);
    return 0;
}
比四则运算那道题简单太多了
发表于 2022-05-03 16:38:54 回复(0)
C
校长_头像 校长_ 
#include "stdio.h"
#include "stdlib.h"
#include "string.h"

int stack1[100][2];
int stack_pointer;

void push(int a, int b);
void pop(int *a, int *b);

int main()
{
    int num,len;
    int a,b,c,d, sum;    //计算乘法次数用
    
    while(scanf("%d", &num) != EOF)
    {
        int k=0;
        int matrix[100][2] = {0};
        char str1[100] = {0};
        
        /*初始化*/
        sum = 0;
        stack_pointer = -1;//栈指针复位到-1位置。
        memset(stack1,0,200*sizeof(int));
        for(int i=0; i<num; i++)
        {
            for(int j=0; j<2; j++)
            {
                scanf("%d", &matrix[i][j]);
            }
        }
        scanf("%s", str1);
        len = strlen(str1);
        
        for(int i=0; i<len; i++)
        {
            if(str1[i] >= 'A' && str1[i] <= 'Z')
            {
                push(matrix[k][0], matrix[k][1]);
                k++;
            }
            else if(str1[i] == ')')
            {
                pop(&c,&d);
                pop(&a,&b);
                if(c == b)
                {
                    sum += a*b*d;//求乘法次数
                    push(a,d);//把相乘形成的新数组压入栈
                }
                else
                {
                    printf("error\n");
                }
            }
            else ;
            
        }
        
        printf("%d\n", sum);
    }
    return 0;
}

void push(int a, int b)
{
    stack_pointer++;
    stack1[stack_pointer][0] = a;
    stack1[stack_pointer][1] = b;
    
}

void pop(int *a, int *b)
{
    *a = stack1[stack_pointer][0];
    *b = stack1[stack_pointer][1];
    stack1[stack_pointer][0] = 0;
    stack1[stack_pointer][1] = 0;
    stack_pointer--;
}

发表于 2021-09-05 17:57:19 回复(0)
C
牛客743102380号头像 牛客743102380号 
#include<stdio.h>
int main()
{
    int n;
    while(scanf("%d",&n) != EOF)
    {
        int juzhen[100][2];
        int b[100][2];
        char a[100] = {0};
        for(int i = 0;i < n;i++)
        {
            scanf("%d",&juzhen[i][0]);
            scanf("%d",&juzhen[i][1]);
        }
        scanf("%s",&a);
        int len = strlen(a);
        int sum = 0;
        int i = 0;
        int j = 0;
        int count = 0;
       
        while(i < len)
        {
            if(a[i] == '(')
            {
                i++;
            }
            if(a[i] >= 'A' && a[i] <= 'Z')
            {
                b[j][0] = juzhen[a[i] - 'A'][0];
                b[j][1] = juzhen[a[i] - 'A'][1];
                i++;
                j++;
                if(a[i] >= 'A' && a[i] <= 'Z')
                {
                b[j][0] = juzhen[a[i] - 'A'][0];
                b[j][1] = juzhen[a[i] - 'A'][1];
                    i++;
                j++;
                }
                if(a[i] == '(')
                {
                    i++;
                }
                if(a[i] == ')')
                {
                    j--;
                    sum += b[j - 1][0] * b[j - 1][1] * b[j][1];
                    b[j - 1][1] = b[j][1];
                    i++;
                }
            }
            if(a[i] == ')')
                {
                    j--;
                    sum += b[j - 1][0] * b[j - 1][1] * b[j][1];
                    b[j - 1][1] = b[j][1];
                    i++;
                }
        }
        printf("%d\n",sum);
    }
    return 0;
}


发表于 2021-08-22 18:18:13 回复(0)
提交观点

问题信息

字符串 栈
难度：
12条回答 35284浏览

热门推荐

通过挑战的用户

查看代码

相关试题

矩阵乘法计算量估算

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号