时间复杂度O(n3)

高斯消元.pdf

步骤

  1. 枚举每一列
    • 找到本列剩余行中绝对值最大的一行
      • 若所有剩余行该列元素均为0，说明无解或无穷多解，直接退出循环
    • 将本行换到剩余行的最上面
    • 将该行当前列元素变为1
    • 用该行消去其它行该列元素
  2. 判断是否有唯一解
    • 若退出循环后行数小于总行数，说明无解或无穷多解
      • 遍历剩余行，判断是这两种情况的哪一种
  3. 有唯一解，求解
    • 从下往上依次求出xn, xn-1, …, x1

例题

883. 高斯消元解线性方程组
输入一个包含 n 个方程 n 个未知数的线性方程组。
方程组中的系数为实数。
求解这个方程组。

输入格式
第一行包含整数 n。
接下来 n 行，每行包含 n+1 个实数，表示一个方程的 n 个系数以及等号右侧的常数。
输出格式
如果给定线性方程组存在唯一解，则输出共 n 行，其中第 i 行输出第 i 个未知数的解，结果保留两位小数。
如果给定线性方程组存在无数解，则输出 Infinite group solutions。
如果给定线性方程组无解，则输出 No solution。
数据范围
1≤n≤100,
所有输入系数以及常数均保留两位小数，绝对值均不超过 100。
输入样例：

  1. 3
  2. 1.00 2.00 -1.00 -6.00
  3. 2.00 1.00 -3.00 -9.00
  4. -1.00 -1.00 2.00 7.00

输出样例：

  1. 1.00
  2. -2.00
  3. 3.00
  1. import java.util.*;
  3. public class Main {
  4.     static final double esp = 1.0e-6;
  6.     public static void main(String[] args) {
  7.         Scanner sc = new Scanner(System.in);
  9.         int n = sc.nextInt();
  10.         double[][] g = new double[n][n+1];
  12.         for (int i = 0; i < n; i++) {
  13.             for (int j = 0; j <= n; j++) {
  14.                 g[i][j] = sc.nextDouble();
  15.             }
  16.         }
  18.         int res = gauss(g, n);
  20.         if (res == 1) System.out.println("No solution");
  21.         else if (res == 2) System.out.println("Infinite group solutions");
  22.         else {
  23.             for (int i = 0; i < n; i++) {
  24.                 System.out.printf("%.2f\n", g[i][n]);
  25.             }
  26.         }
  27.     }
  29.     static int gauss(double[][] g, int n) {
  31.         int r = 0, c = 0;
  32.         for (; c < n; c++) {
  33.             int t = r;
  34.             //找到剩余行中该列值最大的一行
  35.             for (int i = r + 1; i < n; i++) {
  36.                 if (Math.abs(g[i][c]) > Math.abs(g[t][c])) 
  37.                     t = i;
  38.             }
  40.             //如果当前列剩余所有行最大值为0,说明没有唯一解，继续处理下一行
  41.             if (Math.abs(g[t][c]) < esp) continue;
  43.             //交换t和r行
  44.             if (t != r) {
  45.                 for (int i = c; i <= n; i++) {
  46.                     double tmp = g[r][i];
  47.                     g[r][i] = g[t][i];
  48.                     g[t][i] = tmp;
  49.                 }
  50.             }
  52.             //将第r行归一化
  53.             for (int i = n; i >= c; i--) {
  54.                 g[r][i] /= g[r][c];
  55.             }
  57.             //消去其他行第c列元素
  58.             for (int i = r + 1; i < n; i++) {
  59.                 if (Math.abs(g[i][c]) > esp) {
  60.                     for (int j = n; j >= c; j--) {
  61.                         g[i][j] -= g[r][j] * g[i][c];
  62.                     }
  63.                 }
  64.             }
  66.             //继续下一行处理
  67.             r++;
  68.         }
  70.         //判断是否有唯一解
  71.         if (r < n) {
  72.             for (int i = r; i < n; i++) {
  73.                 if (Math.abs(g[i][n]) > esp) return 1;
  74.             }
  75.             return 2;
  76.         }
  78.         //有唯一解的处理
  79.         for (int i = n - 1; i >= 0; i--) {
  80.             for (int j = n - 1; j > i; j--) {
  81.                 g[i][n] -= g[i][j] * g[j][n];
  82.             }
  83.         }
  84.         return 0;
  85.     }
  86. }

