> For the complete documentation index, see [llms.txt](https://wandersofb.gitbook.io/blog/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wandersofb.gitbook.io/blog/suan-fa/shu-xue/gao-si-xiao-yuan.md).

# 高斯消元

学过线代的都知道，把增广矩阵转化为行阶梯型矩阵，然后判断解的情况（无解、无穷解、唯一解），即可。但高斯消元代码涉及到二维比较难理解。高斯消元可以用来求线性多元方程组。

**线性多元方程组**

例如该方程组

$$
\begin{cases} a\_{11}x\_1 + \&a\_{12}x\_2 + \cdots + \&a\_{1n}x\_n = \&b\_1\ a\_{21}x\_1 + \&a\_{22}x\_2 + \cdots + \&a\_{2n}x\_n = \&b\_2\ \vdots &\vdots &\vdots &\vdots\ a\_{n1}x\_1 + \&a\_{n2}x\_2 + \cdots + \&a\_{nn}x\_n = \&b\_2\ \end{cases}
$$

其增广矩阵为

$$
\left\[ \begin{array} {c c c c| c} a\_{11} & a\_{12} & \cdots & a\_{1n} & b\_{1}\ a\_{22} & a\_{22} & \cdots & a\_{2n} & b\_{2}\ \vdots & \vdots & \vdots & \vdots & \vdots\ a\_{n1} & a\_{n2} & \cdots & a\_{nn} & b\_{n}\ \end{array} \right]
$$

* 对增广矩阵进行初等行变换转化为行阶梯型矩阵
  * 对列进行枚举
  * 找到当前列的绝对值最大的那一行
  * 把此行交换到上面（并非第一行，而是还未确定）的行
  * 将该行第一个数置为1，其他数随之变化。
  * 将下面所有行的当前列的值变为零，其他列随着变化。

行阶梯型矩阵

$$
\begin{bmatrix} a\_{11} & a\_{12} & \cdots & a\_{1n} & b\_1\ & a\_{22} & \cdots & a\_{2n} & b\_2\ & & & \vdots & \vdots\ & & & a\_{nn} & b\_n \end{bmatrix}
$$

```cpp
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N =  110;
const double eps = 1e-8;
double p[N][N];

int gauss(int n){
    int c, r;
    for (c = 0, r = 0; c < n; c ++){
        int t = r;
        for (int i = r; i < n; i ++)
            if (fabs(p[i][c]) > fabs(p[t][c]))    
                t = i;
            
        if (fabs(p[t][c]) < eps) continue;
                
        for (int i = c; i <= n; i ++)
            swap(p[r][i], p[t][i]);
        for (int i = n; i >= c; i --)
            p[r][i] /= p[r][c];
        for (int i = r + 1; i < n; i ++)
            if (fabs(p[i][c]) > eps)
                for (int j = n; j >= c; j --)
                    p[i][j] -= p[r][j] * p[i][c];
                    
        r ++;
    }
    
    if (r < n){
        for (int i = r; i < n; i ++)
            if (fabs(p[i][n]) > eps)
                return 2;
        return 1;
    }
    
    for (int i = n - 1; i >= 0; i --)
        for (int j = i + 1; j < n; j ++)
            p[i][n] -= p[i][j] * p[j][n];
        
    return 0;
}


int main(){
    int n ; cin >> n;
    for (int i = 0; i < n; i ++)
        for (int j = 0; j <= n; j ++)
            cin >> p[i][j];
    int t = gauss(n);
    if (t == 0)
        for (int i = 0; i < n; i ++){
            if (fabs(p[i][n]) < eps) p[i][n] = 0;
            printf("%.2lf\n", p[i][n]);
        }
    else if (t == 1) puts("Infinite group solutions");
    else puts("No solution");
    
}
```

**时间复杂度**

观察 for 循环可知，最高循环为三层，其时间复杂度最坏为 $$O(n^3)$$。

#### 异或线性方程组