高斯消元

能够使用$O(n^3)$的时间复杂度计算方程的解。

模板题

883高斯消元解方程

算法原理：

以第一次迭代为例子:
(第一次迭代c是1，即对第一列做以下操作)

代码

#define judge
// Author: oceanlvr
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define mp(a, b) make_pair(a, b)
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;
const int ninf = 0xcfcfcfcf;
const double pi = acos(-1.0);

int n;
const int maxn = 1e3 + 10;
double a[maxn][maxn];
const double eps = 1e-6;
int guess() {
  int c, r;  // c是列 r是行
  for (c = 0, r = 0; c < n; c++) {
    //枚举列
    int t = r;
    // 1.找当这一列绝对值最大的这一行
    for (int i = r; i < n; i++)
      if (fabs(a[i][c]) > fabs(a[t][c])) t = i;

    //当前这一行最小已经是0了不需要再做接下来的操作
    if (fabs(a[t][c]) < eps) continue;
    // 2.当前列和最上面一列交换
    for (int i = c; i <= n; i++) swap(a[t][i], a[r][i]);
    // 3.令该行的主元变为1
    for (int i = n; i >= c; i--) a[r][i] /= a[r][c];
    // 4.将下面所有的行的第c列消为0
    for (int i = r + 1; i < n; i++) {
      if (fabs(a[i][c]) > eps) {
        for (int j = n; j >= c; j--) {
          // a[r][j]当前这行的第j列元素,a[i][c]是下面行的最前面的元素
          //目的是把第r+1行~n行的第c列元素都消除为0
          a[i][j] -= a[r][j] * a[i][c];
        }
      }
    }
    r++;
  }

  if (r < n) {
    //多个解或者无解
    for (int i = r; i < n; i++) {
      if (fabs(a[i][n]) > eps) {
        //出现a=0的情况 ,a是某个数字
        return 2;  //无解
      }
    }
    return 1;  //无穷解
  }
  /*此时这里得到的矩阵是
  1.0 0.5 -1.5 -4.5
  0.0 1.0 0.33  -1.0
  0.0 0.0 1.0  3.0
  */
  //如果有解并且解是唯一的那么就开始给出解的唯一形式
  // 5.将非主元位置的A系数矩阵的其他x消去
  for (int i = n - 1; i >= 0; i--) {
    for (int j = i + 1; j < n; j++) {
      // 其中a[i][j]是主元的位置
      //行从后面向前面消除主元后面的元素
      //例如倒数第二行的[0.0 1.0 0.3  -1.0]
      //[0.0 1.0 0 -2.0] -1.0-0.33*3=-2.0
      a[i][n] -= a[i][j] * a[j][n];
    }
  }
  return 0;  //唯一解
}
int main() {
#ifndef judge
  freopen("E:/yxc/in.txt", "r", stdin);
  freopen("E:/yxc/out.txt", "w", stdout);
#endif
  cin >> n;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n + 1; j++) {
      cin >> a[i][j];
    }
  }
  int t = guess();
  if (t == 0) {
    for (int i = 0; i < n; i++) {
      printf("%.2lf\n", a[i][n]);
    }
  } else if (t == 1) {
    puts("Infinite group solutions");
  } else {
    puts("No solution");
  }
  return 0;
}