标签：dots 1.00 未知数 cdot 线性方程组 int 高斯消

\(\color{black}高斯消元\)

题意

输入一个包含 \(n\) 个方程 \(n\) 个未知数的线性方程组。

方程组中的系数为实数。

求解这个方程组。

下图为一个包含 \(m\) 个方程 \(n\) 个未知数的线性方程组示例：

\[\left\{\begin{matrix}a_{1,1} \cdot x_1 + a_{1,2} \cdot x_2 + \dots + a_{1, n} \cdot x_n = b_1 \\a_{2,1} \cdot x_1 + a_{2,2} \cdot x_2 + \dots + a_{2, n} \cdot x_n = b_2 \\ \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots\\a_{m,1} \cdot x_1 + a_{m,2} \cdot x_2 + \dots + a_{m, n} \cdot x_n = b_m \end{matrix}\right. \]

输入格式

第一行包含整数 \(n\)。

接下来 \(n\) 行，每行包含 \(n+1\) 个实数，表示一个方程的 \(n\) 个系数以及等号右侧的常数。

输出格式

如果给定线性方程组存在唯一解，则输出共 \(n\) 行，其中第 \(i\) 行输出第 \(i\) 个未知数的解，结果保留两位小数。

如果给定线性方程组存在无数解，则输出 Infinite group solutions。

如果给定线性方程组无解，则输出 No solution。

样例输入输出

3
1.00 2.00 -1.00 -6.00
2.00 1.00 -3.00 -9.00
-1.00 -1.00 2.00 7.00

1.00
-2.00
3.00

转化

将方程组化成 1 个 \(n \cdot (n+1)\) 的系数矩阵，可以将其执行以下 3 种初等行列变换操作。

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

操作后，可以将其消成类似上三角的形式，即：

\[\left\{\begin{matrix}a_{1, 1} \cdot x_1 + a_{1, 2} \cdot x_2 + \dots + a_{1, n} \cdot x_n = b_1 \\a_{2,2} \cdot x_1 + a_{2,3} \cdot x_2 + \dots + a_{2, n} \cdot x_n = b_2 \\ \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \\a_{n-1, n-1} \cdot x_{n-1} + a_{n-1, n} \cdot x_n = b_{n-1} \\x_n = b_n\end{matrix}\right. \]

无解/有无穷多种解/有唯一解

• 有唯一解 : 消后是一个完美的阶梯型，即第 \(1\) 行有 \(n\) 个未知数，第 \(2\) 行有 \(n-1\) 个未知数，\(\cdots\cdots\) ，第 \(n\) 行有 \(1\) 个未知数。
• 无解 : \(0 = 非0\)
• 有无穷多组解 : \(0 = 0\)

求解

1. 枚举每一列 \(c\)，找到本列绝对值最大的一行.
2. 将该行换到最上面
3. 将该行的第 \(1\) 个数变成 \(1\)，即将等式两边同时除以这个数
4. 把第 \(c\) 列除了第 \(1\) 个数全部消成 \(0\)。
5. 固定第 \(c\) 列，以后的操作将不影响第 \(1\) 到第 \(c\) 列的数值。
6. 迭代操作结束后，将所有第 \(i\) 列第 \(i\) 行的数值消成 \(1\)，再依次求解。

代码

int gauss(){
    int c, r;   // c 是列，r 是行
    
    for(c = r = 0; c<n; c++){   // 枚举每一列
        // 找到 c 列绝对值最大的一行
        int t = r;
        for(int i=r; i<n; i++){
            if(fabs(a[i][c]) > fabs(a[t][c])){
                t = i;
            }
        }
        if(fabs(a[t][c]) < eps){
            continue;
        }
        
        // 交换这两行
        for(int i=c; i<=n; i++){
            swap(a[t][i], a[r][i]);
        }
        
        //将该行的第 1 个数变成 1，即将等式两边同时除以这个数
        for(int i=n; i>=c; i--){
            a[r][i] /= a[r][c];
        }
        
        // 把第 c 列除了第 1 个数全部消成 0
        for(int i=r+1; i<n; i++){
            if(fabs(a[i][c]) > eps){
                for(int j=n; j>=c; j--){
                    a[i][j] -= a[r][j] * a[i][c];
                }
            }
        }
        
        r++;
    }
    
    if(r < n){
        for(int i=r; i<n; i++){
            if(fabs(a[i][n]) > eps){
                return 2;  // 无解
            }
        }
        
        return 1;   // 有无穷多种解
    }
    
    for(int i=n-1; i>=0; i--){
        for(int j=i+1; j<n; j++){
            a[i][n] -= a[i][j] * a[j][n];
        }
    }
    
    return 0;   // 有唯一解
}

标签：dots,1.00,未知数,cdot,线性方程组,int,高斯消
From： https://www.cnblogs.com/2huk/p/17297341.html