高斯-约旦消元

下面给两道板子

【模板】高斯消元法

最最基础的板子，没啥哆嗦的。下面给出高斯-约旦消元解法。

#include<bits/stdc++.h>
using namespace std;
int n, dt = 1;
double eps = 1e-9, m[102][102];
int main(){
	scanf("%d", &n);
	for(int i=1; i<=n; ++i)
	for(int j=1; j<=n+1; ++j)
		scanf("%lf", &m[i][j]);
	for(int i=1; i<=n; ++i){
		int mx = i;
		for(int j=i+1; j<=n; ++j)
			if(fabs(m[mx][i]) < fabs(m[j][i])) mx = j;
		if(fabs(m[mx][i]) < eps) dt = 0;
		swap(m[mx], m[i]);
		for(int j=n+1; j>=i; --j) m[i][j] /= m[i][i];
		for(int j=1; j<=n; ++j){
			if(j == i) continue;
			double t = m[j][i];
			for(int k=1; k<=n+1; ++k) m[j][k] -= t*m[i][k];
		}
	}
	if(!dt){
		printf("No Solution");
		return 0;
	}
	for(int i=1; i<=n; ++i) printf("%.2f\n", m[i][n+1]);
	return 0;
}

[SDOI2006] 线性方程组

这是一道很好的题(板子)，跟上题唯一的区别就是判无解和无穷解。这题打通了说明你对高斯消元的理解也就差不多了。

搞了两天，终于把高斯-约旦消元的解调出来了。

高斯-约旦消元 和 高斯消元 的原理是一样的，只不过实现方式略有差别。高斯消元是先把主元以前的系数统统化为0，再回代求解；而高斯-约旦消元是把主元化为一，在把所有狮子的主元都化为0，让主元系数都为1并且在对角线上排列。

对于形如这样的狮子\([0\ 0\ 0\ …\ |\ k]\)， 无解的判定方法是所有系数都为0但 \(k\) 不为0，无穷解的判定方式是所有系数都为0且 \(k\) 等于0 或存在某个主元都为0。易知：判定无解在先，其次为无穷解，最后输出答。

所以，在进行高-约消元的时候，如果出现个主元的最大值为0，那么会出现两种情况，要么无解，要么无穷解，所以要查一遍这个狮子的所有系数，看是否满足上述情况。如果判不出无解，这一列主元也就没用了，为了不影响后续的消元操作，那就把这一列全部移动到右边去。选出来的这一行也移动到下边去。所以最后消完元的子矩阵应该位于完整矩阵的左上角。最后再遍历一遍整个矩阵看是否无解即可。

注意细节。

#include<bits/stdc++.h>
using namespace std;
int n, dt = 1, a, b; // a b 分别代表当前的行和列 
double eps = 1e-9, m[52][52]; //eps为精度，因为涉及到小数运算，所以不太会出现完全等于0的数 
int main(){
	scanf("%d", &n);
	a = n, b = n+1;
	for(int i=1; i<=n; ++i)
	for(int j=1; j<=n+1; ++j)
		scanf("%lf", &m[i][j]);
	for(int i=1; i<=a; ++i){
		int mx = i;
		for(int j=i+1; j<=b; ++j)
			if(fabs(m[mx][i]) < fabs(m[j][i])) mx = j;
		if(fabs(m[mx][i]) < eps){ //如果主元都为0 
			bool cnt = 1;
			for(int j=i+1; j<=n; ++j) //查是否无解 
				if(fabs(m[mx][j]) >= eps) cnt = 0;
			if(cnt && fabs(m[mx][n+1]) >= eps){
				printf("-1");
				return 0;
			}
			dt = 0;
			swap(m[mx], m[a--]); //移动 
			--b;
			for(int j=1; j<=n; ++j) swap(m[j][i], m[j][b]); //移动 
			--i;
			continue; //一是防止报错 二是再消也没啥大用 毕竟主元都没了 
		}
		swap(m[mx], m[i]);
		for(int j=n+1; j>=i; --j){
			if(j >= b && j <= n) continue; //避免误判 
			m[i][j] /= m[i][i];
		}
		for(int j=1; j<=n; ++j){ //这里很重要，一定要把能消的都消干净 
			if(j == i) continue;
			double t = m[j][i];
			for(int k=1; k<=n+1; ++k) m[j][k] -= t*m[i][k];
		}
	}
//	for(int i=1; i<=n; ++i){
//		for(int j=1; j<=n+1; ++j){
//			printf("%.2f ", m[i][j]);
//		}printf("\n");
//	}
	for(int i=1; i<=n; ++i){ //再扫一遍 看是否无解 
		bool cnt = 1;
		for(int j=1; j<=n; ++j)
			if(fabs(m[i][j]) >= eps) cnt = 0;
		if(cnt && fabs(m[i][n+1]) >= eps){
			printf("-1");
			return 0;
		}
	}
	if(!dt){ //无穷解 
		printf("0");
		return 0;
	}
	for(int i=1; i<=n; ++i) printf("x%d=%.2f\n", i, m[i][n+1]);
	return 0;
}