一种很优雅的高斯消元写法

类似线性基

Posted by ethan-zhou on April 9, 2021

rt,自己胡出来的算法。用类似线性基的写法写,代码简短,常数小,并且对无解和无穷解的判断都很简单。

以下为毒瘤题 P2455 线性方程组 代码(之前用正常写法怎么都过不了,面向数据才过的。。):

#include<bits/stdc++.h>
using namespace std;
const int MXN=105;
const double eps=1e-8;
int n;
bool used[MXN];
double arr[MXN][MXN],tmp[MXN];
inline bool is0(double x){return fabs(x)<=eps;}
inline void eli(double *a,double *b,int ind){
    if(is0(a[ind]))return;
    double rate=a[ind]/b[ind];
    for(int i=ind;i<=n+1;i++)a[i]-=rate*b[i];
}
inline int insert(double *eq){
	for(int i=1;i<=n;i++)
		if(!is0(eq[i])){
			if(used[i])eli(eq,arr[i],i);
			else{
				for(int j=i+1;j<=n;j++)if(used[j])eli(eq,arr[j],j);
				for(int j=1;j<i;j++)eli(arr[j],eq,i);
				for(int j=i;j<=n+1;j++)arr[i][j]=eq[j];
				return used[i]=1;
			}
		}
	return is0(eq[n+1])?0:-1;
}

int main(){
	scanf("%d",&n);
	bool infsol=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n+1;j++)scanf("%lf",tmp+j);
		int tres=insert(tmp);
		if(tres==-1)return printf("-1"),0;
		infsol|=!tres;
	}
	if(infsol)printf("0");
	else
		for(int i=1;i<=n;i++)
			printf("x%d=%.2f\n",i,arr[i][n+1]/arr[i][i]+eps);

	return 0;
}

作者:@ethan-enhe
本文为作者原创,转载请注明出处:本文链接



icon