高斯消元
高斯消元解线性方程组
- 通过初等行变换把增广矩阵化为阶梯型矩阵，并回代得到方程的解
- 适用于求解 包含 \(n\) 个方程，\(n\) 个未知数的多元线性方程组
前置知识：初等行（列）变换
- 把某一行乘一个非00的数 (方程的两边同时乘上一个非00数不改变方程的解)
- 交换某两行 (交换两个方程的位置)
- 把某行的若干倍加到另一行上去 （把一个方程的若干倍加到另一个方程上去）
算法步骤：
枚举每一列c
1. 找到当前列绝对值最大的一行
2. 用初等行变换(2) 把这一行换到最上面（未确定阶梯型的行，并不是第一行）
3. 用初等行变换(1) 将该行的第一个系数变成 1 （其余所有的系数依次跟着变化）
4. 用初等行变换(3) 将下面所有行的当前列的值变成 0
时间复杂度：\(O(N^3)\)
#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 col, row;
// 枚举每一列
for (col = 0, row = 0; col < n; col ++ ) {
// 1. 找到当前这一列绝对值最大的系数所在的行号
int maxRow = row;
for (int i = row; i < n; i ++ )
if (fabs(a[i][col]) > fabs(a[maxRow][col]))
maxRow = i;
// 如果这一列最大系数的绝对值是0，则该列全为0，所以无需计算，继续下一列，而行数仍然不变
if (abs(a[maxRow][col]) < eps) continue;
// 2. 将该行换到所有未确定的行的最上面(第row行)，由于是上三角矩阵形式，所以从第一个非零的系数开始交换
for (int i = col; i < n + 1; i ++ ) swap(a[maxRow][i], a[row][i]);
// 3. 将最上行的第一个系数化为1，即行内每个系数除以第一个系数
for (int i = n; i >= col; i -- ) a[row][i] /= a[row][col];
// 4. 将下面所有行的第col列化为0（消元）
for (int i = row + 1; i < n; i ++ )
// 判断如果非零再进行操作
if (fabs(a[i][col]) > eps)
for (int j = n; j >= col; j -- )
a[i][j] -= a[row][j] * a[i][col];
// 换上去并固定了一行系数，继续处理下一行
row ++;
}
// 上三角阶梯形矩阵行数小于n，由克拉默法则，系数矩阵行列式等于0，则方程组无解或有无穷多解
if (row < n) {
// 如果出现了左边 = 0， 右边 != 0 的情况，即无解
// row < n，则第row行至第n-1行都是0，所以从row行开始判断
for (int i = row; i < n; i ++ )
// a[i][n]即位增广矩阵第i行第n列的值，
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 ++ ) // 每次用当前行之下的所有行来计算x
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 == 2) puts("No solution");
// 有无穷多解
else if (t == 1) puts("Infinite group solutions");
// 有唯一解
else
for (int i = 0; i < n; i ++ ) {
if (fabs(a[i][n]) < eps) a[i][n] = 0; // 去掉输出 -0.00 的情况
printf("%.2lf\n", a[i][n]);
}
return 0;
}
高斯消元解异或线性方程组
异或运算有一个别名"不进位的加法"，可以利用高斯消元的方法求解异或线性方程组。
算法思想：
- 消成上三角矩阵
- 枚举列
- 找非零行
- 交换
- 下面消零
- 判断
- 完美：唯一解
- 有矛盾：无解
- 无矛盾：无穷解
时间复杂度：\(O(N^3)\)
#include <iostream>
using namespace std;
const int N = 110;
int n;
int a[N][N]; // 系数矩阵
int gauss()
{
int c, r;
// 枚举每一列
for (c = r = 0; c < n; c ++ ) {
// 找非零行
int t = r;
for (int i = r; i < n; i ++ )
if (a[i][c]) {
t = i;
break; // 找到一个非零行即可
}
if (!a[t][c]) continue; // 如果找到的这一行是0，则这一列不需要消元，看下一列
// 交换到未确定部分的顶行
for (int i = c; i <= n; i ++ )
swap(a[t][i], a[r][i]);
// 对下面每一行进行消元
for (int i = r + 1; i < n; i ++ )
if (a[i][c]) // 如果非0则需要消元
for (int j = n; j >= c; j -- )
a[i][j] ^= a[r][j];
// 当前行处理完毕，位置固定，处理下一行
r ++;
}
if (r < n) {
// 左边为0 右边不为0 无解
for (int i = r; i < n; i ++ )
if (a[i][n])
return 2;
// 无穷多解
return 1;
}
// 将方程右边进行回代求解
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];
// 上一行等价于 if (a[i][j]) a[i][n] ^= a[j][n];
// 如果是0 就不用下面的a[j][j] 来^a[i][j]了
// 如果不是0 才需要用第j行第j列a[j][j]来^第i行第j列a[i][j]
// 进而进行整行row[i]^row[j] 间接导致 a[i][n]^a[j][n]
// 有唯一解
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 ++ ) cout << a[i][n] << endl;
}
// 有无穷多解
else if (t == 1) puts("Multiple sets of solutions");
// 无解
else puts("No solution");
return 0;
}