AcWing 883. 高斯消元解线性方程组
\(AcWing\) \(883\). 高斯消元解线性方程组
一、题目描述
输入一个包含 \(n\) 个方程 \(n\) 个未知数的线性方程组。
方程组中的系数为实数。
求解这个方程组。
下图为一个包含 \(m\) 个方程 \(n\) 个未知数的线性方程组示例:
输入格式
第一行包含整数 \(n\)。
接下来 \(n\) 行,每行包含 \(n+1\) 个实数,表示一个方程的 \(n\) 个系数以及等号右侧的常数。
输出格式
如果给定线性方程组存在唯一解,则输出共 \(n\) 行,其中第 \(i\) 行输出第 \(i\) 个未知数的解,结果保留两位小数。
如果给定线性方程组存在无数解,则输出 Infinite group solutions
。
如果给定线性方程组无解,则输出 No solution
。
数据范围
\(1≤n≤100\),所有输入系数以及常数均保留两位小数,绝对值均不超过 \(100\)。
输入样例:
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
二、线性方程组知识
三、高斯消元法
求解线性方程组的办法,是高斯消元法:
-
通过一系列的加减消元,得到类似 \(kx=b\) 的式子,求得最后一个未知量的结果
-
然后逐一回代求解 整个 \(x\) 向量
以下列方程为例:
第一次加减消元,用第\(1\)式子消去后面所有的\(x\)得到:
方法:第\(①\)式左右两边除以\(2\),然后左右两边乘以\(②,③\)式中\(x\)的系数,再分别加(减)到\(②,③\)式中,我称之为系数清零消元法
第二次加减消元,用第\(2\)个式子消去后面所有的\(y\)得到:
这样就完成了高斯消元的步骤\(1\),形成了一个倒三角形的形状,接下来逐一回代即可。
用矩阵表示高斯消元
(1)消元过程:
(2)无解: 当消元完毕后,发现有一行系数都为 \(0\),但是常数项不为 \(0\),此时无解
(3)多解: 当消元完毕后,发现有多行系数、常数项均为 \(0\),此时多解,有几行为全为 \(0\),就有几个自由元,即变量的值可以任取,有无数种情况可以满足给出的方程组
此时自由元为\(2\)个
常见问题
问题一: 为什么化简为 \(1\)的操作,和清零的操作都要倒着推?
当然也可以正着推,不过要用一个变量来记录一下开头的元素的值。化简都除以这个值就行了,不过有点麻烦,倒着推时要以省一个变量~
问题二:if (abs(a[t][c]) < eps) continue;
如何理解?
假设 \(c\)表示列,\(r\)表示行,此时我们进行到了 \(c=2\) \(r=2\)
1 0 2 3
0 0 3 2
0 0 2 3
你会发现此时\(r\)行之下 的\(c\)列的绝对值最大值就是\(0\).
说明此时的第\(c\)列已经化简好了,那么不需要再进行后面的化简操作,
但是此时第\(r\)行不用变,此时\(c\)加\(1\) 就接着从 第二行 第三列 开始找绝对值最大的数。
如果我们的\(r\)向后移动了,那么此时我们的第\(2\)行是没有化简的,这显然是不对的。
以此为例,\(r\)如果向后移动了,此时\(r=3,c=3\)但是此时我们的 第二行 第三列 是 \(3\) 并不是\(1\)这种最简的形态。
问题三:倒着推解是如何来的
当有唯一解的时候,我们最后的化简一定是这种。
解的最终形式,如下所示:
我们倒着将每一行都简成每一行只有一个\(1\) 的形式。 这里模拟一下,代码就懂了。
5、手绘流程
四、实现代码
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
const double eps = 1e-8;
double a[N][N];
int n;
// 数组下标从1开始
void gauss() {
int r = 1;
for (int c = 1; c <= n; c++) {
int t = r;
for (int i = r + 1; i <= n; i++)
if (abs(a[i][c]) > abs(a[t][c])) t = i;
if (abs(a[t][c]) < eps) continue; // 无解或无穷多解
if (t != r) swap(a[r], a[t]);
for (int i = n + 1; i >= c; i--) a[r][i] /= a[r][c];
for (int i = r + 1; i <= n; i++)
for (int j = n + 1; j >= c; j--)
a[i][j] -= a[r][j] * a[i][c];
r++;
}
if (r <= n) {
for (int i = r; i <= n; i++)
if (abs(a[i][n + 1]) > eps) {
puts("No solution");
exit(0); // 无解
}
puts("Infinite group solutions");
exit(0); // 无穷多解
}
for (int i = n; i >= 1; i--)
for (int j = i + 1; j <= n; j++)
a[i][n + 1] -= a[i][j] * a[j][n + 1];
}
int main() {
cin >> n;
// 增广矩阵读入,注意下标从1开始,尺寸:n*(n+1)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n + 1; j++)
cin >> a[i][j];
// 0:无解,1:唯一,2:无穷多组解
gauss();
for (int i = 1; i <= n; i++) {
if (abs(a[i][n + 1]) < eps) a[i][n + 1] = 0;
printf("%.2f\n", a[i][n + 1]);
}
return 0;
}
五. 经验教训
练习题:\(P3389\) 【模板】高斯消元法
1、一定要复制题目中输出的字符串,我就是因为No Solution
-> No solution
挂了第一个点
2、\(Luogu\)的模板题中,没有强制区分无解和无穷多组解。