高斯消元-洛谷模板题P3389

题目大意:

给你n个方程的系数(即 n × ( n + 1 ) n \times (n+1) n×(n+1)的矩阵)，让你求每个数的解.
n ≤ 100 n \leq 100 n≤100

算法：高斯消元

思想:

先用一个式子 E E E将其他式子中的一个未知数 x x x给消掉.那么其他式子就与 x x x无关了。
这个时候，忽略掉 E E E的存在，剩下的式子少了一个未知数 x x x并且仍然符合子问题.继续求解直到只剩下一个只含一个未知数的式子(即一个解).然后将这个解一个一个回代到其他式子中即可得到所有解。

具体在编程实现的时候，选择绝对值最大的系数作为式 E E E能够最小化精度误差

算法步骤:
1.对于每一列（即每个未知数），找出系数绝对值最大所在的行，将其整行交换到第一行.(若不存在非零系数，则该方程组无唯一解)
2.对第一行，将最左边的系数归一化.
3.对下面的所有行，与第一行相消使得最左边的系数归0.
4.此时除了第一行，其他行与最左未知数无关，构成子问题继续求解.

5.求出最后一个未知数的解后，从最后一行往上逆推求所有解。

模板:

const int maxn = 200 + 5;
const double eps = 1e-7;
double a[maxn][maxn] , ans[maxn];
int n;
bool guess ()
{
    // 从第一列开始
    bool ok = true;
    for (int i = 1 ; i <= n ; i++){
        // 找*绝对值*系数最大所在行，将其swap到第一行
        int p = i;
        for (int j = i + 1 ; j <= n ; j++)
            if (fabs(a[j][i]) > fabs(a[p][i])) p = j;
        // 不存在非零系数，则不存在唯一解
        if (fabs(a[i][p]) < eps){
            ok = false;
            break;
        }
        swap(a[p] , a[i]);
        // 将第一行对最左边的系数归一化
        double d = a[i][i];
        for (int j = i ; j <= n + 1 ; j++)
            a[i][j] /= d;
        // 用第一行消去其他行的最左系数
        for (int j = i + 1 ; j <= n ; j++){
            double d = a[j][i];
            for (int k = i ; k <= n + 1 ; k++){
                a[j][k] -= d * a[i][k];
            }
        }
    }
    if (!ok){
        return false;
    }
    // 回代操作
    ans[n] = a[n][n + 1];
    for (int i = n - 1 ; i >= 1 ; i--){
        ans[i] = a[i][n + 1];
        for (int j = i + 1 ; j <= n ; j++)
            ans[i] -= a[i][j] * ans[j];
    }
    return true;
}

关于其他情况的讨论:

1.无解
2.存在*元