Gauss elimination solves linear equations (floating-point Gauss elimination template)

Topic linking

https://www.acwing.com/problem/content/885/

Ideas

The idea of Gauss elimination is as follows ：

• 1. We go from top to bottom , Start from left to right , For each line, we only keep the current [i,i] The value of the line is 1, This is a ladder
• 2. Because it's from top to bottom , So every time we start to eliminate yuan, we first choose The absolute value The position of the maximum current column value , Then exchange data between this row and the top row we processed
• 3. We will deal with the first r OK, No c Column coefficient becomes 1 Convenient for later elimination , For this step, we multiply both sides of the equation in the elementary transformation by a number
• 4. We will present the first r All lines below the line c The coefficients of the column are all reduced to 0, For this step, we use the addition and subtraction of the equations in the elementary transformation
• 5. Finally, if there is a unique solution , Let's recurse the solution of each equation from bottom to top , Because of the lowest equation, we can directly get the solution of the equation , So we continue to eliminate the influence of the latter solution from the bottom up

notes ：
1. Why should we go to the maximum absolute value every time , Because we don't want to get close 0 Number of numbers , Because this will affect our construction of ladder matrix
2. Gauss elimination idea is not difficult , But the implementation may be wrong without paying attention , You can write an output function , It is better to output the current elimination every time debug

Code

#include<bits/stdc++.h>
using namespace std;
//---------------- Custom part ----------------
#define ll long long
#define mod 1000000007
#define endl "\n"
#define PII pair<int,int>
#define INF 0x3f3f3f3f
const double EPS = 1e-8;

int dx[4] = {
    -1, 0, 1, 0}, dy[4] = {
    0, 1, 0, -1};

ll ksm(ll a,ll b) {
    
	ll ans = 1;
	for(;b;b>>=1LL) {
    
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

ll lowbit(ll x){
    return -x & x;}

const int N = 1e2+10;
//---------------- Custom part ----------------
int t,n,m,q;
double a[N][N];

void out(){
    
	for(int i = 0;i < n; ++i){
    
		for(int j = 0;j <= n; ++j){
    
			printf("%.2lf ",a[i][j]);
		}
		puts("");
	}
	puts("");
}

int guss(){
    
	int c,r;
	for(c=0,r=0; c < n; ++c){
    

		int t = r;
		for(int j = r + 1;j < n; ++j) 
			if(fabs(a[j][c]) > fabs(a[t][c])) 
				t = j;
		if(fabs(a[t][c]) < EPS) continue;// At present, it has been eliminated 
		
		for(int i = c; i <= n; ++i) swap(a[t][i],a[r][i]);// Swap the line with the highest absolute value with the top line 
		for(int i = n;i >= c; --i) a[r][i] /= a[r][c];// Put the number of the current equation c Column coefficient becomes 1
		// Put the second of the following equation c Columns are all suppressed to 0
		for(int i = r + 1;i < n; ++i){
    
			if(fabs(a[i][c]) > EPS){
    // If you need to eliminate yuan 
				for(int j = n;j >= c; --j)
					a[i][j] -= a[r][j] * a[i][c];// Equation addition and subtraction 
			}
		}	
		r++;
	}
	if(r < n){
    
		for(int i = r;i < n; ++i)
			if(fabs(a[i][n]) > EPS) 
				return 2;
		return 1;
	}
	// The last part recurses every solution of the equation from bottom to top 
	for(int i = n-1;i >= 0; --i) {
    
		for(int j = i + 1;j <= n; ++j)
			a[i][n] -= a[i][j] * a[j][n];
		if(fabs(a[i][n]) < EPS) a[i][n] = 0.0;// prevent -0.0 The situation of 
	}
	return 0;
}

void slove(){
    
	cin>>n;
	for(int i = 0;i < n; ++i)
		for(int j = 0;j <= n; ++j)
			scanf("%lf",&a[i][j]);
	
	int t = guss();
	if(t == 1) puts("Infinite group solutions");
	else if(t == 2) puts("No solution");
	else{
    
		for(int i = 0;i < n; ++i)
			printf("%.2lf\n",a[i][n]);
	}
	
}

int main()
{
    
// ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	t = 1;
	while(t--){
    
		slove();
	}
	
	return 0;
}