高斯消元 模板 （洛谷3389）

题目背景

Gauss消元

题目描述

给定一个线性方程组，对其求解

输入输出格式

输入格式：
第一行，一个正整数 nn

第二至 n+1n+1 行，每行 n+1n+1 个整数，为 a_1, a_2 cdots a_na
1
​ ,a
2
​ ⋯a
n
​ 和 bb ，代表一组方程。

输出格式：
共n行，每行一个数，第 ii 行为 x_ix
i
​ （保留2位小数）

如果不存在唯一解，在第一行输出”No Solution”.

输入输出样例

输入样例#1： 复制
3
1 3 4 5
1 4 7 3
9 3 2 2
输出样例#1： 复制
-0.97
5.18
-2.39
说明

1≤n≤100

高斯消元，思想就是每次选一个式子的一项，将其他的该式消去。时间复杂度O(n^3）。

#include<bits/stdc++.h>

using namespace std;
const int MAXN = 105;
const double eps = 1e-5;

int n,where[MAXN];
double ans[MAXN],x[MAXN][MAXN];

inline void gauss(){
    for(register int i=1;i<=n;i++){
        int p=-1;
        double mx=0;
        for(register int j=1;j<=n;j++){
            if(fabs(x[i][j])-eps>mx)
                mx=fabs(x[i][j]),p=j;
        }
        if(p==-1){   //特判多解与无解。
            printf("No Solution
");
            return;
        }
        where[i]=p;
        for(register int j=1;j<=n;j++){
            if(i==j) continue;
            double t=x[j][p]/x[i][p];
            for(register int k=1;k<=n+1;k++)
                x[j][k]-=t*x[i][k];
        }   
    }
    for(register int i=1;i<=n;i++)
        ans[where[i]]=x[i][n+1]/x[i][where[i]];
    for(register int i=1;i<=n;i++)
        printf("%.2lf
",ans[i]);
}

int main(){
    scanf("%d",&n);
    for(register int i=1;i<=n;i++)
        for(register int j=1;j<=n+1;j++){
            scanf("%lf",&x[i][j]);
        }
    gauss();
    return 0;
} 

还有一个方法是消成三角形，这样便于求解行列式。
代码郝神给的，%%%

代码

#include<bits/stdc++.h>

using namespace std;
const int MAXN = 105;
const double eps = 1e-7;

int n;
double x[MAXN][MAXN];
double ans[MAXN];

inline void gauss(){
    int h=1,l=1;
    for(;h<=n && l<=n+1;h++,l++){
        int r=h;
        for(register int i=h+1;i<=n;i++) 
            if(fabs(x[i][l])>fabs(x[r][l])) r=i;
        if(fabs(x[r][l])<eps) {h--;continue;}
        if(h!=r) 
            for(register int i=l;i<=n+1;i++) 
                swap(x[h][i],x[r][i]);
        for(register int i=h+1;i<=n;i++)
            if(fabs(x[i][l])>eps){
                double t=x[i][l]/x[h][l];
                for(register int j=l+1;j<=n+1;j++)
                    x[i][j]-=x[h][j]*t;
                x[i][l]=0;
            }
    }
    for(register int i=h;i<=n;i++)
        if(fabs(x[i][n+1])>eps) {
            puts("No Solution");
            return;
        }
    if(h<n+1) {puts("No Solution");return;}
    for(register int i=n;i>=1;i--){
        double tmp=x[i][n+1];
        for(register int j=i+1;j<=n;j++)
            tmp-=ans[j]*x[i][j];
        ans[i]=tmp/x[i][i];
    }
    for(register int i=1;i<=n;i++)
        printf("%.2lf
",ans[i]);
}

int main(){
    scanf("%d",&n);
    for(register int i=1;i<=n;i++)
        for(register int j=1;j<=n+1;j++)
            scanf("%lf",&x[i][j]);
    gauss();
    return 0;
}