15.高斯消元解线性方程组

 

 高斯消元可以在O(n ^ 3)的时间复杂度内，求解一个包含n个方程和n个未知数的多元线性方程组

 解有三种情况

 预备知识：线性代数矩阵的初等行变换，转化成最短阶梯形矩阵

高斯消元就是把一个系数矩阵变换成上三角的形式

 高斯消元涉及到的线代知识不多，秩之类的不涉及

只用最基础的线代知识

无解的情况：不完美阶梯形时，某一行出现了左边没有未知数，右边非零的情况。0 = ？这种情况，无解

 无穷多解的情况：不完美阶梯形时，出现很多0 = 0的方程，无穷多组解

 唯一解的情况：完美的上三角阶梯形矩阵，第一行n个未知数，第二行n - 1个，第n行1个未知数

、

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
const double eps = 1e-6; //判断是否是0
int n;
double a[N][N]; //用double存
int gauss() {
    int c, r;
    //c表示枚举的每一列
    //r表示行
    for (c = 0, r = 0; c < n; c++) {
        int t = r; //t表示当前这一列绝对值最大的那一行
        for (int i = r; i < n; i++) { //找到当前这一列，绝对值最大的那一行
            if (fabs(a[i][c]) > fabs(a[t][c])) {
                t = i;
            }
        }
        if (fabs(a[t][c]) < eps) { //如果当前这一列是0了
            continue;
        }
        for (int i = c; i <= n; i++) { //换到最上面
            swap(a[t][i], a[r][i]);
        }
        for (int i = n; i >= c; i--) { //变成1，倒着来
            a[r][i] /= a[r][c];
        }
        for (int i = r + 1; i < n; i++) { //把下面的都变为0
            if (fabs(a[i][c]) > eps) { //已经是0就不操作
                for (int j = n; j >= c; j--) {
                    a[i][j] -= a[r][j] * a[i][c];
                }
            }
        }
        r++;
    }
    //已经变好了
    if (r < n) { //如果不到n个方程，不是唯一解
        for (int i = r; i < n; i++) {
            if (fabs(a[i][n]) > eps) { //如果出现了0 = ?的情况
                return 2; //无解
            }
        }
        return 1; //无穷多解
    }
    for (int i = n - 1; i >= 0; i--) { //最后一步，倒着把答案推出来
        for (int j = i + 1; j < n; j++) {
            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 == 0) { //唯一解
        for (int i = 0; i < n; i++) {
            cout << fixed << setprecision(2) << a[i][n] << endl;
        }
    } else if (t == 1) { //无穷多解
        cout << "Infinite group solutions" << endl;
    } else { //无解
        cout << "No solution" << endl;
    }
    return 0;
}