高斯-若尔当消元法(G-J消元法)

Author Avatar
空気浮遊 2018年04月01日
  • 在其它设备中阅读本文章

据说本算法的效率要低一些... 但更好懂,而且实际上...

... 都是 $O(n^3)$ 的算法啊。

原题面:https://www.luogu.org/problemnew/show/P3389
数据可能比较水~ 可以测这一组附加数据(来自题解评论区 @WilliamPon):

3 -1 -2 1 7207 1 2 -5 1161 1 1 -5 9814

Output:
8007 -8653 -2092

最主要的特点是忽略了回代过程。

Porandiginia 的题解已经讲得很清楚了( https://www.luogu.org/blog/37781/solution-p3389 ),但代码有些细节可能需要注意一下。

Code

// Code by ajcxsu
// Problem: Gauss
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cmath>
#define EPS (1e-8)
using namespace std;

double x[110][110];

int main() {
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    for(int j=0;j<=n;j++)
        scanf("%lf",&x[i][j]);
    for(int i=0;i<n;i++) {
        int u=i;
        for(int j=i+1;j<n;j++)
            if(fabs(x[j][i])>fabs(x[u][i])) u=j; // 绝对值最大行
        for(int j=0;j<=n;j++) swap(x[u][j],x[i][j]);
        if(fabs(x[i][i])<=EPS) {
            printf("No Solution\n");
            return 0;
        } // 如果没有唯一解情况,输出NOSOL
        for(int j=i+1;j<=n;j++) x[i][j]/=x[i][i]; // 系数化为1 (必须从n+1开始,否则当x[i][i]/=x[i][i]之后,x[i][i]的值就会变动
        for(int j=0;j<n;j++)
            if(j!=i)
                for(int k=i+1;k<=n;k++) x[j][k]-=x[j][i]*x[i][k]; // (j)-[j,i]*(i) 方程相减
    }
    for(int i=0;i<n;i++) printf("%.2lf\n",x[i][n]);
    return 0;
}