高斯消元

模板库 数学

$Gaussian \_ Elimination$ 高斯消元
时间复杂度 $O(n^3)$ ，解 $n$ 个方程组
注意精度问题

#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 123;
const double EPS = 1e-6;
class Gaussian_Elimination{
    private:
        int n;
        double mat[MAXN][MAXN];
    public:
        void INIT(){
            scanf("%d",&n);
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n+1;j++)
                    scanf("%lf",&mat[i][j]);
        }
        void Gauss(){
            for(int i=1;i<=n;i++){
                int now=i;
                for(int j=i+1;j<=n;j++){
                    if(fabs(mat[j][i])>fabs(mat[now][i]))
                        now=j;
                }
                for(int j=1;j<=n+1;j++)
                    swap(mat[now][j],mat[i][j]);
                for(int j=n+1;j>=i;j--)//line
                    for(int k=i+1;k<=n;k++)//row
                        mat[k][j]-=mat[k][i]/mat[i][i]*mat[i][j];
            }
            for(int i=n;i>=1;i--){
                for(int j=i+1;j<=n;j++)
                    mat[i][n+1]-=mat[i][j]*mat[j][n+1];
                mat[i][n+1]/=mat[i][i];
            }
        }
        void Print_Solution(){
            for(int i=1;i<=n;i++){
                if(fabs(mat[i][i])<EPS){
                    puts("No Solution");
                    return;
                }
            }
            for(int i=1;i<=n;i++){
                printf("%.2lf\n",mat[i][n+1]+EPS);
            }
        }
}DATA;
int main(){
    DATA.INIT();
    DATA.Gauss();
    DATA.Print_Solution();
    return 0;
}