Gauss elimination method and template code

Gauss elimination method for solving linear equations

Ideas and steps

The last one （ The approximate ） Ladder matrix

Then reduce it to an approximate identity matrix , We can get the solution

---

Template code

// Background ：AcWing 883
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=110;
const double eps=1e-8;   // Do not put double Misspelled int, The reason why it should be less than 1e-8, Because c++ A drawback of floating point numbers , So less than eps when , It can be approximately regarded as 0
double a[N][N];  // Storage augmentation matrix 
int n;
int gauss()
{
    
    int r,c;  //r Indicates the current line to be processed  
    for(r=0,c=0;c<n;c++)   // Traverse each column 
    {
    
        int t=r;
        for(int i=r;i<n;i++)                       // Find the row with the largest element in this column 
            if(fabs(a[i][c])>fabs(a[t][c]))
                t=i;
        if(fabs(a[t][c])<eps) continue;    // If the element is the largest , still 0, Then skip , Go to the next column 
        for(int i=c;i<=n;i++) swap(a[t][i],a[r][i]);   // Put the selected line in “ At the top ” Go to 
        for(int i=n;i>=c;i--) a[r][i] /=a[r][c];    // Put the first in this line c Into 1
        for(int i=r+1;i<n;i++)             // Put the second line c Column elimination into 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)     // If the final step is not strictly complete 
    {
    
        for(int i=r;i<n;i++)
            if(fabs(a[i][n])>eps)      //0== Non zero case , unsolvable 
                return 2;
        return 1;        //0==0 The situation of , There are infinite solutions 
    }
    for(int i=n-1;i>=0;i--)                // Find the solution from bottom to top 
        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;
}

---

Gauss elimination method for solving XOR linear equations

Ideas and steps

It is consistent with Gauss elimination method in solving linear equations

Template code

// Background ：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++)    // Traverse each column 
    {
    
        int t=r;
        for(int i=r;i<n;i++)
            if(a[i][c])    // Find No c The first in the column is not 0 All right 
            {
    
                t=i;
                break;
            }
        if(!a[t][c]) continue;  // If it's all 0 了 , Just continue
        for(int i=c;i<=n;i++) swap(a[r][i],a[t][i]);   // Put this line on top 
        for(int i=r+1;i<n;i++)    // Delete the following line with the selected line , The first c Column elimination as 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;
}