2020-08-14

高斯消元解线性方程组

X25XD~YZRE64YKBFU{4~F3X.png

1、C++在存储浮点数时会存在误差当判断一个浮点数是否为0时，不判断==0
而是判断是否小于eps 一个很小的数
2、旧版c++中 abs 返回整数的绝对值 fabs()返回浮点数的绝对值

高斯消元核心操作
1、枚举每一列
2、找到当前这一列中绝对值最大的一行
3、将这行换到最上面去
4、将该行的第一个数变成1
5、将当前列的下面所有数消成0

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
const double eps = 1e-6;
int n;
double a[N][N];
void out() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n + 1; j++) {
            cout << a[i][j] << ' ';
        }
        cout << endl;
    }
    cout << endl;
}
int gauss()
{
    int c, r;
    for (c = 1, r = 1; c <= n; c++) {//操作1 按列枚举 1~n
        int t = r;
        for (int i = r; i <= n; i++) { //操作2，找出当前枚举列中的绝对值最大的行
            if (fabs(a[i][c]) > fabs(a[t][c]))
                t = i;        //C++存浮点数0时 可能存的是0.000001；
        }                   //C++在存入浮点数时有误差，所以当他小于一个很小的数是认为他为0
        if (fabs(a[t][c]) < eps)//如果绝对值最大的数都是0，那么为全0列 不做操作
            continue;
        //将绝对值最大的那一行换到还没确定的最上面一行
        //比如第一次操作完毕后第一行会被确定，以后就不动了
        //r++后便从第二行开始 在交换就把绝对值最大的一行和第二行交换
        for (int i = c; i <= n + 1; i++)swap(a[t][i], a[r][i]);
        //将最顶上这一行的第一个非0数字化为1
        //由于每次除以第一个数字，如果从前往后除，那么第一个数除完就变成1了
        //所以本步操作从后往前
        for (int i = n + 1; i >= c; i--)a[r][i] /= a[r][c];
        //将1下面的数字都化为0
        //每行成比例进行加减
        for (int i = r + 1; i <= n; i++) {
            //如果下面一行已经是0，则不做操作
            if (fabs(a[i][c]) > eps) {
                //同理本步为倒叙操作，因为第一行第一个数已经为1 这时候a[i][c](每行的第一个数就是比例)
                for (int j = n + 1; j >= c; j--) {
                    a[i][j] -= a[r][j] * a[i][c];
                }
            }
        }
        //操作完后 确定行数++
        r++;
        // out();
    }
    //这里r<=n由于r的初始值就为1 当r=n+1时才证明每一行都确定了
    if (r <= n) {
        //这里i=r 确定了两行时r=3，所以r就是已经确定的下一行了
        for (int i = r; i <= n; i++) {
            //如果出现0=！0的情况则无解
            if (fabs(a[i][n + 1]) > eps)
                return 2;
        }
        //否则出现的是0=0的情况为有无穷多个解
        return 1;
    }
    //倒叙求解
    //i从最后一行开始 逐个往上走
    //j为i+一列 如i=n-1，则n-1列的数为1 n-1列前的都为0 要把第n列的比例在n+1列减掉 
    //比例为a[i][j]
    for (int i = n; i >= 1; i--) {
        for (int j = i + 1; j <= n; j++) {
            a[i][n + 1] -= a[j][n + 1] * a[i][j];
        }

    }
    return 0;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n + 1; j++)
            cin >> a[i][j];
    }
    int t = gauss();
    if (t == 0) {
        for (int i = 1; i <= n; i++) {
            printf("%.2lf\n", a[i][n + 1]); //注意输出两位小数的写法 %.2lf
        }
    }
    else if (t == 1)
        cout << "Infinite group solutions" << endl;
    else cout << "No solution" << endl;
    return 0;
}