注意：浮点数判断是否等于0时与一个特别小的浮点数比较。注意将待比较数转成其绝对值形式

884. 高斯消元解异或线性方程组
输入一个包含 n 个方程 n 个未知数的异或线性方程组。
方程组中的系数和常数为 0 或 1，每个未知数的取值也为 0 或 1。
求解这个方程组。
异或线性方程组示例如下：

  1. M[1][1]x[1] ^ M[1][2]x[2] ^ … ^ M[1][n]x[n] = B[1]
  2. M[2][1]x[1] ^ M[2][2]x[2] ^ … ^ M[2][n]x[n] = B[2]
  3. …
  4. M[n][1]x[1] ^ M[n][2]x[2] ^ … ^ M[n][n]x[n] = B[n]

其中 ^ 表示异或(XOR)，M[i][j] 表示第 i 个式子中 x[j] 的系数，B[i] 是第 i 个方程右端的常数，取值均为 0 或 1。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含 n+1 个整数 0 或 1，表示一个方程的 n 个系数以及等号右侧的常数。
输出格式
如果给定线性方程组存在唯一解，则输出共 n 行，其中第 i 行输出第 i 个未知数的解。
如果给定线性方程组存在多组解，则输出 Multiple sets of solutions。
如果给定线性方程组无解，则输出 No solution。
数据范围
1≤n≤100
输入样例：

  1. 3
  2. 1 1 0 1
  3. 0 1 1 0
  4. 1 0 0 1

输出样例：

  1. 1
  2. 0
  3. 0

思路：
类似于加减乘除意义上的高斯消元，只是运算符有所改变
将亦或 ^ 看作是加号或减号，将 & 位与看作是乘号即可。

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner sc= new Scanner(System.in);
  6.         int n = sc.nextInt();
  7.         int[][] g = new int[n][n + 1];
  9.         for (int i = 0; i < n; i++) {
  10.             for (int j = 0; j <= n; j++) {
  11.                 g[i][j] = sc.nextInt();
  12.             }
  13.         }
  15.         int res = gauss(g, n);
  17.         if (res == 1) System.out.println("No solution");
  18.         else if (res == 2) System.out.println("Multiple sets of solutions");
  19.         else {
  20.             for (int i = 0; i < n; i++) {
  21.                 System.out.println(g[i][n]);
  22.             }
  23.         }
  24.     }
  26.     static int gauss(int[][] g, int n) {
  27.         int r = 0, c = 0;
  29.         for ( ; c < n; c++) {
  30.             int t = r;
  31.             for (int i = r + 1; i < n; i++) {
  32.                 if (g[i][c] == 1) t = i;
  33.             }
  35.             if (g[t][c] == 0) continue;
  37.             if (r != t)
  38.                 for (int i = c; i <= n; i++) {
  39.                     int tmp = g[r][i];
  40.                     g[r][i] = g[t][i];
  41.                     g[t][i] = tmp;
  42.                 }
  44.             for (int i = r + 1; i < n; i++) {
  45.                 if (g[i][c] != 0) {
  46.                     for (int j = n; j >= c; j--) {
  47.                         g[i][j] ^= g[i][c] & g[r][j];
  48.                     }
  49.                 }
  50.             }
  51.             r++;
  52.         }
  54.         if (r < n) {
  55.             for (int i = r; i < n; i++) {
  56.                 if (g[i][n] != 0) return 1;
  57.             }
  58.             return 2;
  59.         }
  61.         for (int i = n - 1; i >= 0; i--) {
  62.             for (int j = i + 1; j < n; j++) {
  63.                 g[i][n] ^= g[i][j] & g[j][n];
  64.             }
  65.         }
  67.         return 0;
  68.     }
  69. }