高斯消元 AcWing 883. 高斯消元解线性方程组

川长思鸟来 2023-09-28 13:11 212阅读 0赞

## 高斯消元 AcWing 883. 高斯消元解线性方程组 ##

### 原题链接 ###

[AcWing 883. 高斯消元解线性方程组][AcWing 883.]

### 算法标签 ###

线性代数 高斯消元

### 思路![在这里插入图片描述][a4734cfbc65f424fabf6e2644f4538a7.png] ###

### 代码 ###

#include<bits/stdc++.h>
    #define int long long
    #define abs fabs
    #define rep(i, a, b) for(int i=a;i<b;++i)
    #define Rep(i, a, b) for(int i=a;i>=b;--i)
    using namespace std;
    const int N = 105;
    double a[N][N], eps = 1e-8;
    int n;
    inline int read(){
       int s=0,w=1;
       char ch=getchar();
       while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
       while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
       return s*w;
    }
    void put(int x) {
        if(x<0) putchar('-'),x=-x;
        if(x>=10) put(x/10);
        putchar(x%10^48);
    }
    int gu(){// 高斯消元，答案存于a[i][n]中，0 <= i < n
        // c代表列 r代表行
        int c, r;
        // 按列枚举
        for(c=0, r=0; c<n; ++c){
            int t=r;
            rep(i, r, n){
                if(abs(a[i][c])>abs(a[t][c])){// 找绝对值最大的行
                    t=i;
                }
            }
            if(abs(a[t][c])<eps){
                continue;
            }
            rep(i, c, n+1){// 将绝对值最大的行换到最顶端
                swap(a[t][i], a[r][i]);
            }
            Rep(i, n, c){// 将当前行的首位变成1
                a[r][i]/=a[r][c];
            }
            rep(i, r+1, n){// 用当前行将下面所有的列消成0
                if(abs(a[i][c])>eps){
                    Rep(j, n, c){
                        a[i][j]-=a[r][j]*a[i][c];
                    }
                }
            }
            ++r;
        }
        if(r<n){
            rep(i, r, n){
                if(abs(a[i][n])>eps){
                    return 2;// 无解
                }
            }
            return 1;// 有无穷多组解
        }
        Rep(i, n-1, 0){
            rep(j, i+1, n){
                a[i][n]-=a[i][j]*a[j][n];
            }
        }
        return 0;// 有唯一解
    }
    signed main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        n=read();
        rep(i, 0, n){
            rep(j, 0, n+1){
                scanf("%lf", &a[i][j]);
            }
        }
        int t=gu();
        if(t==2){
            puts("No solution");
        }else if(t==1){
            puts("Infinite group solutions");
        }else{
            rep(i, 0, n){
                if(abs(a[i][n])<eps){// 去掉输出 -0.00 的情况
                    a[i][n]=0;
                }
                printf("%.2lf\n", a[i][n]);
            }
        }
        return 0;
    }

原创不易  
转载请标明出处  
如果对你有所帮助 别忘啦点赞支持哈  
![在这里插入图片描述][9cb4cb80a18345158f8a69e2f196e5b9.png]

[AcWing 883.]: https://www.acwing.com/problem/content/885/
[a4734cfbc65f424fabf6e2644f4538a7.png]: https://img-blog.csdnimg.cn/a4734cfbc65f424fabf6e2644f4538a7.png
[9cb4cb80a18345158f8a69e2f196e5b9.png]: https://img-blog.csdnimg.cn/9cb4cb80a18345158f8a69e2f196e5b9.png