4.1.4 数值矩阵运算
在利用计算机解决工程领域和其他领域问题时经常要对矩阵进行计算。数值矩阵通常用二维数组表示，假设整数矩阵的行数为m、列数为n，则可用整数数组a[m][n]来存储，其中a[i][j]代表矩阵中第i+1行、第j+1列的元素。由于存取矩阵中任何一个数字，可根据数组下标直接找到，因此存储数值矩阵的二维数组属于典型的直接存取类线性表。
利用二维数组可进行许多数值矩阵的运算。例如，判别布尔矩阵的某些特性（如每行、每列中true的元素个数是否都为偶数）；矩阵转置（行列对换）；两个同规模的数值矩阵相加或相减；两个规模分别为m×n和n×l的数值矩阵A和B相乘，乘积存入规模为m×l的数值矩阵C；等等。
【4.1.4.1 Error Correction】
当一个布尔矩阵的每行和每列总和为偶数时，该布尔矩阵具有奇偶均势的特性，即包含偶数个1。例如，一个4×4具有奇偶均势特性的矩阵：
1 0 1 0
0 0 0 0
1 1 1 1
0 1 0 1
行的总和是2、0、4和2。列的总和是2、2、2和2。
请编写一个程序，输入矩阵，并检查其是否具有奇偶均势特性。如果没有，程序还要检查是否可以通过仅改变矩阵中的一个数字使矩阵具有奇偶均势特性。如果不能，则把矩阵归类为Corrupt。
输入
输入包含一个或多个测试用例，每个测试用例的第一行是一个整数n（n<100），表示矩阵的大小。后面的n行，每行n个数，矩阵中的每个数不是0就是1。输入以n为0结束。
输出
对于输入的每个矩阵，输出一行。如果该矩阵具有奇偶均势特性，则输出“OK”。如果奇偶均势特性可以通过改变一个数字产生，则输出“Change bit(i,j)”，其中i是要改变数字所在的行，j是要改变数字所在的列；否则输出“Corrupt”。
试题来源：Ulm Local Contest 1998
在线测试：POJ 2260，ZOJ 1949
试题解析
设矩阵为a，其中i行的数的总和为row[i]，j列的数的总和为col[j]。
首先，在输入矩阵为a的同时统计各行各列的数的总和row和col。
然后，计算数的总和为奇数的行数cr与数的总和为奇数的列数cc，并分别记下最后数的总和为奇数的行序号i和最后数的总和为奇数的行序号j（若row[k] & 1=1，则cr++，i=k；若col[k] & 1==1，则cc++，j=k，0≤k≤n-1）。
最后，判断矩阵a的奇偶均势特性：
1）若n行、n列的数的和都为偶数（cc==0且cr==0），则矩阵a具有奇偶均势特性；
2）若矩阵a仅有1行和1列的数的总和为奇数（cc==1且cr==1），并设这一行列为i行和j列，则说明(i,j)中的数字使得i行和j列的数和为奇数，将其取反可恢复矩阵a的奇偶均势特性。注意，数组a中行列从0开始编号，因此应输出（i+1,j+1）；
3）出现其他情况，矩阵a归类为Corrupt。
参考程序
#include <stdio.h> //预编译命令
#include <assert.h>
#define MAXN 512 //定义矩阵容量
int n; //矩阵规模
int a[MAXN][MAXN], row[MAXN], col[MAXN]; //矩阵为a，其中i行的数和为row[i], j
//列的数和为col[j]
FILE *input; //定义输入文件的指针变量
int read_case() //输入矩阵
{
int i,j;
fscanf(input,"%d",&n); //输入矩阵大小
if (n==0) return 0; //若输入结束，则返回0
for (i=0; i<n; i++) //输入矩阵并返回1
for (j=0; j<n; j++)
fscanf(input,"%d",&a[i][j]);
return 1;
}
void solve_case() //判断矩阵的奇偶均势特性
{
int cc,cr,i,j,k;
for (i=0; i<n; i++) //初始时各行各列的数的总和为0
row[i] = col[i] = 0;
for (i=0; i<n; i++) //统计各行各列的数的总和
for (j=0; j<n; j++)
{
row[i] += a[i][j];
col[j] += a[i][j];
}
cr = cc = 0;
for (k=0; k<n; k++) //累计数和为奇数的行数cr并记下最后数和为奇数的
//行序号i；累计数和为奇数的列数cc并记下最后数和为奇数的列序号j
{
if (row[k]&1) { cr++; i=k; }
if (col[k]&1) { cc++; j=k; }
}
if (cc==0 && cr==0) printf("OK\n"); //若所有行和列的数和都为偶数，则输出“OK”；若
//仅有1行和1列的数和为奇数，则可通过（i+1, j+1)位取反恢复矩阵奇偶均势特性；否则矩
//阵的特性为Corrupt
else if (cc==1 && cr==1) printf("Change bit (%d,%d)\n",i+1,j+1);
else printf("Corrupt\n");
}
int main()
{
input = fopen("error.in","r"); //输入文件名串与输入文件变量连接
assert(input!=NULL); //初始时输入文件为非结束状态
while(read_case()) solve_case(); //反复输入和处理测试数据组，直至输入0为止
fclose(input); //关闭输入文件
return 0;
}
【4.1.4.2 Matrix Chain Multiplication】
假设我们要评价诸如A×B×C×D×E这样的表达式，其中A、B、C、D和E是矩阵。因为矩阵乘法满足结合律，所以乘法执行的次序可以是任意的。然而，相乘的次数则依赖于运算顺序。
例如，设A是一个50×10矩阵，B是一个10×20矩阵，C是一个20×5矩阵。计算A×B×C有两种不同的方法，即(A×B)×C和A×(B×C)。第一种方法有15 000次相乘，但第二种方法只有3500次相乘。
请你编写一个程序，对给出的运算顺序，确定需要相乘的次数。
输入
输入包含两个部分：矩阵列表和表达式列表。
输入的第一行给出一个整数n(1≤n≤26)，表示在第一部分中矩阵的个数。后面的n行每行包含一个大写字母，表示矩阵的名称；以及两个整数，表示矩阵的行数和列数。
输入的第二部分按下述语法说明（以扩展的巴科斯范式（EBNF）给出）：
SecondPart = Line { Line }
Line = Expression
Expression = Matrix | "(" Expression Expression ")"
Matrix = "A" | "B" | "C" | ... | "X" | "Y" | "Z"
输出
对于在输入的第二部分给出的每个表达式，输出一行。如果由于矩阵的不匹配使表达式运算错误，则输出“error”；否则输出一行，给出计算该表达式需要相乘的次数。
试题来源：Ulm Local Contest 1996
在线测试：POJ 2246，ZOJ 1094
提示
两个规模分别为m×n和n×l的数值矩阵A和B相乘，乘积存入规模为m×l的数值矩阵C，其中C中每个元素
(0≤i≤m-1，0≤j≤l-1)，即产生矩阵C中每个元素的相乘的次数为n，矩阵C中一共有m×l个元素，所以总的相乘的次数为m×n×l。如试题描述，A是一个50×10的矩阵，B是一个10×20的矩阵，C是一个20×5的矩阵。计算A×B的相乘的次数为50×10×20=10 000，A×B是一个50×20的矩阵；(A×B)×C的相乘的次数为50×20×5=5000；所以(A×B)×C总共有10 000+5000=15 000次相乘。
设e为表达式的字符数组，p为e的字符指针；将相乘次数mults、乘积矩阵的行数rows、列数cols组成一个结构体并将其定义为类triple。计算表达式的相乘次数的函数expression()、目前得出的乘积矩阵t、待乘的两个矩阵t1和t2都为类triple的实例。
我们在输入时，计算出各大写字母表示的矩阵的行数rows[c]和列数cols[c]('A'≤c≤'Z')；然后反复输入表达式。每输入一个表达式e，将e的字符指针p和出错标志初始化为0，通过调用函数expression()计算乘积矩阵t：
1）若当前字符为“(”，则字符指针p+1，递归计算括号内的表达式t1和t2（t1=expression();t2=expression()），字符指针p+1。若t1的列数不等于t2的行数（t1.cols!=t2.rows)，则设失败标志（error=1）；否则计算t1相乘t2后的乘积矩阵t（t.rows=t1.rows;t.cols=t2.cols;t.mults=t1.mults+t2.mults+t1.rows*t1.cols*t2.cols）
2）若当前字符为字母，则记下对应矩阵的行列数，相乘次数设为0（t.rows=rows[e[p]];t.cols=cols[e[p]];t.mults=0），字符指针p+1。
最后，返回乘积矩阵t。显然调用expression()函数后，若error==1，则表明表达式运算错误；否则需要相乘的次数为t.mults。
参考程序
#include <stdio.h> //预编译命令
typedef struct {int mults; int rows; int cols;} triple; //定义表达式的triple为一
//个包含相乘次数mults、矩阵的行数rows和列数cols的结构体
int rows[256],cols[256]; //变量名为c的矩阵的行数为rows[c]，列数为cols[c]
char e[100]; // 存储表达式的字符数组
int p; // e的字符指针
char error; //出错标志
triple expression() //计算表达式e对应的乘积矩阵
{
triple t; //乘积矩阵
if (e[p]=='(') //若当前字符为'('，则字符指针+1，并取出括号
//内的表达式t1和t2
{
triple t1,t2;
p++;
t1 = expression();
t2 = expression();
p++; //字符指针+1
if (t1.cols!=t2.rows) error = 1;//若t1的列数不等于t2的行数，则设失败标志
t.rows = t1.rows; //计算乘积矩阵的行列数和相乘次数
t.cols = t2.cols;
t.mults = t1.mults+t2.mults+t1.rows*t1.cols*t2.cols;
}
else //若当前字符为矩阵名，则记下矩阵的行列数，相乘
//次数设为0
{
t.rows = rows[e[p]];
t.cols = cols[e[p]];
t.mults = 0;
p++; //字符指针+1
}
return t; //返回乘积矩阵
}
main()
{
FILE* input = fopen("matrix.in","r"); //定义输入文件的指针变量，并将文件名串与该变量
//连接
char c;
int i,n,ro,co;
triple t; //乘积矩阵t为类triple
fscanf(input,"%d%c",&n,&c); //读矩阵个数
for (i=0; i<n; i++) //读n个矩阵的信息
{
fgets(e,99,input);
sscanf(e,"%c%d %d",&c,&ro,&co); //读第i个矩阵的名称、行数和列数
rows[c] = ro;
cols[c] = co;
}
while (1) //输入和处理每个表达式
{
fgets(e,99,input); //输入表达式
if (feof(input)) break; //若读至文件结束标志，则退出循环
p = error = 0; //字符指针和出错标志初始化
t = expression(); //计算表达式e对应的乘积矩阵
if (error) puts("error"); //若出错，则输出失败信息；否则输出相乘次数
else printf("%d\n",t.mults);
}
fclose(input); //关闭输入文件
return 0;
}