5

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

 2 years ago
source link: https://blog-e.tk/2021/04/09/%E4%B8%80%E7%A7%8D%E5%BE%88%E4%BC%98%E9%9B%85%E7%9A%84%E9%AB%98%E6%96%AF%E6%B6%88%E5%85%83%E5%86%99%E6%B3%95/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
一种很优雅的高斯消元写法 - Blog E

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
本文为作者原创，转载请注明出处：本文链接

阅读量 13

来发评论吧~
Powered By Valine
v1.4.4

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK