求助 70分

徐天乾 @ 2021-07-02 14:14:39

#include<bits/stdc++.h>
using namespace std;
double a[110][110],b[110],Q;
int i,j,n,flag,FLAG,Flag[110];;
void Gauss(int t){
    if (t>n) return ;
    int i,j,k;
    for (k=1;k<=n;k++)
        if (a[k][t]!=0&&!Flag[k]) break;
    if (!a[k][t]){flag=1;return ;}
    Flag[k]=1;
    for (i=1;i<=n;i++){
        if (i==k||!a[t][t]) continue;
        Q=a[i][t]/a[t][t];
        for (j=t;j<=n+1;j++)
            a[i][j]-=a[k][j]*Q;
    }
    Gauss(t+1);
    b[t]=a[k][n+1]/a[k][t];
    for (i=1;i<=n;i++)
        a[i][n+1]-=a[i][t]*b[t],a[i][t]=0;
    return ;            
}
int main(){
    scanf("%d",&n);
    for (i=1;i<=n;i++)
        for (j=1;j<=n+1;j++)
            scanf("%lf",&a[i][j]);
    Gauss(1);
    if (flag){
        for (i=1;i<=n;i++) FLAG|=a[i][n+1]!=0;
        printf("%d\n",-FLAG);return 0;
        } 
    for (i=1;i<=n;i++) printf("x%d=%.2f\n",i,b[i]); 
    return 0;
}

by Cat_shao @ 2021-07-02 19:14:13

洛谷此题讨论区有个hack样例，您的程序输出-1，正确答案为0。

4
0 0 2 4 6
0 0 1 1 2
0 0 4 8 12
1 1 1 1 0

我之前调这道题的时候测试过就输出0，4和8AC了，但是您的程序4和8都炸了，说明判断无限个解有问题。

by Cat_shao @ 2021-07-02 19:32:36

我的代码：

//
// Created by Cat-shao on 2021/1/22.
//

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 52;

int n, firstMove;
double matrix[MAX_N][MAX_N]; // 行列编号都从1开始，n行，n + 1列（增广矩阵）

vector<int> order;

void swapRow(int x, int y) { // 第x行和第y行交换
    double temp; // 临时存储
    for (int i = 1; i <= n + 1; ++i) { // i是列，一共n + 1列
        temp = matrix[x][i];
        matrix[x][i] = matrix[y][i];
        matrix[y][i] = temp;
    }
}

void moveColToEnd(int col) { // 将col列换到最后一列
    double temp;
    int varName; // 原本第col列对应的变量的名字（变量名字本来是1~n，这个moveColToEnd会打乱顺序，等到输出的时候处理下就好）
    varName = *(order.begin() + col);
    order.erase(order.begin() + col);
    if (firstMove == -1) {
        firstMove = varName;
    }
    order.push_back(varName);
    for (int i = 1; i <= n; ++i) { // i是行，一共n行
        temp = matrix[i][col];
        for (int j = col + 1; j <= n; ++j) { // j是列，一共n列（增广矩阵，右侧常数不动）
            matrix[i][j - 1] = matrix[i][j];
        }
        matrix[i][n] = temp;
    }
}

int main()
{
    firstMove = -1;
    scanf("%d", &n);
    memset(matrix, 0, sizeof(matrix));
    order.push_back(0);
    for (int i = 1; i <= n; ++i) { // i是列，n + 1属于右侧常数，不算它
        order.push_back(i);
    }
    for (int i = 1; i <= n; ++i) { // i是行
        for (int j = 1; j <= n + 1; ++j) { // j是列
            scanf("%lf", &matrix[i][j]);
        } 
    }

    bool canSwap;
    for (int i = 1; i <= n; ++i) { // i是行（主元），主元的行和列一致
        while (matrix[i][i] == 0 && order[i] != firstMove) { // 从下面换行和换列
            canSwap = false;
            for (int j = i + 1; j <= n; ++j) { // j是行，用于找一个非零的替换主元
                if (matrix[j][i] != 0) {
                    swapRow(i, j);
                    canSwap = true;
                    break;
                }
            }
            if (!canSwap) { // 全是0
                moveColToEnd(i); // 退到最后
            }
        }
        if (order[i] == firstMove) { // 被移动到末尾的行都是废行
            // 现在第i行一定全是0，看右侧常数项，判断无限解和无解，退出
            for (int j = i; j <= n; ++j) { // j是行，用于判断
                if (matrix[j][n + 1] != 0) { // 第j行一定全是0，如果右侧常数不为0，无解
                    printf("-1");
                    return 0;
                }
            }
            printf("0");
            return 0;
        }

        // 现在主元一定非0
        for (int j = i + 1; j <= n + 1; ++j) { // j是列，这个循环其实想让主元变1
            matrix[i][j] /= matrix[i][i];
        }
        matrix[i][i] = 1; // 等价于这个 matrix[i][i] /= matrix[i][i];

        for (int j = 1; j <= n; ++j) { // j是行
            if (j == i) { // 这个循环不止消下三角，还顺便把上三角给消掉了，自己行不能消自己行
                continue;
            }
            for (int k = i + 1; k <= n + 1; ++k) { // k是列
                matrix[j][k] -= matrix[j][i] * matrix[i][k];
            }
            matrix[j][i] = 0; // 等同于 matrix[j][i] -= matrix[j][i] * matrix[i][i]，matrix[i][i]在上文赋值成1，这个算式必然是0
        }
    }
    // 正常退出就有解
    for (int i = 1; i <= n; ++i) { // i是主元的行和列
        printf("x%d=%.2lf\n", i, matrix[i][n + 1]);
    }
    return 0;
}

大概思路是（命名按照您的代码）：

1. 正常高斯消元。
2. 主元不能为0，如果a[t][t] == 0，就尝试从t + 1行 开始找a[什么行][t] != 0的那一行，把那一行换上来。
3. a[t ~ 最后一行][t] 全都是0，这一列没救了，标记为废弃，弹出，放到最后一列。对新来的一列进行高斯消元，以及换主元（步骤2）
4. 当前的t列发现已经废弃了，a[t][第一列 ~ t-1列]已经被前面的操作1消成0了，因为当前t列是废列，t + 1 到 最后一列 全是废列，a[t][t ~ 最后一列] 全是0。得出t行到最后一行中所有的数全是0，相当于等号左边是0，这个时候判断等号右侧的常数项，是0就是无限解，是非0的数就是无解

by Cat_shao @ 2021-07-02 19:36:07

如果出现了废列，那么这个方程必然是无限解或者无解。

在出现废列，判断时，先判断等号右侧几个常数项都是0，才是无限解。有一个非0，就是无解。

本蒟蒻描述能力太弱了，您要是听不懂，而且极其想把这个题调出来，我可以做个动画。

by Cat_shao @ 2021-07-02 19:47:21

您代码的问题：

1. 没有考虑到主元（a[t][t]）为0的情况，主元为0方程也可能有解。
2. 发现不能换主元的情况就直接退出了，实际上即使当前判断时无限解，也可能存在无解没有被判断的情况。

by loading777jzr @ 2022-01-26 15:04:02

@Cat_shao 太牛了这也……