Gauss 高斯消元

高斯消元…… （裸的暴力）

如果你有一个n元的方程组你会怎么办？

Ans：直接用初中的解方程组的方法呀！

没错，直接暴力加减消元。那什么是“高斯消元”？说白了，就是普通的加减消元罢了。

本人再考场上打了一个暴力解方程，大家都说要高斯消元，弄得我方极了，最后才发现我打的暴力就是高斯消元

流程

1. 选其中一个方程
2. 将其他方程的其中一个元与选出的方程统一系数
3. 将选出的方程与其他方程相减，消去一个未知数，得到 n-1 个 n-1 元的方程组
4. 重复之前的步奏，知道只剩一个一元一次的方程
5. 求出解，将解一步步往回带，得出所有的解

代码实现

洛谷模板题：P3389 【模板】高斯消元法

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 using namespace std;

 int n;

 double a[][],b[],c[];

 //a为方程组，b为常数项，c为解

 void gauss(){            //高斯消元

     for(int i=;i<=n;i++){

         for(int j=i+;j<=n;j++){

             double s=a[i][n-i+]/a[j][n-i+];

             for(int k=;k<=n;k++)a[j][k]*=s;

             for(int k=;k<=n;k++)a[j][k]-=a[i][k];

             b[j]=b[j]*s-b[i];

         }

     }

     if(-1e-<=a[n][]&&a[n][]<=1e-)//double 会有精度误差

         printf("No Solution"),exit();//系数为0，没有唯一解

     c[]=b[n]/a[n][];

     for(int i=n-;i>=;i--){

         for(int j=;j<=n-i;j++)

             b[i]-=a[i][j]*c[j];

         if(-1e-<=a[i][n-i+]&&a[i][n-i+]<=1e-)

             printf("No Solution"),exit();    //同上

         c[n-i+]=b[i]/a[i][n-i+];

     }

 }

 int main(){

     scanf("%d",&n);

     for(int i=;i<=n;i++){

         for(int j=;j<=n;j++)

             scanf("%lf",a[i]+j);

         scanf("%lf",b+i);

     }

     gauss();

     for(int i=;i<=n;i++)printf("%.2f\n",c[i]);

 }

时间复杂度O（n），这不就是人人都能想出的大暴力吗？