高斯消元总结

本文主要是介绍高斯消元总结，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

首先，相比于朴素的高斯消元，高斯约旦消元更好写且答案更容易表达，以下代码实现全部采用这种方式

普通的高斯消元通过加减构造上三角矩阵，约旦消元通过加减构造对角线矩阵

作为常见的数学工具，高斯消元在概率期望、求解行列式等方面有广泛应用，本篇博客并为提及，只记录高斯消元最基本的应用

传统方程求解

P2455 [SDOI2006]线性方程组

首先是对于多解及无解的判断
如果消元过程中某一列第 \(i\) 行之后都为 \(0\)，一定产生一个特殊解
如果是形如 \(0x_i=0\)，则有无数组解
如果形如 \(0x_i=a_i\)，则无解

以这道题为例附上约旦消元模板

代码实现

#include<bits/stdc++.h>
using namespace std;
int n;
double a[105][105];
bool f;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n+1;j++){
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		int maxx=i;
		for(int j=i+1;j<=n;j++){
			if(fabs(a[maxx][i])<fabs(a[j][i]))maxx=j;
		}
		swap(a[i],a[maxx]);
		if(fabs(a[i][i])<1e-9)continue;
		double chu=a[i][i];
		for(int j=i;j<=n+1;j++){
			a[i][j]/=chu;
		}
		for(int j=1;j<=n;j++){
			if(i==j)continue;
			double chu=a[j][i]/a[i][i];
			for(int k=i;k<=n+1;k++){
				a[j][k]-=a[i][k]*chu;
			}
		}
//		for(int j=1;j<=n;j++){
//			for(int k=1;k<=n+1;k++){
//				cout<<a[j][k]<<" ";
//			}
//			cout<<endl;
//		}
//		cout<<endl;
	}
	for(int i=1;i<=n;i++){
		int cnt=0;
		for(int j=1;j<=n;j++){
			if(fabs(a[i][j])<1e-9)cnt++;
		}
		if(cnt==n){
			if(fabs(a[i][n+1])<1e-9){
				f=true;
			}
			else{
				cout<<-1;
				return 0;
			}
		}
	}
	if(f==true){
		cout<<0;
		return 0;
	}
	for(int i=1;i<=n;i++){
		printf("x%d=%.2lf\n",i,a[i][n+1]);
	}
	return 0;
}

P5027 Barracuda

比较基础的应用，钦定哪个方程是错的，然后消元按照题意判断是否满足条件。

异或方程组

对于异或方程组，操作完全类似，只不过相减变成整行异或，这个一般可以用 \(bitset\) 进行优化

P2447 [SDOI2010]外星千足虫

判断用几个条件可以算出结果，相当于判断除去无用方程（即多解）的凑够 \(n\) 个方程的最后位置

代码实现

	#include<bits/stdc++.h>
using namespace std;
const int maxn=3005;
int n,m,ans;
char c[1005];
bitset<1005>a[maxn];
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		scanf("%s",c+1);
		for(int j=1;j<=n;j++){
			if(c[j]=='1')a[i][j]=1;
		}
		int x;
		cin>>x;
		a[i][n+1]=x;
	}
	for(int i=1;i<=n;i++){
		int pos=i;
		while(pos<=m&&(!a[pos][i]))pos++;
		if(pos>m){
			puts("Cannot Determine");
			return 0;
		}
		swap(a[i],a[pos]);
		ans=max(ans,pos);
		for(int j=1;j<=m;j++){
			if(i==j||(!a[j][i]))continue;
			a[j]^=a[i];
		}
//		if(i==n)cout<<pos<<endl;
	}
	cout<<ans<<endl;
	for(int i=1;i<=n;i++){
		if(a[i][n+1])puts("?y7M#");
		else puts("Earth");
	}
	return 0;
}

P3164 [CQOI2014]和谐矩阵

将每个位置作为一个未知数，列出上下左右相关方程即可
由于需要输出方案，消成上三角矩阵更为方便

这篇关于高斯消元总结的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程