题解 P3389 【【模板】高斯消元法】

这个题目呢，我是按照WZJdalao的白书上的模板做的 然后呢，被vector卡了很久，然后就决定使用数组 然后呢，我又忘记了很多细节的修改 然后就卡了很久才做出来。 对于高斯消元呢，我们从一个例子讲起。 我们首先确定一个方程组作为例子 ```cpp x-2y+3z=6 4x-5y+6z=12 7x-8y+10z=21 ``` 先将它转化为矩阵 ```cpp 1 -2 3 6 4 -5 6 12 7 -8 10 21 ``` 解决这个方程组 我们会希望它变成如下形式 ```cpp 1 0 0 a 0 1 0 b 0 0 1 c ``` 这样就可以表示为$x=a,y=b,z=c$ 我们使用高斯消元，就要一步一步将每个未知数约去。 这种方法是以列为单位消去的 首先我们将第一列转化为1 0 0的形式 在这里要注意一下，我们往往是将这个系数绝对值最大的方程转移到被减的这一行，这样就可以减小误差 所以我们先将矩阵变成这样 ```cpp 7 -8 10 21 4 -5 6 12 1 -2 3 6 ``` 然后将正在处理的方程式化简，让正被处理的系数化1 ```cpp 1 -8/7 10/7 3 4 -5 6 12 1 -2 3 6 ``` 然后使用加减法将第二个与第三个方程组的第一个系数化0 ```cpp 1 -8/7 10/7 3 0 -3/7 2/7 0 0 -6/7 11/7 3 ``` 然后这时候第一列就被化简完成 同理我们化去第二行与第三行，步骤如下： 1.化简第二行 ```cpp 1 -8/7 10/7 3 0 1 -2/3 0 0 -6/7 11/7 3 ``` 2.用第一行减第二行×(-8/7),第三行减第二行×(-6/7) ```cpp 1 0 2/3 3 0 1 -2/3 0 0 0 1 3 ``` 3.不需要化简第三行，所以直接用第一行减去第三行×2/3，第二行减去第三行×(-2/3) ```cpp 1 0 0 1 0 1 0 2 0 0 1 3 ``` 最后我们就得到了一组解$x=1,y=2,y=3$。所以高斯消元其实是运用了小学解方程组的加减法的呢。 ```cpp #include<cstdio> #include<cmath> const double EPS=1E-8; double B[110][110]; int n; int main(){ scanf("%d",&n); for (register int i=0;i<n;i++){ for (register int j=0;j<n;j++) scanf("%lf",&B[i][j]);//读入系数 scanf("%lf",&B[i][n]);//读入值 } for (register int i=0;i<n;i++){ int pivot=i; for (register int j=i;j<n;j++)//选择一个当前位置系数绝对值最大的调换过来，防止误差 if (fabs(B[j][i]-B[pivot][i])<=EPS) pivot=j; for (register int j=0;j<=n;j++){//交换操作，要将所有的全部交换过来 double t=B[i][j]; B[i][j]=B[pivot][j]; B[pivot][j]=t; } if (fabs(B[i][i])<=EPS){//如果该位置系数等于零，则0x=a，一定无解 printf("No Solution\n"); return 0; } for (register int j=i+1;j<=n;j++) B[i][j]/=B[i][i];//将该位的系数变为1 for (register int j=0;j<n;j++) if (i!=j) for (register int k=i+1;k<=n;k++) B[j][k]-=B[j][i]*B[i][k];//将其他方程用加减法减去系数值 } for (register int i=0;i<n;i++) printf("%.2lf\n",B[i][n]);//最后输出结果。 return 0; } ```