文章目录
前言
一、高斯消元
二、例题，代码
AcWing 883. 高斯消元解线性方程组
本题解析
AC代码
AcWing 884. 高斯消元解异或线性方程组
本题解析
AC代码
三、时间复杂度
前言
复习acwing算法基础课的内容，本篇为讲解数学知识：高斯消元，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。
一、高斯消元
高斯消元运用于去解多元函数的解，如下图所示：
利用高斯消元，我们可以在很短的时间内去判断这个多元方程是否有解，如果是由唯一组解的情况下可以解出这一解，高斯消元的计算过程类似于线性代数，如何去解这个问题，我们在下文会根据题目进行一些规定和分析.
二、例题，代码
AcWing 883. 高斯消元解线性方程组
本题链接：AcWing 883. 高斯消元解线性方程组
本博客提供本题截图：
本题解析
首先来说明以下本题的几个需要声明的量和值，然后再介绍高斯消元：
我们用二维数组a去存储整个方程组，注意我们在做除法的时候因为我们表达一个分数比较复杂，所以这里用的是小数，用小数就有了精度缺失这个问题，比如1 / 3 * 3这个结果应该是等于1的，但是我们表示成小数之后运算结果为0.999...，故我们在表达0这个量的时候，因为精度问题，我们可以用一个特别小的数去当0，当运算结果小于我们设定的这个十分小的数的时候，我们就默认为0，在本题中，我们用const double eps = 1e-6;去表达这个无穷小的数.本题中，我们用c去表示列，用r去表示行
我们在解的过程中，规定如下解法：
把整个多元函数集化简成如下图所示的情况：（空白部分均为0）
如果最后的化简结果如上图所示，那么就有唯一的一组解；
如果最后化简得到的式子中有0 = 非零这种特殊情况的，没有解；
如果最后化简得到的式子中有0 = 0这种情况的，有无数组解.
下面来规定几个高斯消元的操作（线代中的计算方法）
把某一行乘一个非零的数
交换某两行
将某行的若干倍加到另一行上
下面来正式介绍高斯消元在代码上如何实现求解的各种操作：
高斯消元分以下几个步骤：
枚举每一列c：
1.找到绝对值最大的一行
for (c = 0, r = 0; c < n; c ++ ) { int t = r; for (int i = r; i < n; i ++ ) if (fabs(a[i][c]) > fabs(a[t][c])) t = i; if (fabs(a[t][c]) < eps) continue;//如果最大的一行都已经是0了，那么就没必要操作这一列了，直接continue即可 }
2.将该行换到最上面
for (int i = c; i < n + 1; i ++ ) swap(a[t][i], a[r][i]);
3.将该行第一个数变成1
这步的操作其实就是让该行的每一列元素都除以第一个不为0的列的值，这里需要注意必须倒着进行，否则如果第一个数除以本身的话，后面的数处理起来就比较麻烦了，解决方法可以是存储一下第一个数，但是没有这个必要，倒着进行for循环即可解决这个问题
for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c];
4.将下面所有行的第c列消成0
这里注意我们已经让第r行，第c列的数变成1了，所以我们在消后面几行的时候，只需要让第i行第j列的元素减去该行第c列元素的值乘第r行j列元素的值
for (int i = r + 1; i < n; i ++ ) if (fabs(a[i][c]) > eps) //这个数不是0再进行操作 for (int j = n; j >= c; j -- ) a[i][j] -= a[r][j] * a[i][c];
下面来说说求解的过程：
按照常理来说，我们应该枚举到最后，我们的行数r应该是枚举到最后一行了，如果没有，证明这里有特殊情况出现了：即没有解或者有无穷多组解，下面我们来讨论这种情况：
if (r < n) { for (int i = r; i < n; i ++ ) if (fabs(a[i][n]) > eps) //即等式左边全部为0，但是等式右边的值不为0 return 2; //证明无解 return 1; //证明有无穷多组解 }
接下来看一下有解的代码，并计算解：
从下往上进行代值，得到方程的解，这里建议自己动手模拟一下这个过程
for (int i = n - 1; i >= 0; i -- ) for (int j = i + 1; j < n; j ++ ) a[i][n] -= a[j][n] * a[i][j]; return 0; //证明有解
AC代码
#include <iostream> #include <algorithm> #include <cmath> using namespace std; const int N = 110; const double eps = 1e-6; int n; double a[N][N]; int gauss() { int c, r; for (c = 0, r = 0; c < n; c ++ ) { int t = r; for (int i = r; i < n; i ++ ) if (fabs(a[i][c]) > fabs(a[t][c])) t = i; if (fabs(a[t][c]) < eps) continue; for (int i = c; i < n + 1; i ++ ) swap(a[t][i], a[r][i]); for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c]; for (int i = r + 1; i < n; i ++ ) if (fabs(a[i][c]) > eps) for (int j = n; j >= c; j -- ) a[i][j] -= a[r][j] * a[i][c]; r ++ ; } if (r < n) { for (int i = r; i < n; i ++ ) if (fabs(a[i][n]) > eps) return 2; return 1; } for (int i = n - 1; i >= 0; i -- ) for (int j = i + 1; j < n; j ++ ) a[i][n] -= a[j][n] * a[i][j]; return 0; } int main() { cin >> n; for (int i = 0; i < n; i ++ ) for (int j = 0; j < n + 1; j ++ ) cin >> a[i][j]; int t = gauss(); if (t == 0) { for (int i = 0; i < n; i ++ ) printf("%.2lf\n", a[i][n]); } else if (t == 1) puts("Infinite group solutions"); else puts("No solution"); return 0; }
