矩阵的简单应用.doc

矩阵的简单应用 浙江省余姚中学 韩文弢 关键字 矩阵 矩阵乘法 线性方程组 摘要 矩阵在线性代数中扮演着非常重要的角色，同样也是解决信息学题目的利器。本文通过几个例题展示了矩阵的一些基本运算和操作：矩阵乘法，通过矩阵的基本操作来解线性方程组。 例题1 递推数列(recurrence) 题目描述： 给出一个k阶齐次递推数列的通项公式，以及初始值，求。 输入格式： 第1行 整数和。 第2行 k个整数。 第3行 k个整数。 输出格式： 第1行 一个整数p，是除以10,000的余数。 输入样例： 2 10 1 1 1 1 输出样例： 89 算法分析： 从数据范围可以看出，我们不能一项一项来推算。为了对递推进行加速，我们从一个最简单的例子Fibonacci数列着手。Fibonacci数列的递推公式为，我们令，另外再设一个矩阵A，使得。很容易看出，满足要求。进而，若有，则。经过这样的变换，尽管从表面上看我们仍然需要n步的计算才能得到，但由于矩阵乘法满足结合律，我们可以像计算一个整数的非负整次幂那样通过分治来计算一个矩阵的非负整次幂，从而求出。 扩展至一般情况，若，同样地，我们令，另外再设一个矩阵A，使得。通过比较，我们可以得出。于是，若有，则。这样，我们同样也能用分治的方法来求得。 通过使用矩阵乘法，整个算法的时间复杂度为，空间复杂度为。如果在矩阵相乘时使用Strassen算法，时间复杂度还可以进一步降为。 例题2 图形变换(shape) 题目描述： 平面上有n个点需要依次进行m个变换处理。变换的规则有4种，分别为： 平移(M) 按照向量对点进行平移，即。 缩放(Z) 以原点为参考，按照比例对点进行缩放，即。 翻转(F) 把点按照x轴或者y轴进行翻转，即或。 旋转(R) 使点绕原点旋转a度（a为正时逆时针旋转，为负时顺时针旋转），离原点的距离不变。 其中括号中的字母为该变换的指令代码。编程序依次输出变换后各点的坐标。 输入格式： 第1行 整数和。 第2行至第m+1行 每行代表一个变换指令，为M x y、Z 、F k或者R a，其中均为绝对值不超过10,000的实数，k为0（表示按照x轴翻转）或者1（表示按照y轴翻转）。 第m+2行至第m+n+1行 每行两个实数，表示一个点的坐标，其中均为绝对值不超过10,000的实数。 输出格式： 第1行至第n行 每行两个实数，为变换后点的坐标，保留4位小数。 输入样例： 4 1 M 0 1 Z 0.5 R 45 F 0 2 1 输出样例： 0.0000 1.4142 算法分析： 这一题同样也不能直接模拟。为了使变换加快，我们需要预先求出所有变换叠加效果的计算公式，然后一次性完成各点的变换。 为了使变换公式的形式得到简化，我们把点的坐标写成向量（同时也是一个只有一列的矩阵）的形式。这时，我们可以通过矩阵乘法完成后面3种操作。缩放：，其中；翻转：，其中或；旋转：，其中。问题是采用这种坐标的表达方式我们无法通过矩阵乘法实现平移，那么我们该怎么办呢？ 让我们稍微修改一下坐标的表达方式，令。这时，我们只要令就可以通过来完成平移变换了。其他三个变换矩阵也需要进行一些扩展，即或。如果m个变换所对应的矩阵分别为，我们先计算出总的变换矩阵，那么变换后的坐标所对应的向量。在进行矩阵乘法的时候请注意矩阵之间的位置关系，因为矩阵乘法不满足交换律。 使用矩阵乘法后，整个算法的时间复杂度为，而且如果我们对所有矩阵求转置后再相乘的话，空间复杂度仅为，即。此外，这种方法还可以扩展到三维的情况。 例题3 化学方程式配平(chemeq) 题目描述： 给出一个未配平的化学方程式，要求根据质量守恒定律对其进行配平，不需要考虑化合价问题。 输入格式： 第1行 一个字符串，由字母、数字、加号、等号以及左右小括号组成，表示一个未配平的化学方程式。元素由一个大写字母紧跟若干个（可以为0个）小写字母构成，括号可以嵌套，数字只出现在元素名或右小括号的后面。整个字符串不超过200个字符，包含的数字不超过1,000，并保证在语法上是合法的。 输出格式： 第1行 一个字符串，为配平后的方程式。各项的系数也都保证不超过1,000，且所有系数的最大公约数必须为1，其中系数1必须省略。如果方程式无解，则输出“No solution”；如果有多组不成比例关系的解，则输出“Solution not unique”。 输入样例： Cu+HNO3=Cu(NO3)2+NO+H2O 输出样例： 3Cu+8HNO3=3Cu(NO3)2+2NO+4H2O 算法分析： 在做这道题目的时候，我们必须抛开平时人工配平化学方程式时一切“投机取巧”的方法，而去寻求一种通用的可以通过计算机来实现的算法。我们知道，化学反应遵循质量守恒定律，即反应前后原子的种类和数量保持不变。我们就可以根据这一定