# 高斯消元

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

**线性多元方程组**

例如该方程组

$$
\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)$$。

#### 异或线性方程组


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wandersofb.gitbook.io/blog/suan-fa/shu-xue/gao-si-xiao-yuan.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.