题解 P3389 【【模板】高斯消元法】

· · 题解

update：麻烦了管理员，发现BUG了

这篇题解介绍两种方法~~~

具体实现过程参照其他题解，这里提供两种方法的优劣

法1 高斯消元

初始形式：

\begin{cases} x_{1,1} \quad x_{1,2} \quad \dots\quad x_{1,n} \ |\ x_{1,n+1}\\ x_{2,1} \quad x_{2,2} \quad \dots\quad x_{2,n} \ |\ x_{2,n+1}\\ \dots \\ x_{n,1} \quad x_{n,2} \quad \dots\quad x_{n,n} \ |\ x_{n,n+1}\\ \end{cases}

结束形式：

\begin{cases} x_{1,1}^{'} \quad x_{1,2}^{'} \quad \dots\quad x_{1,n}^{'} \ |\ x_{1,n+1}^{'}\\ 0 \ \ \ \ \quad x_{2,2}^{'} \quad \dots\quad x_{2,n}^{'} \ |\ x_{2,n+1}^{'}\\ \dots \\ 0 \ \ \ \ \quad 0 \ \ \ \ \quad \dots\quad x_{n,n}^{'} \ |\ x_{n,n+1}^{'}\\ \end{cases}

即化为上三角形式

时间复杂度：O(n^3)

优点：

对于无解的判断：某一行前 n 个数均为 0，最后的结果却不为 0。
对于无数解的判断：某一行 n+1 个数均为 0.

缺点：

实现行数：需要回带，约 40 行（较复杂）

法2：高斯-约旦消元

初始形式：

\begin{cases} x_{1,1} \quad x_{1,2} \quad \dots\quad x_{1,n} \ |\ x_{1,n+1}\\ x_{2,1} \quad x_{2,2} \quad \dots\quad x_{2,n} \ |\ x_{2,n+1}\\ \dots \\ x_{n,1} \quad x_{n,2} \quad \dots\quad x_{n,n} \ |\ x_{n,n+1}\\ \end{cases}

结束形式：

\begin{cases} 1\ \ \quad 0 \quad \dots\quad 0 \ \ |\ x_{1,n+1}^{'}\\ 0 \ \ \quad 1 \quad \dots\quad 0\ \ |\ x_{2,n+1}^{'}\\ \dots \\ 0 \ \ \quad 0 \quad \dots\quad 1 \ \ |\ x_{n,n+1}^{'}\\ \end{cases}

即化为对角线形式

复杂度：O(n^3)

优点：

实现行数：无需回带，约 25 行（较简单）

缺点：

只能判断是否有唯一解，无法判断究竟是无解还是无数解。

法1代码：

#include<bits/stdc++.h>
using namespace std;
const int N=105;
double a[N][N];
double x[N], eps=1e-6;
int solve(int n, int m){
    int c=0;
    int r;
    for(r=0;r<n&&c<m;r++,c++){
        int maxr=r;
        for(int i=r+1;i<n;i++){
            if(abs(a[i][c])>abs(a[maxr][c]))
                maxr=i;
        }
        if(maxr!=r) swap(a[r], a[maxr]);
        if(fabs(a[r][c])<eps){
            r--;
            continue;
        }
        for(int i=r+1;i<n;i++){
            if(fabs(a[i][c])>eps){
                double k=a[i][c]/a[r][c];
                for(int j=c;j<m+1;j++) a[i][j]-=a[r][j]*k;
                a[i][c]=0;
            }
        }
    } 
    for(int i=r;i<m;i++){
        if(fabs(a[i][c])>eps) return -1;//无解
    }    
    if(r<m) return m-r;//返回自由元个数
    for(int i=m-1;i>=0;i--){
        for(int j=i+1;j<m;j++) a[i][m]-=a[i][j]*x[j];
        x[i]=a[i][m]/a[i][i];
    }
    return 0;//有唯一解
}
int main() {
    int n;
    cin>>n;
    for(int i=0;i<n;i++) {
        for(int j=0;j<=n;j++) {
            cin>>a[i][j];
        }
    }
    int pan=solve(n, n);
    if(pan!=0) {
        cout<<"No Solution";
        return 0;
    }
    for(int i=0;i<n;i++) {
        printf("%.2lf\n", x[i]);
    }
}

法2代码：

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,pl;
double a[1001][1001];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
       for(int j=1;j<=n+1;j++)
       cin>>a[i][j];
    for(int i=1;i<=n;i++)
    {
        pl=i;
        for(int j=i;j<=n;j++) {
            if(a[j][i]>a[pl][i]) pl=i;
        }                                     
        if(a[pl][i]==0) {cout<<"No Solution";return 0;} //无解或有自由元   
        for(int j=1;j<=n+1;j++)
        swap(a[i][j],a[pl][j]);
        double k=a[i][i];
        for(int j=1;j<=n+1;j++)
        a[i][j]=a[i][j]/k; 
        for(int j=1;j<=n;j++)
        {
            if(i!=j)
            { 
                double ki=a[j][i];
                for(int m=1;m<=n+1;m++)
                a[j][m]=a[j][m]-ki*a[i][m];
            }
        }
    }
    for(int i=1;i<=n;i++)
    printf("%.2lf\n",a[i][n+1]);
    return 0;
}

参考博客：

https://blog.csdn.net/u011815404/article/details/88890702

https://www.cnblogs.com/xcg123/p/10679600.html