【模板】高斯消元法

【模板】高斯消元法 ⁡ \operatorname{【模板】高斯消元法} 【模板】高斯消元法

题目链接： luogu P3389 ⁡ \operatorname{luogu\ P3389} luogu P3389

题目背景

Gauss 消元

题目

给定一个线性方程组，对其求解

输入

第一行，一个正整数 n n n

第二至 n + 1 n+1 n+1 行，每行 n + 1 n+1 n+1 个整数，为 a 1 , a 2 ⋯ a n a_1, a_2 \cdots a_n a1​,a2​⋯an​ 和 b b b ，代表一组方程。

输出

共 n n n 行，每行一个数，第 i i i 行为 x i x_i xi​ （保留2位小数）

如果不存在唯一解，在第一行输出 “No Solution” 。

样例输入

3
1 3 4 5
1 4 7 3
9 3 2 2
           

样例输出

-0.97
5.18
-2.39
           

数据范围

1 ≤ n ≤ 100 , ∣ a i ∣ ≤ 1 0 4 , ∣ b ∣ ≤ 1 0 4 1≤n≤100,∣a_i∣≤10^4 ,∣b∣≤10^4 1≤n≤100,∣ai​∣≤104,∣b∣≤104

思路

这道题是模板题，高斯消元。

我这里用的是高斯-约旦消元法，看的是这位大佬的博客。

我也微微讲一下我的理解吧：

就枚举 a i a_i ai​ ，然后找到系数绝对值最大的一个，然后移到第 i i i 行。

把这个系数化为 1 1 1 ，然后就消元，把其它方程的这个数消掉。

（对于消元过程的讲解，可以看百度百科）

最后就缩成了简化阶梯型矩阵。

那最后就把答案除以剩下的一个系数，就是每一个解的答案了。

不过如果有一列系数都是 0 0 0 ，就说明无解或者有多组解。

代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#define Abs(x) (x) < 0 ? -(x) : (x)

using namespace std;

int n;
double a[101][102];

int main() {
	scanf("%d", &n);//读入
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n + 1; j++)
			scanf("%lf", &a[i][j]);//读入
	
	for (int i = 1; i <= n; i++) {
		int maxx = i;
		for (int j = i + 1; j <= n; j++)
			if (Abs(a[j][i]) > Abs(a[maxx][i]))//找到系数最大的（不算正负）
				maxx = j;
		for (int j = 1; j <= n + 1; j++)//与这一列交换
			swap(a[i][j], a[maxx][j]);
		if (!a[i][i]) {//这一列全部都是系数0
			printf("No Solution");
			return 0;
		}
		for (int j = 1; j <= n; j++)//消元
			if (i != j) {
				for (int k = i + 1; k <= n + 1; k++)
					a[j][k] = a[j][k] - (a[i][k] * (a[j][i] / a[i][i]));
			}
	}
	
	for (int i = 1; i <= n; i++)//输出
		printf("%.2lf\n", a[i][n + 1] / a[i][i]);
	
	return 0;
}