矩阵乘法的运算量与矩阵乘法的顺序强相关。
例如：
A是一个50×10的矩阵，B是10×20的矩阵，C是20×5的矩阵
计算A*B*C有两种顺序：((AB)C)或者(A(BC))，前者需要计算15000次乘法，后者只需要3500次。
编写程序计算不同的计算顺序需要进行的乘法次数。
数据范围：矩阵个数：
，行列数：
，保证给出的字符串表示的计算顺序唯一。
进阶：时间复杂度：%5C)
，空间复杂度：
[编程题]矩阵乘法计算量估算
- 热度指数：71539 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
输入多行，先输入要计算乘法的矩阵个数n，每个矩阵的行数，列数，总共2n的数，最后输入要计算的法则计算的法则为一个字符串，仅由左右括号和大写字母（'A'~'Z'）组成，保证括号是匹配的且输入合法！
输出描述:
输出需要进行的乘法次数
示例1
输入
3 50 10 10 20 20 5 (A(BC))
输出
3500
//与四则运算有相同的思想，只不过这里的运算情况只有一种，所以符号栈可以省略
#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)
#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)
#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)
#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)
#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)
#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)
#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)
#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)
#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)
问题信息
难度：
11条回答
1988收藏
33429浏览
通过挑战的用户
查看代码-
2022-09-20 10:34:20 -
2022-09-19 13:21:16
-
2022-09-16 10:49:21
-
2022-09-16 10:05:16
-
2022-09-16 08:49:35
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
