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

· · 题解

通过初等行列变换得到的线性方程组，如果是

  1. 完美阶梯型，唯一解
  2. 零 = 非零，无解
  3. 零 = 零， 无穷多组解

面对一个线性方程组，通过行列变换，依次变换成下面三个状态：

  1. 把对角线左下部分的都消掉
  2. 把对角线右上部分的都消掉
  3. 只剩下对角线上的系数

就可以这样行列变换

  1. 把某一行乘一个非零的数
  2. 交换某两行
  3. 把某行的若干倍加到另一行上去

通过这种方式，把只保留对角线上的系数，且系数是1，就得到了答案

参考代码如下：


#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 110;
const double eps = 1e-6;

int n;
double a[N][N];

//debug代码的方式
void out()
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++) printf("%10.2lf", a[i][j]);
    }
}

int gauss()
{
    int c, r;
    for (c = 0, r = 0; c < n; c++)
    {
        int t = r;
        for (int i = r; i < n; i++)         //找到当前这一列绝对值最大的这一行
            if (fabs(a[i][c]) > fabs(a[t][c]))  //fabs是double的，abs是整形的
            t = i;

        if (fabs(a[t][c]) < eps) continue;   //小于eps时，认为是0

        for (int i = c; i < n + 1; i++) swap(a[t][i], a[r][i]);  //把这一行交换到第一行上去
        for (int i = n; i >= c; i--) a[r][i] /= a[r][c];         //倒着来，最后更新第一个数，把第一个数变成1

        for (int i = r + 1; i < n; i++)                          //把下面所有行的这列都消成0
            if (fabs(a[i][c]) > eps)                             //已经是0就不用消了
                for (int j = n; j >= c; j--)                     //从后往前消
                    a[i][j] -= a[r][j] * a[i][c];

        //out();

        r++;
    }

    if (r < n)   //r不是n，就不是唯一解
    {
        for (int i = r; i < n; i++)
            if (fabs(a[i][n]) > eps)
                return 2;       //无解， 0 = !0)

        return 1;               //无穷多组解   0 = 0
    }

    for (int i = n - 1; i >= 0; i--)                          //倒着把方程消一遍，把每i行第j列的系数保留1外，都消成0
        for (int j = i + 1; j < n; j++)
            a[i][n] -= a[j][n] * a[i][j];                     //a[j][n], 就是xj的值。a[i][n]，当前这一行的xi的值
                                                              //下面一行已经求出xj的值，只需模拟，当前i行的第n列，-= a[i][j] * xj

    return 0;  //唯一解
}

int main()
{
    cin >> n;
    for (int i= 0; i < n; i++)
        for (int j = 0; j < n + 1; j++)
            cin >> a[i][j];

    int t = gauss();

    if (t == 0)
    {
        for (int i = 0; i < n; i++) printf("%.2f\n", a[i][n]);
    }
    else if (t == 1) puts("0");
    else puts("-1");

    return 0;
}