高斯消元

短命女 2022-01-07 09:21 304阅读 0赞

https://www.luogu.org/problemnew/show/P3389

高斯消元用来解决n元一次方程组，复杂度为n ^ 3

流程和初中学的那个加减消元法差不多

首先我们存储方程的各项系数（就相当于把向量存下来）

然后我们依次消去每项，具体的，把每次没有消掉的那一项（设为k）的系数最大值的那个方程的系数变为1，然后用这个方程的系数依次减去每个方程，让其他方程的k的系数为0

做到最后，你就获得了一个右上角矩阵，解出最低下的一项，依次回代即可

几个细节：

1.取系数最大值是为了防止精度误差

2.无解的情况就是一个方程的未知数系数为0但结果不为0；多解就是像00000这样的一列有多个

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<map>
    #include<cmath>
    using namespace std;
    inline int read()
    {
        int ans = 0,op = 1;
        char ch = getchar();
        while(ch < '0' || ch > '9')
        {
            if(ch == '-') op = -1;
            ch = getchar();
        }
        while(ch >= '0' && ch <= '9')
        {
            (ans *= 10) += ch - '0';
            ch = getchar();
        }
        return ans * op;
    }
    #define db double
    const db eps = 1e-7;
    const int maxn = 101;
    db mp[maxn][maxn],ans[maxn];
    int n;
    void gauss(int i)
    {
        int t = i;
        for(int j = i + 1;j <= n;j++)
            if(fabs(mp[t][i]) < fabs(mp[j][i])) t = j;    
        if(fabs(mp[t][i]) < eps)
        {
            printf("No Solution");
            exit(0);
        }
        if(i != t) swap(mp[i],mp[t]);
        db div = mp[i][i];
        for(int j = i;j <= n + 1;j++)
            mp[i][j] /= div;
        for(int j = i + 1;j <= n;j++)
        {
            div = mp[j][i];
            for(int k = i;k <= n + 1;k++)
                mp[j][k] -= div * mp[i][k];
        }
    }
    int main()
    {
        n = read();
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= n + 1;j++)
                scanf("%lf",&mp[i][j]);
        for(int i = 1;i <= n;i++) gauss(i);
        ans[n] = mp[n][n + 1];
        for(int i = n - 1;i >= 1;i--)
        {
            ans[i] = mp[i][n + 1];
            for(int j = i + 1;j <= n;j++) ans[i] -= mp[i][j] * ans[j];
        }
        for(int i = 1;i <= n;i++) printf("%.2lf\n",ans[i]);
    }

转载于:https://www.cnblogs.com/LM-LBG/p/10645018.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211223/10aeb7cbe16d443b8cfee58a40a150e6.png