AcWing 883. 高斯消元-详细注释版
原题链接
简单
作者:
别期待太多
,
2024-10-20 16:22:44
,
所有人可见
,
阅读 5
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 110;
const double eps = 1e-8;
int n;
double a[N][N];
int gauss() // 高斯消元,答案存于a[i][n]中,0≤i<n
{
int c, r;//row是行,column是列
for (c = 0, r = 0; c < n; c ++ )//从第一列开始循环
{
//1 找max,置顶
int t = r;
for (int i = r; i < n; i ++ ) //竖着对行循环,从标准r开始,找绝对值最大的
if (fabs(a[i][c]) > fabs(a[t][c]))
t = i;//t表示首系数最大的行号
if (fabs(a[t][c]) < eps)//如果最大系数是0,即本列所有首系数都是0,相当于不存在首未知量
continue;
for (int i = c; i <= n; i ++ )//横着对列循环,t行是首系数绝对值最大的行
swap(a[t][i], a[r][i]);//t行和标准r行的元素对应交换,原来的t行成为标准r行
//2 首系数化为1,下方变为0
for (int i = n; i >= c; i --)//横着对列循环,将新标准r行的首系数变成1,注意最后除“标准元素”
a[r][i] /= a[r][c];//结果a[r][c]==1
for (int i = r + 1; i < n; i ++ )//竖着对行循环,将1下面所有首系数消成0
if (fabs(a[i][c]) > eps)//如果本行首系数不是0
for(int j = n; j >= c; j -- )//一行一行地来。横着对列循环,注意最后消“标准元素”
a[i][j] -= (a[i][c]/1) * a[r][j];//减去标准行j列的 标准[i][c] 倍
//第一行固定不动,接着是下一行
r ++ ;
}//循环完毕,结果为阶梯型
//3 判断解的情况
if(r < n)//有 0=0或0=b的情况存在
{
for (int i = r; i < n; i ++ )//从第r行开始向下循环,下面系数部分全为0
if (fabs(a[i][n]) > eps)//若r~n-1行有b不为0,方程为 0=b的情况,无解 (注意索引[n]是常数向量b!
return 2; // 无解
return 1; //那么就是0=0的情况,有无穷多组解
}
//r=n,有唯一解
for (int i = n - 1; i >= 0; i -- )//从最后一行开始求解
for (int j = i + 1; j < n; j ++ )//最后一行不用减,就是解
a[i][n] -= a[i][j] * a[j][n];//a[i][n]储存x_i的解,a[j][n]:调用之前的解来求解本行的解;a[i][j]*a[j][n]:系数乘以调用解
return 0; //有唯一解
}
int main()
{
scanf("%d", &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 == 2) puts("No solution");
else if (t == 1) puts("Infinite group solutions");
else
{
for (int i = 0; i < n; i ++ )
printf("%.2lf\n", a[i][n]);
}
return 0;
}