高斯消元法 思路及模闆代碼

高斯消元法解線性方程組

思路及步驟

最後的到一個（近似）階梯形矩陣

再把它化簡成近似機關矩陣，即可得到解

模闆代碼

//題目背景：AcWing 883
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=110;
const double eps=1e-8;   //别把double誤寫成int，之是以要小于1e-8，是因為c++浮點數的一種弊端，是以小于eps時，可以近似的看作是0
double a[N][N];  //存儲增廣矩陣
int n;
int gauss()
{
    int r,c;  //r表示目前要處理的這一行    
    for(r=0,c=0;c<n;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;    //如果元素最大，還是0，那就跳過，去處理下一列
        for(int i=c;i<=n;i++) swap(a[t][i],a[r][i]);   //把選中的這一行放到“最上面”去
        for(int i=n;i>=c;i--) a[r][i] /=a[r][c];    //把這一行的第c列化成1
        for(int i=r+1;i<n;i++)             //把其他行的第c列消成0
            if(fabs(a[i][c])>eps)
            {
                for(int j=n;j>=c;j--)
                    a[i][j]-=a[i][c]*a[r][j];
            }
        r++;
    }
    if(r<n)     //如果最後不是嚴格完全的階梯型
    {
        for(int i=r;i<n;i++)
            if(fabs(a[i][n])>eps)      //0==非零的情況，無解
                return 2;
        return 1;        //0==0的情況，有無窮多解
    }
    for(int i=n-1;i>=0;i--)                //從下往上的把解給求出來
        for(int j=i+1;j<n;j++)
            a[i][n]-=a[j][n]*a[i][j];
    return 0;
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        for(int j=0;j<n+1;j++)
            scanf("%lf",&a[i][j]);
    int t=gauss();
    if(t==2)
        printf("No solution");
    else if(t==1)
        printf("Infinite group solutions");
    else
        for(int i=0;i<n;i++)
        {
            if(fabs(a[i][n])<eps)
                a[i][n]=0;
            printf("%.2lf\n",a[i][n]);
        }
    return 0;
}
           

高斯消元法解異或線性方程組

思路及步驟

與高斯消元法解線性方程組一緻

模闆代碼

//題目背景：AcWing 884
#include<iostream>
#include<algorithm>
using namespace std;
const int N=110;
int n;
int a[N][N];
int gauss()
{
    int r,c;
    for(r=0,c=0;c<n;c++)    //周遊每一列
    {
        int t=r;
        for(int i=r;i<n;i++)
            if(a[i][c])    //找到第c列中第一個不為0的行就行了
            {
                t=i;
                break;
            }
        if(!a[t][c]) continue;  //如果全為0了，就continue
        for(int i=c;i<=n;i++) swap(a[r][i],a[t][i]);   //把這一行放到上面去
        for(int i=r+1;i<n;i++)    //用選中的這一行去消下面的行，把第c列消為0
            if(a[i][c])
                for(int j=c;j<=n;j++)
                    a[i][j]^=a[r][j];
        r++;
    }
    if(r<n)
    {
        for(int i=r;i<n;i++)
            if(a[i][n])
                return 2;
        return 1;
    }
    for(int i=n-1;i>=0;i--)
        for(int j=i+1;j<n;j++)
            if(a[i][j])
                a[i][n]^=a[j][n];
    return 0;
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        for(int j=0;j<n+1;j++)
            scanf("%d",&a[i][j]);
    int res=gauss();
    if(res==2)
        printf("No solution");
    else if(res==1)
        printf("Multiple sets of solutions");
    else
        for(int i=0;i<n;i++)
            printf("%d\n",a[i][n]);
    return 0;
}