首页 > 代码库 > UVa 442 矩阵链乘及scanf说明符中的\n
UVa 442 矩阵链乘及scanf说明符中的\n
题目:计算题给矩阵相乘次序所需的相乘次数。 我们已知的m*n和n*k矩阵相乘,得到的是m*k矩阵,但需要的相乘次数是m*n*k(开始当成了m*k %>_<%)。evaluate,求值
思路:每个矩阵用结构体表示,有名字、行、列、需要计算的次数。矩阵相乘的过程用栈来模拟。遇到左括号(,压栈这是自然的。遇到一个矩阵时,检查栈顶,如果栈顶元素是左括号,则压栈,否则就是矩阵,则比较栈顶矩阵和输入矩阵是否匹配,如果匹配则修改栈顶矩阵的列、计算次数,这样输入矩阵对栈顶进行了修改,相当于完成了相乘,这时栈顶矩阵已经是它们相乘的结果矩阵了。遇到右括号),需要将栈顶矩阵和其下面的左括号出栈,再将出栈的矩阵入栈。(这里可以保证矩阵不会连续存于栈里的,因为每次矩阵入栈时,如果栈顶元素是矩阵,就会进行相乘,只留结果矩阵的。)该矩阵再入栈时,需要坚持栈顶元素是否为矩阵,若为矩阵,则进行相乘,这里在修改计算次数时,不仅要加上左矩阵的次数、m*n*k,还有加上右矩阵结构体中的计算次数。 其他的还有一些边界条件需要注意的,比如这里栈顶指针top初始为0,以及一直保持着栈顶指针指向栈顶元素,top==0表示栈为空,top==n表示栈中有n个元素。
这里,在用矩阵名字来索引其在结构体数组中的位置时,增加了一个索引矩阵index2(index是c/c++的函数。。。)。即index2[name-‘A‘]表示的是name矩阵在结构体数组a中的位置。这个在输入矩阵时进行维护即可。 另外,由于有多组数据,在对每组数据进行处理时,应对结构体数组副本进行处理,所以用了memcpy对结构体数组进行了复制。
scanf("...\n"); scanf 说明符中的 \n 很特别,不是要求输入一个回车换行。它过滤空格、制表符、回车等空白符输入,在scanf("%d\n",&i); printf("%d\n",i);中,输入一个数后不会立即显示,要等再接收到一个非空白符的输入,scanf语句的输入才结束。参考:这里
//注释是C99中的。
Code:
//#define LOCAL #include<stdio.h> #include<string.h> struct matrix { char name; int m,n,num; }; matrix a[30]; matrix b[30]; int index2[30]; //额,index是C/C++的函数 char stack[100]; int main() { #ifdef LOCAL freopen("442.in","r",stdin); freopen("442.out","w",stdout); #endif int n; scanf("%d",&n); getchar(); for(int i=0;i<n;++i) { scanf("%c%d%d",&b[i].name,&b[i].m,&b[i].n); b[i].num=0; index2[b[i].name-‘A‘]=i; getchar(); } /*for(int i=0;i<n;++i) { printf("%c %d %d\n",b[i].name,b[i].m,b[i].n); printf("%c:%d\n",b[i].name,index[b[i].name-‘A‘]); } */ char c; while((c=getchar())!=EOF) { memset(stack,0,sizeof(stack)); memcpy(a,b,sizeof(b)); //for(int i=0;i<n;++i){ printf("%c %d %d\n",a[i].name,a[i].m,a[i].n);printf("%c:%d\n",a[i].name,index[a[i].name-‘A‘]);} int top=0;//top等于0时栈为空 int flag=1; while(c!=‘\n‘) { if(c==‘(‘) stack[++top]=c; else if(c==‘)‘) { char d=stack[top--]; stack[top]=d; if(top-1>0 && stack[top-1]!=‘(‘&&stack[top-1]!=‘)‘) { int yix=index2[stack[top]-‘A‘],zix=index2[stack[top-1]-‘A‘]; if(a[zix].n!=a[yix].m) flag=0; else { a[zix].n=a[yix].n; a[zix].num+=a[zix].m*a[yix].n*a[yix].m+a[yix].num; top--; } } } else {//读入字母 if(stack[top]==‘(‘) stack[++top]=c; else if(top==0) stack[++top]=c; else { char d=stack[top]; int dix=index2[d-‘A‘],cix=index2[c-‘A‘]; if(a[dix].n!=a[cix].m) flag=0; else { a[dix].n=a[cix].n; a[dix].num=a[dix].num+a[dix].m*a[cix].n*a[cix].m+a[cix].num; } }//else }//else if(flag==0) while((c=getchar())!=‘\n‘); else c=getchar(); }//whilec //printf("%d\n",stack[top]); if(flag==0) printf("error\n"); else printf("%d\n",a[index2[stack[top]-‘A‘]].num);//这里不是a[top],也不是a[stack[top]]。。。 }//while return 0; }