AcWing 883. 高斯消元解线性方程组-注释满满
原题链接
简单
作者:
现代修士o_O
,
2021-05-17 16:29:16
,
所有人可见
,
阅读 239
/*
枚举每一列c,
找到当前列绝对值最大的一行
把这一行换到最上面
将该行的第一个数变成1 (其余所有的数字依次跟着变化)
将下面所有行的当前列的值变成 0
*/
#include <iostream>
#include <algorithm>
#include <cmath> //包含fabs()
using namespace std;
const double eps = 1e-6;
const int N = 110;
double a[N][N];
int n;
int gauss() // 高斯消元,答案存于a[i][n]中,0 <= i < n
{
int c, r;//c表示列,r表示行
//1.枚举每一列c,
for (c = 0, r = 0; c < n; c ++ )
{
//2.找到当前列绝对值最大的一行,从第r行找
int t = r;//设t行最大
for (int i = r ; i < n; i ++ )
if (fabs(a[i][c]) > fabs(a[t][c]))
t = i;//寻找最大的数值是因为可以避免系数变得太大,精度较高.
//2.5 特殊情况跳过 下面的r ++ ;将会失败
if (fabs(a[t][c]) < eps) continue;//continue是因为该列不会对上三角的形成做贡献,即目标上三角对角线上在该行的"1"未能形成(故r++是放在后面而没有在for循环里);
//之所以要小于1e-6,是因为c++浮点数的一种弊端,所以小于egs时,可以近似的看作是0
//3.把这一行换到最上面,t,r行交换
for (int j = c; j < n + 1; j ++ ) swap(a[t][j], a[r][j]);
//4.将该行的第一个数变成1 (其余所有的数字依次跟着变化)
// double temp = a[r][c];
// for (int j = c; j < n + 1; j ++ ) a[r][j] /= temp;
for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c];//用行首操作,如果不想保存行首就从后往前
//5.将下面所有行的当前列的值变成 0
for (int i = r + 1; i < n; i ++ )
if (fabs(a[i][c]) > eps) // 当然要大于0才需要变成0
for (int j = n; j >= c; j -- )//减行首需要从后往前,除非保存行首
a[i][j] -= a[i][c] * a[r][j]; // 每一行的数都要减去 该行首倍数 的第r行的对应列,这样行首就为0了
r ++;//若该行已经成功贡献了目标上三角对角线上的"1",则移步到下一行进行构成上三角的操作;
}
if (r < n)//不是唯一解
{
for (int i = r; i < n; i ++ ) // 因为已经是完美阶梯型,所以r~n-1行的值应该都为0,也就是对应方程的左侧==0;
if (fabs(a[r][n]) > eps)//即对应方程的右侧!= 0,形成了矛盾,故无解;
return 2;
return 1;//则对于每一行,对应方程右侧==0,即形成0 = 0,故无数解;
}
//r == n 存在唯一解
//把结果存放a[i][n]
for (int i = n - 1; i >= 0; i --)//枚举行i从后往前
for (int j = i + 1; j < n; j ++ )//行i 下面的行j
a[i][n] -= a[i][j] * a[j][n];//a[j][n]是已知,a[i][j]是a[i][i]左边的数,
//也就是把阶梯型削成对角线形,最后常数就是答案
return 0;
}
int main()
{
cin >> n;
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 == 0)
{
//printf()用%f输出double型,而scanf却用%lf
for (int i = 0; i < n; i ++ ) printf("%.2f\n", a[i][n]);
}
else if (t == 1) puts("Infinite group solutions");
else puts("No solution");
return 0;
}
大佬如果不能有-0.0输出的严格限制,应该怎么办呢