（二）高斯消元
高斯消元能在O(𝑛^3)的时间复杂度内求解n个方程，n个未知数的多元线性方程组，即
对增广矩阵做初等行列变换，变成一个行最简阶梯型矩阵（线性代数）
- 对某一行（列）乘以一个非零的数
- 交换两行（列）
- 将一行（列）的若干倍加到另一行（列）
解的情况有三种
- 无解，系数矩阵秩不等于增广矩阵的秩
- 有无穷多解，系数矩阵秩等于增广矩阵的秩，且小于n
- 有唯一解，系数矩阵秩等于增广矩阵的秩，且等于n
高斯消元算法步骤：
从列开始，循环枚举处理每一列
-
找到该列绝对值（使用
中的fabs函数）最大的一行，如果最大的绝对值为0，说明当前列已经化简好了，此重循环（列）跳出进行下一列处理 这里就可以区分出后续的r是否++，以此判断唯一解 与 无穷解+无解
-
将这一行换到最上面
循环交换两行的各个元素
-
将该行第一个数变成1
每一行的各个元素，从后往前除以该行的首元素
-
用当前行将下面所有行的当前列消成0
用下面每一行每一列的元素-当前行的每一个元素*下面每一行当前列的元素
-
固定该行，处理下一行，处理的行数r++
即当前行的位置就固定了
AcWing883. 高斯消元解线性方程组
注：
- 本题采用fabs即浮点绝对值来取绝对值，在判断是否为0时，应为小于一个足够小的数即为0
- 用每一行的最后一列存储解的值
- 最后有唯一解的求解原因更详细说明AcWing 883. 高斯消元解线性方程组 - AcWing
#include <iostream>
#include <algorithm>
#include <cmath> //fabs的头文件
using namespace std;
const int N=110;
const double eps=1e-6;//绝对值小于10^-6即为0
int n;
double a[N][N];//存储增广矩阵
//高斯消元法解线性方程组
int gauss(){
int c,r;//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;
//判断当前列最大绝对值为 0 ，那么这一列所有数都是 0，当前列无需继续化简，结束这轮循环，进入处理下一列
if(fabs(a[t][c])<eps) continue;
//将当前行换到上面第r行（注意随着每一次完整处理都会固定一行，则当前行是换到固定行的下面一行，第一次就换到第一行）
for(int i=c;i<=n;i++) swap(a[t][i],a[r][i]);//从当前行的第c列开始换
//将该行的第c列的数改为1 该行的元素从后往前改
for(int i=n;i>=c;i--) a[r][i]/=a[r][c];
//将下面的行的该列元素消为0
for(int i=r+1;i<n;i++)
if(a[i][c]>eps)//非0才操作 若已经是0的行就没必要操作
//从后往前，当前行的每个数字，都减去对应列 * 行首非0的数字，这样就能保证该行c列数字是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 表示系数矩阵的秩与增广矩阵的秩不等 无解
return 2;
return 1;//否则系数矩阵的秩与增广矩阵的秩相等 且<n 无穷多解
}
//r=n 有唯一解 求解
for(int i=n-1;i>=0;i--)//从最后一行开始倒推解xi
for(int j=i+1;j<n;j++)
/*
j=i+1,i的下一行 下一列的数
a[i][j]表示xj的系数，a[j][n]表示xj
*/
a[i][n]-=a[i][j]*a[j][n];//解存储在最后一列
return 0;
}
int main(){
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<=n;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");//无解
}AcWing884. 高斯消元解异或线性方程组
实现思路：基本思路和上题求解一般的线性方程组一致，只是区别在与本题未知量之间是异或运算，更适合电脑的运算。
高斯消元得到上三角矩阵 1、枚举列 2、找到当前列的非零行 3、非零行换到剩余行的最上面 4、剩余行中除去最上面一行，下面所有行的当前列都消零 判断解的种类 1、无解 2、无穷多解 3、唯一解
#include <iostream>
#include <algorithm>
using namespace std;
const int N=110;
int a[N][N];
int n;
int gauss(){
//消成阶梯型矩阵
int r,c;
for(r=c=0;c<n;c++){//1.枚举列开始
//2.找到剩余行中的非零行 从r行开始(因为上轮循环r++或跳过)
int t=r;
for(int i=r;i<n;i++)
if(a[i][c]){
t=i;
break;
}
//跳出循环
if(a[t][c]==0) continue;//表示当前列没有非零行 直接进入下一列循环
//3.找打了满足的非零行,与剩余行的最上面交换
for(int i=c;i<=n;i++) swap(a[i][r],a[t][i]);
//4.剩余行中的第c列都消为0
for(int i=r+1;i<n;i++)
if(a[i][c]){//非0就消为0
for(int j=c;j<=n;j++)
a[i][j]^=a[r][j];//做异或
}
r++;//已经固定一行 下一轮
}
//5.判断解的情况
if(r<n){
for(int i=r;i<n;i++)
if(a[i][n]) return 2;//无解
return 1;//无穷解
}else{//唯一解
for(int i=n-1;i>=0;i--)
for(int j=i+1;j<n;j++)
a[i][n]^=a[i][j]*a[j][n];//倒推求解
return 0;
}
}
int main(){
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<=n;j++)
cin>>a[i][j];
int res=gauss();
if(res==0){//唯一解
for(int i=0;i<n;i++) cout<<a[i][n]<<endl;
}else if(res==1) puts("Multiple sets of solutions");//无穷多解
else puts("No solution");//无解
return 0;
}