数论常用内容——高斯消元

本文主要是介绍数论常用内容——高斯消元，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

高斯消元法

数学上，高斯消元法，是线性代数中的一个算法，可用来为线性方程组求解

高斯消元法求解线性方程组时，首先需要根据方程，列出增广矩阵。然后再利用初等行变换把增广矩阵转换为行阶梯阵，然后回代求出方程的解

高斯消元法的应用

1、找出可逆矩阵的逆矩阵

设A为一个N*N的可逆矩阵，将一个N*N单位矩阵I放在A的右边，形成一个N*2N的分块矩阵 B = [A,I] 。经过高斯消元法的计算程序后，矩阵B的左边原来A的位置会变成一个单位矩阵I ，而逆矩阵A ^(-1) 会出现在原来I的位置。

注：假如高斯消元法不能将A化为三角形的格式，那就代表A 是一个不可逆的矩阵。

2、算出矩阵的秩

将增广矩阵进行高斯消元变换，统计非零行行数（即最后一列的非零数字的个数），即为该矩阵的秩

高斯消元的编程思路及代码实现

先来介绍思路：

把方程组转换成增广矩阵。
利用初等行变换来把增广矩阵转换成行阶梯阵：
枚举k从0到equ – 1，当前处理的列为col(初始为0) ，每次找第k行以下(包括第k行)，col列中元素绝对值最大的列与第k行交换。如果col列中的元素全为0，那么则处理col + 1列，k不变。
转换为行阶梯阵，判断解的情况：
① 无解：当方程中出现(0, 0, …, 0, a)的形式，且a != 0时，说明是无解的。
② 唯一解：条件是k = equ，即行阶梯阵形成了严格的上三角阵。利用回代逐一求出解集。

下面放出代码

首先是对于整数的高斯消元

代码中有详细注释，对于上面思路理解不深刻的可以看一下代码注释

const int MAXN=50;int a[MAXN][MAXN];//增广矩阵
int x[MAXN];//解集
bool free_x[MAXN];//标记是否是不确定的变元void Debug(void){int i, j;for (i = 0; i < equ; i++){for (j = 0; j < var + 1; j++){cout << a[i][j] << " ";}cout << endl;}cout << endl;
}inline int gcd(int a,int b){int t;while(b!=0){t=b;b=a%b;a=t;}return a;
}inline int lcm(int a,int b){return a/gcd(a,b)*b;//先除后乘防溢出
}// 高斯消元法解方程组(Gauss-Jordan elimination).(-2表示有浮点数解，但无整数解，
//-1表示无解，0表示唯一解，大于0表示无穷解，并返回自由变元的个数)
//有equ个方程，var个变元。增广矩阵行数为equ,分别为0到equ-1,列数为var+1,分别为0到var.
int Gauss(int equ,int var){int i,j,k;int max_r;// 当前这列绝对值最大的行.int col;//当前处理的列int ta,tb;int LCM;int temp;int free_x_num;int free_index;for(int i=0;i<=var;i++){x[i]=