69.Acwing基础课第883题-简单-高斯消元解线性方程组
题目描述
\(输入一个包含 n 个方程 n 个未知数的线性方程组\)。
\(方程组中的系数为实数\)。
\(求解这个方程组\)。
\(下图为一个包含 m 个方程 n 个未知数的线性方程组示例:\)
\[ \begin{aligned} a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n &= b_1, \\ a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n &= b_2, \\ \cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots& \\ a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n &= b_m; \end{aligned}
\]
输入格式
\(第一行包含整数 n\)。
\(接下来 n 行，每行包含 n+1 个实数，表示一个方程的 n 个系数以及等号右侧的常数\)。
输出格式
如果给定线性方程组存在唯一解，则输出共 n 行，其中第 i 行输出第 i 个未知数的解，结果保留两位小数。
注意：本题有 SPJ，当输出结果为 0.00 时，输出 -0.00 也会判对。在数学中，一般没有正零或负零的概念，所以严格来说应当输出 0.00，但是考虑到本题作为一道模板题，考察点并不在于此，在此处卡住大多同学的代码没有太大意义，故增加 SPJ，对输出 -0.00 的代码也予以判对。
如果给定线性方程组存在无数解，则输出 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
代码：
// 包含基础输入输出、字符串操作、算法、数学函数头文件
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>using namespace std;// 常量定义：
// N=110：最多支持100个未知数的线性方程组（留冗余）
// eps=1e-8：浮点数精度阈值（判断是否为0，避免浮点误差）
const int N = 110;
const double eps = 1e-8;int n; // n：方程组的未知数个数（也是方程个数）
double a[N][N]; // 增广矩阵：a[i][j]表示第i行第j列，最后一列a[i][n]是常数项b_i// 高斯消元核心函数：将增广矩阵化为行最简形，求解线性方程组
// 返回值：0-有唯一解 | 1-有无穷多解 | 2-无解
// 最终解（若有唯一解）存储在a[i][n]中（第i个未知数的解）
int gauss()
{int c, r; // c：当前处理的列（未知数）；r：当前处理的行（方程）// 遍历每一列（逐个消去未知数）for (c = 0, r = 0; c < n; c ++ ){// ========== 步骤1：找当前列绝对值最大的行（选主元，避免除数过小导致精度误差） ==========int t = r; // 初始假设当前行是主元行for (int i = r; i < n; i ++ )if (fabs(a[i][c]) > fabs(a[t][c]))t = i; // 更新为主元行（绝对值最大）// ========== 步骤2：判断当前列是否全为0（该未知数无法消元，跳过） ==========if (fabs(a[t][c]) < eps) continue;// ========== 步骤3：将主元行交换到当前处理行（第r行） ==========for (int i = c; i <= n; i ++ ) swap(a[t][i], a[r][i]);// ========== 步骤4：将主元行的当前列系数化为1（行变换：当前行 ÷ 主元） ==========// 从后往前遍历：避免先修改a[r][c]导致后续计算错误for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c];// ========== 步骤5：消去当前列下方所有行的系数（化为0） ==========for (int i = r + 1; i < n; i ++ )// 若当前行的该列系数非0，才需要消元if (fabs(a[i][c]) > eps)// 从后往前消元：避免先修改a[i][c]导致后续计算错误for (int j = n; j >= c; j -- )a[i][j] -= a[r][j] * a[i][c];r ++ ; // 当前行处理完成，下一行待处理}// ========== 步骤6：判断解的情况 ==========// 若处理的行数 < 未知数个数（存在自由变量）if (r < n){// 检查是否存在 0 = 非0 的矛盾方程（无解）for (int i = r; i < n; i ++ )// 若常数项非0，系数全0 → 0 = b_i ≠ 0，无解if (fabs(a[i][n]) > eps)return 2;// 无矛盾方程 → 有无穷多解return 1;}// ========== 步骤7：回代求解（将上三角矩阵化为对角矩阵，得到唯一解） ==========// 从最后一行往前回代，消去上三角的非对角元素for (int i = n - 1; i >= 0; i -- )for (int j = i + 1; j < n; j ++ )// a[i][n] = a[i][n] - 已求解的未知数 × 对应系数a[i][n] -= a[i][j] * a[j][n];return 0; // 有唯一解
}int main()
{// 输入未知数个数nscanf("%d", &n);// 输入增广矩阵：n行，每行n个系数 + 1个常数项（共n+1列）for (int i = 0; i < n; i ++ )for (int j = 0; j < n + 1; j ++ )scanf("%lf", &a[i][j]);// 调用高斯消元函数，获取解的情况int t = gauss();if (t == 2) puts("No solution"); // 无解else if (t == 1) puts("Infinite group solutions"); // 无穷多解else // 有唯一解，输出每个未知数的解（保留2位小数）{for (int i = 0; i < n; i ++ )printf("%.2lf\n", a[i][n]);}return 0;
}