高斯消元学习笔记

最近的模拟赛出现了一道坑爹的数学题,正解是上一篇博文所讲的数学插值。然而高斯消元还是可以拿到 65 分的成绩,没办法,凭借着我对其原理的依稀记忆我只能考场上手推高斯消元。

原理

高斯消元其实是个很简单的东西,无非就小学奥数的难度罢了。按照小学奥数的加减消元和代入消元即可完成。模板题给了你 n 个的 n 元一次多项式求解。我们可以通过加减消元合并为 n - 1 个 n - 1 元的一次多项式(合并相邻两个);于是,经过 n - 1 次合并我们就可以得到一个一元一次方程,可以很方便的得到解。我们再将解回代,即可解出方程。

代码

其实没什么好说的,直接看代码就行。鉴于大部分洛谷题解的质量堪忧(经常被 Hack ),所以这篇代码也是经过了重重考验吧。欢迎 Hack 。

为避免误会,事先声明洛谷此题有无数组解和无解都属于 No solution. 如果这两种情况要分开来你可能需要另外一种写法,我也会给出。

需要注意一下无解的情况和主元不能为 0 ,大部分题解被 Hack 也都是因为这个原因。

AC 代码:

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
// ==============================
// author: memset0
// website: https://memset0.cn
// ==============================
#include <bits/stdc++.h>
using namespace std;

const int maxn = 110;
const double inf = 1e10;
int n;
double t, ans[maxn], f[maxn][maxn];

int work() {
for (int i = 1; i <= n; i++) {
// f[i][i]即所谓的主元
if (f[i][i] == 0) { // 主元不能为0,要交换
int j = i + 1;
while (f[j][i] == 0 && j <= n) j++;
if (j > n) return -1; // 肯定无解
swap(f[i], f[j]);
}
for (int j = i + 1; j <= n; j++) {
t = -f[j][i] / f[i][i];
for (int k = i; k <= n + 1; k++)
f[j][k] += f[i][k] * t;
}
}
for (int i = n; i >= 1; i--) {
for (int j = i + 1; j <= n; j++)
f[i][n + 1] -= ans[j] * f[i][j];
ans[i] = f[i][n + 1] / f[i][i];
}
return 0;
}

int main() {

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

if (work() == -1)
printf("No Solution\n");
else for (int i = 1; i <= n; i++)
printf("%.2lf\n", ans[i]);

return 0;
}

可以区分无数解和无解的算法,无数解在有些题目中是可行的(也许有 SPJ ),叫做自由元,你可以取任意一个值:

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
// ==============================
// author: memset0
// website: https://memset0.cn
// ==============================
#include <bits/stdc++.h>
using namespace std;

const int maxn = 110;
const double inf = 1e10;
int n;
double t, ans[maxn], f[maxn][maxn];

int work() {
for (int i = 1; i <= n; i++) {
if (f[i][i] == 0) {
int j = i + 1;
while (f[j][i] == 0 && j <= n) j++;
swap(f[i], f[j]);
}
for (int j = i + 1; j <= n; j++) {
t = -f[j][i] / f[i][i];
for (int k = i; k <= n + 1; k++)
f[j][k] += f[i][k] * t;
}
}
for (int i = n; i >= 1; i--) {
for (int j = i + 1; j <= n; j++)
f[i][n + 1] -= ans[j] * f[i][j];
if (f[i][i] == 0) {
if (ans[i] == 0) return -1; // 无数解
else return -2; // 无解

}
ans[i] = f[i][n + 1] / f[i][i];
}
return 0;
}

int main() {

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

if (work() < 0)
printf("No Solution\n");
else for (int i = 1; i <= n; i++)
printf("%.2lf\n", ans[i]);

return 0;
}

后续 & 参考资料

哦,对了,还记得我开头说的那个模拟赛上的高斯消元么?因为某些原因其实不是正解只有 65 分,另外由于那题的某些限制,任意元不能取 0 ,所以只有 45 了,还好那场模拟赛大家分都不高,勉强凑活啦。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×