题解 P2455 【[SDOI2006]线性方程组】

zhengrunzhe · 2018-02-04 11:32:23 · 题解

高斯消元 每次消元时将所有下面的行按照系数的绝对值大小排序 可以大大减少被0除的可能 如

0 1 1 1
1 1 0 1

原本是第二行第一个1除以第一行第一个0，无意义 经过排序后

1 1 0 1
0 1 1 1

第一行与第二行交换 第一行的第一个数变成了1

1 1 1 1
0 1 1 1
0 1 1 1 

当第一行和第二行无需消元时即可跳过 直接取消第二行和第三行

先判无解 方程ax=b无解的情况即是a=0 b≠0 换成多元即是左边系数全为0但值不为0

后判无穷解 ax=b当a=0,b=0时有无穷解 多元即系数和值全为0

ax=b当a≠0时有唯一解x=b/a

#include<cmath>
#include<cstdio>
#include<algorithm>
const int N=101;
typedef double db;
int n;
db a[N][N+1],ans[N];
bool cmp(db *a,db *b) //按系数绝对值依次排序
{
    for (int u=1;u<=n;u++)
        if (abs(a[u])!=abs(b[u]))
            return abs(a[u])>abs(b[u]);
    return 0;
}
void quicksort(int l,int r) //快排
{
    if (l>=r)return;
    int i=l,j=r;db *k=a[(l+r)/2];
    while (i<=j)
    {
        while (cmp(k,a[j]))j--;
        while (cmp(a[i],k))i++;
        if (i<=j)
        {
            std::swap(a[i],a[j]);
            i++;j--;
        }
    }
    quicksort(l,j);
    quicksort(i,r);
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n+1;j++)
            scanf("%lf",&a[i][j]); //a[i][n+1]代表方程右边的值
    for (int i=1;i<n;i++)
    {
        quicksort(i,n); //首先将第i行包括本身的以下行排序
        for (int j=i+1;j<=n;j++)
        {
            if (!a[j][i])continue;  //无需消元即可跳过
            db mul=-a[j][i]/a[i][i];
            for (int k=i;k<=n+1;k++)
                a[j][k]+=a[i][k]*mul; //消元
        }
    }
    if (!abs(a[n][n])&&abs(a[n][n+1])){puts("-1");return 0;} //判无解
    if (!abs(a[n][n])&&!abs(a[n][n+1])){puts("0");return 0;} //判无穷解
    ans[n]=a[n][n+1]/a[n][n]; //即可首先得出Xn，进行回代
    for (int i=n-1;i;i--)
    {
        for (int j=i+1;j<=n;j++)a[i][n+1]-=a[i][j]*ans[j]; //回代
        if (!abs(a[i][i])&&abs(a[i][n+1])){puts("-1");return 0;} //判无解
        if (!abs(a[i][i])&&!abs(a[i][n+1])){puts("0");return 0;} //判无穷解
        ans[i]=a[i][n+1]/a[i][i]; //得出Xi
    }
    for (int i=1;i<=n;i++)printf("x%d=%.2lf\n",i,ans[i]); //输出 记得保留两位小数
    return 0;
}