朴素高斯消元#3#7错误

Aw顿顿 @ 2022-02-07 22:53:41

by Aw顿顿 @ 2022-02-07 22:53:54

#include<bits/stdc++.h>
#define eps 1e-4
using namespace std;
#define N 505
#define M 500005
int n,m,cnt,h[N],st[M],ed[M],d[N];
double a[N][N],ans[N],res;
struct edge{int v,nxt;}e[M<<1];
void add(int u,int v){e[++cnt].v=v;e[cnt].nxt=h[u];h[u]=cnt;d[v]++;}
void Gauss(int n){
    for(int i=1;i<=n;i++){
        int t=i;//从当前行向后比对 
        for(int j=i+1;j<=n;j++)
            if(fabs(a[j][i])>fabs(a[t][i]))t=j;
        if(i!=t)for(int j=1;j<=n+1;j++)
            swap(a[i][j],a[t][j]);
        if(fabs(a[i][i])<eps)continue;
        for(int j=i+1;j<=n;j++){
            //if(i==j)continue;
            double x=a[j][i]/a[i][i];
            for(int k=i;k<=n+1;k++)
                a[j][k]-=x*a[i][k];
        }
    }bool f=0;
    for(int i=n;i>=1;i--){
        double sum=a[i][n+1];
        for(int k=i+1;k<=n;k++)
            sum-=a[i][k]*ans[k];
        if(!a[i][i]&&!sum)f=1;
        if(!a[i][i]&&sum){puts("-1");return;}
        ans[i]=sum/a[i][i];
    }if(f){puts("0");return;}
    for(int i=1;i<=n;i++)
        if(fabs(ans[i])<eps)printf("x%d=%.2lf\n",i,fabs(ans[i]));
        else printf("x%d=%.2lf\n",i,ans[i]);
    return;
}signed main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n+1;j++)
            scanf("%lf",&a[i][j]);
    }Gauss(n);
    return 0;
}

by derta @ 2022-02-07 23:25:52

#include<bits/stdc++.h>
#define eps 1e-4
using namespace std;
#define N 505
#define M 500005
int n,m,cnt,h[N],st[M],ed[M],d[N];
double a[N][N],ans[N],res;
struct edge{int v,nxt;}e[M<<1];
void add(int u,int v){e[++cnt].v=v;e[cnt].nxt=h[u];h[u]=cnt;d[v]++;}
void Gauss(int n){
    for(int i=1;i<=n;i++){
        int t=i;//从当前行向后比对 
        for(int j=i+1;j<=n;j++)
            if(fabs(a[j][i])>=fabs(a[t][i]))t=j; /*********/
        if(i!=t)for(int j=1;j<=n+1;j++)
            swap(a[i][j],a[t][j]);
        if(fabs(a[i][i])<eps)continue;
        for(int j=i+1;j<=n;j++){
            //if(i==j)continue;
            double x=a[j][i]/a[i][i];
            for(int k=i;k<=n+1;k++)
                a[j][k]-=x*a[i][k];
        }
    }bool f=0;
    for(int i=n;i>=1;i--){
        double sum=a[i][n+1];
        for(int k=i+1;k<=n;k++)
            sum-=a[i][k]*ans[k];
        if(fabs(a[i][i])<eps&&fabs(sum)<eps)f=1; /*****/
        if(fabs(a[i][i])<eps&&fabs(sum)>eps){puts("-1");return;} /*****/
        ans[i]=sum/a[i][i];
    }if(f){puts("0");return;}
    for(int i=1;i<=n;i++)
        if(fabs(ans[i])<eps)printf("x%d=%.2lf\n",i,fabs(ans[i]));
        else printf("x%d=%.2lf\n",i,ans[i]);
    return;
}signed main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n+1;j++)
            scanf("%lf",&a[i][j]);
    }Gauss(n);
    return 0;
}

by derta @ 2022-02-07 23:26:05

@Aw顿顿

by derta @ 2022-02-07 23:29:07

第一处修改原因未知，可能只是恰好能够 AC 此题

by Aw顿顿 @ 2022-02-07 23:30:30

@derta 感谢！我看一下

by Aw顿顿 @ 2022-02-07 23:31:56

啊 浮点数直接用 ! 判断确实是草率了/yun

by Aw顿顿 @ 2022-02-07 23:42:28

翻了一遍讨论区，据说是一些特殊的数据能卡掉高斯消元（？）