java---高斯消元---线性方程组（每日一道算法2022.9.20）

题目：

输入:
3
1.00 2.00 -1.00 -6.00
2.00 1.00 -3.00 -9.00
-1.00 -1.00 2.00 7.00

输出：
1.00
-2.00
3.00

public class 高斯消元解线性方程组 {
    public static int N = 110, m;
    public static double INF = 1E-6;
    public static double[][] a = new double[N][N];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        m = in.nextInt();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m+1; j++) {
                a[i][j] = in.nextDouble();
            }
        }

        //判断，0有唯一解，1有无数组解，2无解
        int t = gauss();
        if (t == 0) {
            for (int i = 0; i<m; i++) System.out.printf("%.2f\n",Math.abs(a[i][m]) < INF ? 0 : a[i][m]);  //特判避免-0.00
        }
        else if (t == 1) System.out.println("Infinite group solutions");
        else if (t == 2) System.out.println("No solutions");
    }

    //高斯消元
    public static int gauss() {
        //c是column列，r是row行, 每次遍历c列中的所有值，拿到c列中最大绝对值的位置t行
        int c, r;
        for (c = 0, r = 0; c < m; c++) {

            int t = r;
            for (int i = r; i < m; i++){
                if (Math.abs(a[i][c]) > Math.abs(a[t][c])) t = i;
            }

            if (Math.abs(a[t][c]) < INF) continue;              //如果为0，那么就说明当前列全部为0，直接看下一个就行

            for (int i = c; i < m+1; i++) swap(t, r, i);      //将a[t]和a[r]进行交换，也就是将包含最大绝对值的t行和当前最顶端r行进行交换
            for (int i = m; i >= c; i--) a[r][i] /= a[r][c];   //将a[r][i]变为1,也就是这行所有值除以a[r][c],切记要反着更新值，不然数据会错
            for (int i = r + 1; i < m; i++) {                  //从第r行开始，将第c列的所有数都消为0
                if (Math.abs(a[i][c]) > INF) {
                    for (int j = m; j >= c; j--) {
                        a[i][j] -= a[i][c] * a[r][j];      //将每行都减去行首*对应列的数，就能保证：行首 -= 1*行首 = 0
                    }
                }
            }
            
            r++; //换到下一行
         }

        // r小于m说明剩下的方程个数小于m，不存在唯一解，判断是无解还是有无数组解
        if (r < m) {
            for (int i = r; i < m; i++) {
                if (Math.abs(a[i][m]) > INF) return 2;     //也就是如果0等于非0的情况，无解
            }
            return 1;   //有无数组解
        }

        //如果有唯一解，那么倒着消一遍就可以了，也就是从倒数第二行开始，将等式左边从1开始的非0数，根据下一行对应列的值进行消元，直到等式左侧除了那个1以外所有值为0
        for (int i = m-1; i >= 0; i--) {
            for (int j = i+1; j < m; j++) {
                a[i][m] -= a[i][j] * a[j][m];
            }
        }
        return 0;
    }

    //我***的java, 有个swap会死吗，c++和python哪个不比你好使？
    public static void swap(int t, int c, int i) {
        double temp = a[t][i];
        a[t][i] = a[c][i];
        a[c][i] = temp;
    }
}

baimao大佬的高斯消元步骤整理：
1.遍历每一列
2.找到当前列上最大的一个数，将该数所在的行与还没交换过的最上面的行交换
3.将还没操作过的最上面一行的当前列的数的系数变为1
4.将下面每一行的当前列的系数变为0
5.1.如果所有的行都被移动过，则有唯一解；否则
—1.当没有移动过的行存在右边值 b ≠ 0，则无解（即左边没有未知数，右边系数非0）
—2.当没有移动过的行右边值都是 b = 0，则有无穷解（左边没有未知数，右边系数也为0）
5.2.最后得到最后一行的一个Xn的解，依次往上运算Xn-1、Xn-2 … X1的解

简单题！这是道简单题！布响丸辣！

声明：算法思路来源为y总，详细请见https://www.acwing.com/
本文仅用作学习记录和交流