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

· · 题解

在这里只是给大家分享一个判断不是唯一解的小技巧，当然代码是会贴的，代码内会有部分注释。算法不是很难，看看其他大佬的题解或者博客很快就能学会的。

想要快速阅读可以直接看下面的第二点

进入正题：

全部程序打好以后，可能比较头疼的就是怎么判断到底是不是唯一解了，目前有两个办法：

1.判断是否有某个方程的系数全是0。

其实这个也不是很难打，在方程的系数已经满足对角线（i==j）都为1的时候（也就是消完系数，开始回代求解的时候，即f[i][j]==1,i==j）花个O(n^2)一行行扫看看有没有系数全是0的方程。

但是像本蒟蒻懒到不想打判断怎么办？？？

对于C++玩家来说（C和pascal等暂时没有试过）我们可以利用C++的一个特性（应该可以这么说吧）

2.判断一个解是不是一个数

看到题目是不是有点晕？其实这个过程很简单也很懒。如果您已经搞懂了高斯消元，你会发现，当一组方程所有的系数为0时，我们在计算的过程中这些0肯定是会被除的（比如说在某列系数化一的时候），这就造成了计算错误：0不能为除数。 但是，C++在除0的时候并不会崩溃报错，而是把这个解换成nan（Not a Number），而这个nan的特性就是：

自己不等于自己

想必各位大佬已经想到怎么做了！ 我们只需在正常的消元后，判断储存解的数组（在我的代码里是用方程等于号之后的那个位置作为解的）是否有自己不等于自己的数就可以了！

下面是代码：

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=100;
int n;
double f[maxn+1][maxn+1];//用二维数组存系数矩阵

inline void Gauss()//高斯消元的主函数
{
    for(register int i=1;i<=n;i++)//选取一列作为消灭系数的对象
    {
        for(register int j=i;j<=n;j++)//挨个系数化一
            for(register int l=n+1;l>=i;l--)
                f[j][l]/=f[j][i];
        for(register int j=i+1;j<=n;j++)//挨个选取方程，减去系数（可能不太好理解，请自行手推弄懂高斯消元）
            for(register int l=i;l<=n+1;l++)
                f[j][l]-=f[i][l];
    }
    for(register int i=n;i>=1;i--)//直接在系数的那个位置乘上未知数，然后移到方程的等号右边
        for(register int j=n;j>=i+1;j--)
            f[i][j]*=f[j][n+1],f[i][n+1]-=f[i][j];
}

inline bool judge()//判断函数
{
    for(register int i=1;i<=n;i++)//挨个寻找解，如果有某个解自己不等于自己，说明没有唯一解
        if(f[i][n+1]!=f[i][n+1])
            return false;
    return true;
}

int main()
{
    scanf("%d",&n);
    for(register int i=1;i<=n;i++)
        for(register int j=1;j<=n+1;j++)
            scanf("%lf",&f[i][j]);//输入矩阵
    Gauss();//消元
    if(judge())//判断是否有解自己不等于自己
    for(register int i=1;i<=n;i++)
        printf("%.2f",f[i][n+1]),putchar('\n');
    else
        printf("No Solution");//有的话就是没有唯一的解了
    return 0;
}