算法简介：九鹦之喙

高斯消元是一种快速求一些线性方程组的算法。消元法是一种用某一种未知数表示另外一种未知数从而减少未知数数量得到解的方法。而众所周知，消元法的理论基础是等式的性质。

算法演示：星虎之掌

算法推导：蜂鸟之羽

首先给出一个简单的三元一次方程组：

初中学过的消元方式就是加减消元、代入消元。解这个方程的话，首先用第二个式子变形分别消掉一三式子里面的 $x$ ，这是候一三方程式就构成了一个二元一次方程组，解出来了就全解出来了。

我们可以用一种矩阵的形式去表示整个方程组：

我们定义初等变换有一下三种：

  1. 交换任意两行
  2. 对于某一行整体乘上一个数
  3. 对于任意两行相加或者相减

我们就不难模拟出一下流程

  • 枚举主元，找到主元下面系数不为零的一行（有时为了精度，会选择主元绝对值最大的一行
  • 把这一行与主元交换
  • 把主元系数变为一
  • 把主元下面的系数变为零

那么这是候得出来的矩阵有下面几种可能：

  • 有解：系数矩阵的 $(i,i)$ 位置非 0
  • 无解：系数矩阵的 $(i,i)$ 为 0 且增广矩阵的对应行非 0
  • 无数解：系数矩阵的 $(i,i)$ 为 0 且增广矩阵的对应行也为 0

算法模板：瑞兽之形

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
#define Maxn 105
#define eps (1e-6)

using namespace std;

int n;
double a[Maxn][Maxn]; // 增广矩阵

int gauss(){
	for (int i = 1; i <= n; ++i){ //第i主元
		for (int k = i; k <= n; ++k){
			if (fabs(a[k][i]) > eps){
				swap(a[k], a[i]);
				break;
			}
		} //换非0行
		if (fabs(a[i][i]) < eps){
			return 0;
		}

		for (int j = n + 1; j >= i; j--){
			a[i][j] /= a[i][i];
		} // 变1

		for (int k = i + 1; k <= n; k++){
			for (int j = n + 1; j >= i; j--){
				a[k][j] -= a[k][i] * a[i][j];
			}
		} // 变0
	}
	for (int i = n - 1; i >= 1; i--){ // 回代
		for (int j = i + 1; j <= n; j++){
			a[i][n + 1] -= a[i][j] * a[j][n + 1];
		}
	}
	return 1; // 存在唯一解
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n + 1; j++){
			scanf("%lf", &a[i][j]);
		}
	}

	if (gauss()){
		for (int i = 1; i < n + 1; i++){
			printf("%.2lf\n", a[i][n + 1]);
		}
	} else{
		puts("No Solution");
	}
	return 0;
}

算法实战：原鳄之爪

查看相关标签喵！