矩阵的幂运算——C语言实现

Answer 1

矩阵的幂运算——C语言实现方式解说如下：

引入

在写离散数学的作业时，题目要求图的邻接矩阵的幂，例如：

像这样的计算没有是枯燥乏味的，所以我决定让计算机去解决它。

矩阵的乘法和幂运算

两个矩阵的乘法仅当第一个矩阵A的列数和另一个矩阵B的行数相等时才能定义。如A是m×n矩阵和B是n×p矩阵，它们的乘积C是一个m×p矩阵C=Cij。

计算情况像这样：

由此我们可以总结出矩阵的乘法和幂运算的一些基本规则：

设矩阵M1，M2，res。

1、能够计算M1*M2的前提是M1的列数等于M2的行数。

2、设res=M1*M2，那么res的行数等于M1的行数，res的列数等于M2的列数。

如何实现

我们用一个结构体来表示一个矩阵，结构体中的matrix指向一个一维指针数组，一维指针数组中的每一个元素是指向一个整型的int数组，通过这样让matrix指针能够访问表示矩阵的二维数组的每一个元素。

计算矩阵的幂运算可以通过递归来实现：

假设要计算矩阵M的n次幂。

1、n为偶数，要计算M的n次幂，那么可以先计算M的n2次幂，再将两个M的n2次幂相乘就可以得到M的n次幂。

而计算M的n2次幂也同样可以利用前面的逻辑进行计算，也就是说可以通过递归来计算M的n次幂。

2、n为奇数，那么n+1为偶数，那么可以通过①中的方法先计算M的（n+1）/2次幂，再用矩阵的乘法将结果和矩阵M相乘即可得到M的n+1次幂。

代码实现

从上面的推理可以知道我们需要实现以下功能：

1、创建矩阵。

2、矩阵的乘法。

3、矩阵的幂运算。

而且我们可以知道矩阵的幂运算是需要用到矩阵的乘法的，当计算矩阵的奇数次幂时需要用到矩阵的乘法。

由于矩阵的幂运算通过递归进行，那么在计算过程中一些矩阵对接下来的计算无用时，我们需要把它释放掉，防止出现内存泄漏，因此还需要实现。

4、矩阵的释放。

这里我给出我的代码成果：

代码测试

对照上面的测试用例，可以发现是完全符合的。获取代码。

以上就是矩阵的幂运算的全部内容，希望对你有帮助。