萌新刚学两秒半OI，不知道怎么判断无穷多解

dyc2022 @ 2023-09-11 16:33:18

#include<bits/stdc++.h>
using namespace std;
double a[128][128];
const double eps=1e-7;
int n,flag=0;
main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n+1;j++)scanf("%lf",&a[i][j]);
    for(int i=1;i<=n;i++)
    {
        int maxj=i;
        for(int j=i+1;j<=n;j++)if(fabs(a[j][i])>fabs(a[maxj][i]))maxj=j;
        for(int j=1;j<=n+1;j++)swap(a[i][j],a[maxj][j]);
        if(fabs(a[i][i])<eps)continue;
        for(int j=n+1;j>=i;j--)a[i][j]/=a[i][i];
        for(int j=1;j<=n;j++)
        {
            if(i==j)continue;
            double base=a[j][i];
            for(int k=i;k<=n+1;k++)a[j][k]-=base*a[i][k];
        }
    }
    for(int j=1;j<=n;j++)
    {
        if(fabs(a[j][j])<eps)
        {
            flag=1;
            if(fabs(a[j][n+1])>=eps)puts("-1");
            return 0;
        }
    }
    if(flag)puts("0");
    else for(int j=1;j<=n;j++)printf("x%d=%.2lf\n",j,a[j][n+1]);
    return 0;
}

by STUDENT0 @ 2023-09-11 17:19:11

您再看看

by dyc2022 @ 2023-09-13 16:54:16

改了两个地方，

#include<bits/stdc++.h>
using namespace std;
double a[128][128];
const double eps=1e-10;
int n,flag=0,c;
main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n+1;j++)scanf("%lf",&a[i][j]);
    for(int i=1;i<=n;i++)
    {
        int maxj=i;
        for(int j=i+1;j<=n;j++)if(fabs(a[j][i])>fabs(a[maxj][i]))maxj=j;
        for(int j=1;j<=n+1;j++)swap(a[i][j],a[maxj][j]);
        if(fabs(a[i][i])<eps)continue;
        for(int j=n+1;j>=i;j--)a[i][j]/=a[i][i];
        for(int j=1;j<=n;j++)
        {
            if(i==j)continue;
            double base=a[j][i];
            for(int k=i;k<=n+1;k++)a[j][k]-=base*a[i][k];
        }
        c++;
    }
    for(int i=1;i<=n;i++)
    {
        int cnt=0;
        for(int j=1;j<=n+1;j++)
        {
            if(a[i][j]==0)cnt++;
        }
        if(cnt==n&&a[i][n+1]>=eps)return printf("-1"),0;
    }
    if(c==n)for(int j=1;j<=n;j++)printf("x%d=%.2lf\n",j,a[j][n+1]);
    else printf("0");
    return 0;
}

结果 100 分，但 hack wa 了。

by 王江睿 @ 2023-09-13 21:41:42

cnt==n&&a[i][n+1]>=eps 这里加一下fabs()

然后对于一下这组hack

4
0 0 2 1 2
0 0 1 1 1
0 0 0 1 1
0 0 0 0 0

会发现其实是：

3
0 2 1 2
0 1 1 1
0 0 1 1

这个的答案是正确的。

这个代码的问题就在于，对于这组数据中给出的；不懂得向上消元。

0 0 0 1 1
0 0 0 0.5 0
0 0 1 0.5 1
0 0 0 0 0

手模一下，第四次循环我们期望矩阵长这个样子。但是矩阵保持了原来的样子。

也就是说，对于一个方程组，如果呈一个三角形的状态，x很小但是y很大的矛盾是永远无法被你的程序发现的。

如果把你的代码改成这样，

        for(int j=c+1;j<=n;j++)

那么这一组数据就过去了。

但是，需要注意，这样会 wa on #3
这是因为中间的交换操作一定程度上打破了顺序。

这个地方有两种解决的方法。第一种是把可以交换的搜索范围扩大到 1～n。这样虽然有冗余，但是绝对不会出错。第二种是让第i列的问题在不是在第i行解决，而是在排除了前面的重复的行的第c行解决。这样不仅不会提高算法的常数，而且也很好改、好写。

第一种我没有调出来。第二种见以下代码。

#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

const double eps = 1e-10; // 精度误差
const int maxn = 1005;

int n;
double a[maxn][maxn];

int gauss() {
    int i, j, k, r;
    for (i = 0, j = 0; j < n; j++) {
        for (r = i, k = i + 1; k < n; k++)
            if (fabs(a[k][j]) > fabs(a[r][j]))
                r = k;
        if (fabs(a[r][j]) < eps) continue;
        if (r != i) for (k = j; k <= n; k++) swap(a[i][k], a[r][k]);
        for (k = n; k >= j; k--) a[i][k] /= a[i][j];
        for (k = i + 1; k < n; k++)
            for (r = n; r >= j; r--)
                a[k][r] -= a[k][j]*a[i][r];
        i++;
    }
    for (k = i; k < n; k++)
        if (fabs(a[k][n]) > eps)
            return -1; // 无解或无穷解（不满秩）
    if (i < n) return 1; // 无解或无穷解（不满秩）
    for (i = n - 1; i >= 0; i--)
        for (j = i + 1; j < n; j++)
            a[i][n] -= a[i][j]*a[j][n];
    return 0; // 有唯一解
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j <= n; j++)
            scanf("%lf", &a[i][j]);
    int flag = gauss();
    switch (flag) {
    case -1:
        printf("-1\n");
        break;
    case 1:
        printf("0\n");
        break;
    default:
        for (int i = 0; i < n; i++)
            printf("x%d=%.2lf\n", i + 1, a[i][n]);
    }
    return 0;
}
// post scriptum: by ChatGPT 3.5

by what_can_I_do @ 2024-10-21 20:16:08

@dyc2022 萌新刚学两秒半OI，不知道怎么判断无穷多解

大佬能教教我吗

by dyc2022 @ 2024-10-21 22:13:47

@what_can_I_do 但我还是不会 qwq