***一个矩阵连乘的问题***
给定n个矩阵{A1,A2,...,An}，考察这n个矩阵的连乘积A1A2...An。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序，这种计算次序可以用加括号的方式来确定。
矩阵连乘积的计算次序与其计算量有密切关系。例如，考察计算3个矩阵{A1,A2,A3}连乘积的例子。设这3个矩阵的维数分别为10*100，100*5，和5*50。若按(A1A2)A3计算，3个矩阵连乘积需要的数乘次数为10*100*5+10*5*50 = 7500。若按A1(A2A3)计算，则总共需要100*5*50+10*100*50 = 75000次数乘。
现在你的任务是对于一个确定的矩阵连乘方案，计算其需要的数乘次数。
输入输出格式
输入数据由多组数据组成。每组数据格式如下：
第一行是一个整数n (1≤n≤26)，表示矩阵的个数。
接下来n行，每行有一个大写字母，表示矩阵的名字，后面有两个整数a,b，分别表示该矩阵的行数和列数，其中1<a,b<100。
第n+1行是一个矩阵连乘的表达式，由括号与大写字母组成，没有乘号与多余的空格。如果表达式中没有括号则按照从左到右的顺序计算，输入的括号保证能够配对。
对于每组数据，输出仅一行包含一个整数，即将该矩阵连乘方案需要的数乘次数。如果运算过程中出现不满足矩阵乘法法则的情况（即左矩阵列数与右矩阵的行数不同），则输出“error”。
样例输入
3
A 10 100
B 100 5
C 5 50
A(BC)
样例输出
75000
我写了一个程序，通过了我自己的所有测试数据，但是就是无法AC.请大家帮帮忙了
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*
-1:the bottom of stack
-2:'('
-3:')'
*/
#define NUM_OF_CHAR 26
typedef enum {FALSE,TRUE} BOOL;
struct m{
int row;
int col;
};
struct stack{
struct m a[NUM_OF_CHAR];
int top;
};
void initst(struct stack *ps)
{
ps->top=-1;
}
BOOL st_empty(struct stack s)
{
if(s.top==-1) return TRUE;
else return FALSE;
}
void push(struct stack *ps,struct m e)
{
if(ps->top+1==100){
printf("error:stack is full!\n");
exit(EXIT_FAILURE);
}
ps->a[++(ps->top)]=e;
}
struct m pop(struct stack *ps)
{
struct m e;
if(ps->top==-1){
printf("error:stack is empty!\n");
exit(EXIT_FAILURE);
}
e=ps->a[(ps->top)--];
return e;
}
struct m gettop(struct stack *ps)
{
struct m e;
e=ps->a[ps->top];
return e;
}
int find(char c[],char ch)
{
int i;
for(i=0;i<NUM_OF_CHAR;i++)
if(c[i]==ch) return i;
return -1;
}
int main()
{
int i,j,n;
long int mul;
struct m mt[NUM_OF_CHAR],m[NUM_OF_CHAR],mm,e;
char c[NUM_OF_CHAR];
char s[100],*ps;
struct stack st;
BOOL err;
while(scanf("%d",&n)!=EOF)
{
fflush(stdin);
for(i=0;i<n;i++){
scanf("%c%d%d",&c[i],&mt[i].row,&mt[i].col);
fflush(stdin);
}
gets(s);
ps=s;
initst(&st);
e.col=e.row=-1;
push(&st,e);
err=FALSE;
mul=0;
do
{
if(*ps>='A'&&*ps<='Z')
push(&st,mt[find(c,*ps)]);
else if(*ps=='('){
e.col=-2;e.row=-2;
push(&st,e);
}
else if(*ps==')'){
i=0;
m[i]=pop(&st);
while(m[i].row!=-2){
i++;
m[i]=pop(&st);
}
mm=m[i-1];
for(j=i-1;j>0;j--)
{
if(mm.col!=m[j-1].row){
err=TRUE;
break;
}
mul+=(long int)mm.row*mm.col*m[j-1].col;
mm.row=mm.row;mm.col=m[j-1].col;
}
push(&st,mm);
if(err) break;
}
else if(*ps=='\0'){
i=0;
m[i]=pop(&st);
while(m[i].row!=-1){
i++;
m[i]=pop(&st);
}
mm=m[i-1];
for(j=i-1;j>0;j--)
{
if(mm.col!=m[j-1].row){
err=TRUE;
break;
}
mul+=(long int)mm.row*mm.col*m[j-1].col;
mm.row=mm.row;mm.col=m[j-1].col;
}
//push(&st,mm);
if(err) break;
}
ps++;
}while(!st_empty(st));
if(err)
printf("error\n");
else
printf("%ld\n",mul);
}
return 0;
}
问题点数：100、回复次数：23Top
1 楼UPCC（杂食动物）回复于 2006-06-04 18:02:22 得分 0
留个脚印... ...Top
2 楼chenhu_doc（^0^纯一狼^0^ 看书看到大笑，直到不能自已）回复于 2006-06-04 18:13:44 得分 0
我也来做做！Top
3 楼donghaish（roland）回复于 2006-06-04 21:03:28 得分 0
up
Top
4 楼tailzhou（尾巴）回复于 2006-06-05 09:59:50 得分 0
你程序的输出应该有问题。
将
while(scanf("%d",&n)!=EOF)
{
}
修改为 scanf("%d",&n)再提交看看；
另外象 int find(char c[],char ch)这个函数是没必要的，
struct m mt[NUM_OF_CHAR];
scanf("%c %d %d",&c,&row,&col);
mt[c-'A'].row=row;
mt[c-'A'].col=col;
直接使用mt[*ps-'A']就找到对应的struct m了;
Top
5 楼tailzhou（尾巴）回复于 2006-06-05 10:10:28 得分 0
原题在哪？Top
6 楼SamuelKevin（曼陀罗）回复于 2006-06-05 12:08:18 得分 0
将
while(scanf("%d",&n)!=EOF)
{
}
修改为 scanf("%d",&n)再提交看看；
//楼上的 别误导人家
楼主那样写明明就是正确的嘛Top
7 楼tailzhou（尾巴）回复于 2006-06-05 12:14:46 得分 0
输入数据由多组数据组成。每组数据格式如下：
没看到这行，sorry allTop
8 楼donghaish（roland）回复于 2006-06-05 12:51:38 得分 0
另外象 int find(char c[],char ch)这个函数是没必要的，
struct m mt[NUM_OF_CHAR];
scanf("%c %d %d",&c,&row,&col);
mt[c-'A'].row=row;
mt[c-'A'].col=col;
直接使用mt[*ps-'A']就找到对应的struct m
但是如果我输入的不按照字母顺讯，比如Z A E什么的按你说的就不对了Top
9 楼donghaish（roland）回复于 2006-06-05 13:03:15 得分 0
原题在acm.fzu.edu.cnTop
10 楼tailzhou（尾巴）回复于 2006-06-05 13:09:44 得分 0
没仔细看你的程序，不过测试你的程序对(a)((b))(c)这样的出不来结果，应该出入栈有问题
我写了个，我这上不了acm.fzu.edu.cn,没法测试：
#include <iostream>
#define NUM_OF_CHAR 26
#define NUM_OF_STRING 100
struct m{
int row;
int col;
};
struct m mt[NUM_OF_CHAR];
char s[NUM_OF_STRING];
char * ps;
long mul;
struct m multiple()
{
long l=0;
struct m rst;
rst.row=0;
rst.col=0;
bool IsFirst=true;
while(true)
{
if (*ps==')' || *ps=='\0')
{
if (*ps==')')
{
++ps;
}
return rst;
}
struct m t;
if (*ps=='(')
{
++ps;
t=multiple();
if (t.row==-1)
{
return t;
}
}
else
{
t=mt[*ps-'A'];
++ps;
}
if (IsFirst)
{
rst.row=t.row;
rst.col=t.col;
IsFirst=false;
}
else
{
if (rst.col!=t.row)
{
t.row=-1;
return t;
}
mul+=rst.row*rst.col*t.col;
rst.col=t.col;
}
}
}
int main()
{
int i,j,n,row,col;
char c;
scanf("%d\n",&n);
for(i=0;i<n;i++){
scanf("%c %d %d\n",&c,&row,&col);
mt[c-'A'].row=row;
mt[c-'A'].col=col;
}
gets(s);
ps=s;
mul=0;
struct m rst=multiple();
if(rst.row==-1)
{
printf("error\n");
}
else
{
printf("%ld\n",mul);
}
return 0;
}
Top
11 楼tailzhou（尾巴）回复于 2006-06-05 13:14:39 得分 0
但是如果我输入的不按照字母顺讯，比如Z A E什么的按你说的就不对了
这题跟输入顺序没关系的呀!Top
12 楼tailzhou（尾巴）回复于 2006-06-05 13:15:42 得分 0
D:\projects\cl>TEST
3
A 10 100
B 100 5
C 5 50
((A))((B))(C)
7500
D:\projects\cl>TEST
3
A 10 100
C 5 50
B 100 5
((A))((B))(C)
7500Top
13 楼donghaish（roland）回复于 2006-06-05 13:36:01 得分 0
WRONG ANSER!Top
14 楼tailzhou（尾巴）回复于 2006-06-05 13:52:08 得分 0
我的程序只算一组数据的，你加上
while(scanf("%d",&n)!=EOF)
{
}
了没？Top
15 楼donghaish（roland）回复于 2006-06-05 16:31:01 得分 0
"仔细看你的程序，不过测试你的程序对(a)((b))(c)这样的出不来结果，应该出入栈有问题"
没问题啊，我试过了Top
16 楼tailzhou（尾巴）回复于 2006-06-05 16:41:36 得分 0
帖子你肯定修改过了，
#define NUM_OF_CHAR26，
上午都还能编译通过的Top
17 楼donghaish（roland）回复于 2006-06-05 17:14:36 得分 0
大哥，冤枉，我还不知道怎么修改帖子呢？！
我一点都没改Top
18 楼donghaish（roland）回复于 2006-06-06 23:37:58 得分 0
upTop
19 楼donghaish（roland）回复于 2006-06-10 22:04:09 得分 0
UPTop
20 楼tailzhou（尾巴）回复于 2006-06-12 19:57:54 得分 0
30559 2006-06-12 19:54:44 Accepted 1061 C++ 0.00s 320K tailzhou
#include <iostream>
#define NUM_OF_CHAR 26
#define NUM_OF_STRING 500
struct m{
int row;
int col;
};
struct m mt[NUM_OF_CHAR];
char s[NUM_OF_STRING];
char * ps;
long mul;
struct m multiple()
{
long l=0;
struct m rst;
rst.row=0;
rst.col=0;
bool IsFirst=true;
while(true)
{
if (*ps==')' || *ps=='\0')
{
if (*ps==')')
{
++ps;
}
return rst;
}
struct m t;
if (*ps=='(')
{
++ps;
t=multiple();
if (t.row==-1)
{
return t;
}
}
else
{
t=mt[*ps-'A'];
++ps;
}
if (IsFirst)
{
rst.row=t.row;
rst.col=t.col;
IsFirst=false;
}
else
{
if (rst.col!=t.row)
{
t.row=-1;
return t;
}
mul+=rst.row*rst.col*t.col;
rst.col=t.col;
}
}
}
int main()
{
int i,j,n,row,col;
char c;
while(scanf("%d\n",&n)!=EOF)
{
for(i=0;i<n;i++){
scanf("%c %d %d\n",&c,&row,&col);
mt[c-'A'].row=row;
mt[c-'A'].col=col;
}
gets(s);
ps=s;
mul=0;
struct m rst=multiple();
if(rst.row==-1)
{
printf("error\n");
}
else
{
printf("%ld\n",mul);
}
}
return 0;
}
Top
21 楼tailzhou（尾巴）回复于 2006-06-12 20:06:04 得分 0
30561 2006-06-12 19:58:58 Accepted 1061 C++ 0.01s 180K tailzhou
这次是用的你的程序（几处小修改）
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*
-1:the bottom of stack
-2:'('
-3:')'
*/
#define NUM_OF_CHAR 26 //***** 修改NUM_OF_CHAR26--> NUM_OF_CHAR 26
typedef enum {FALSE,TRUE} BOOL;
struct m{
int row;
int col;
};
struct stack{
struct m a[NUM_OF_CHAR];
int top;
};
void initst(struct stack *ps)
{
ps->top=-1;
}
BOOL st_empty(struct stack s)
{
if(s.top==-1) return TRUE;
else return FALSE;
}
void push(struct stack *ps,struct m e)
{
if(ps->top+1==500){ //*******修改 100-->500
printf("error:stack is full!\n");
exit(EXIT_FAILURE);
}
ps->a[++(ps->top)]=e;
}
struct m pop(struct stack *ps)
{
struct m e;
if(ps->top==-1){
printf("error:stack is empty!\n");
exit(EXIT_FAILURE);
}
e=ps->a[(ps->top)--];
return e;
}
struct m gettop(struct stack *ps)
{
struct m e;
e=ps->a[ps->top];
return e;
}
int find(char c[],char ch)
{
int i;
for(i=0;i<NUM_OF_CHAR;i++)
if(c[i]==ch) return i;
return -1;
}
int main()
{
int i,j,n;
long int mul;
struct m mt[NUM_OF_CHAR],m[NUM_OF_CHAR],mm,e;
char c[NUM_OF_CHAR];
char s[500],*ps; //****** 修改 s[100]-->s[500]
struct stack st;
BOOL err;
while(scanf("%d\n",&n)!=EOF) //** 修改"%d"-->"%d\n"
{
//fflush(stdin); //**** 注释了这行
for(i=0;i<n;i++){
scanf("%c %d %d\n",&c[i],&mt[i].row,&mt[i].col); ////** 修改"("%c%d%d"-->"%c %d %d\n"
//fflush(stdin); //**** 注释了这行
}
gets(s);
ps=s;
initst(&st);
e.col=e.row=-1;
push(&st,e);
err=FALSE;
mul=0;
do
{
if(*ps>='A'&&*ps<='Z')
push(&st,mt[find(c,*ps)]);
else if(*ps=='('){
e.col=-2;e.row=-2;
push(&st,e);
}
else if(*ps==')'){
i=0;
m[i]=pop(&st);
while(m[i].row!=-2){
i++;
m[i]=pop(&st);
}
mm=m[i-1];
for(j=i-1;j>0;j--)
{
if(mm.col!=m[j-1].row){
err=TRUE;
break;
}
mul+=(long int)mm.row*mm.col*m[j-1].col;
mm.row=mm.row;mm.col=m[j-1].col;
}
push(&st,mm);
if(err) break;
}
else if(*ps=='\0'){
i=0;
m[i]=pop(&st);
while(m[i].row!=-1){
i++;
m[i]=pop(&st);
}
mm=m[i-1];
for(j=i-1;j>0;j--)
{
if(mm.col!=m[j-1].row){
err=TRUE;
break;
}
mul+=(long int)mm.row*mm.col*m[j-1].col;
mm.row=mm.row;mm.col=m[j-1].col;
}
//push(&st,mm);
if(err) break;
}
ps++;
}while(!st_empty(st));
if(err)
printf("error\n");
else
printf("%ld\n",mul);
}
return 0;
}
Top
22 楼nanangerile（闲）回复于 2006-06-13 00:07:10 得分 0
upTop
23 楼softj（天地客人<最近很迷茫>）回复于 2006-06-14 16:00:14 得分 0
有意思,UPTop
