高斯消元复习

很久之前学过这个东西，但因为一直没有用过就忘记了，写篇博客复习了一下

例题高斯消元解线性方程组

给定义个 $n$ 元一次方程组,求出它的解

我们将方程组的系数矩阵表示出来,那么就是

$$\begin{vmatrix}a_{1,1}~a_{1,2}~...~a_{1,n} b_1\\a_{2,1}~a_{2,2}~...~a_{2,n}~b_2\\\vdots~~~\ddots~~~\vdots\\a_{n,1}~a_{n,2}~...~a_{n,n}~b_n\\\end{vmatrix}$$

对于这个矩阵,我们可以进行下面几种操作

1.把某一行乘以一个非0的数

2.交换某两行

3.把某一行的若干倍加到另一行上

高斯消元则是通过这些操作,将一个系数矩阵变成三角形的形状

首先枚举每一列

1.找到每一行中绝对值最大的系数

2.交换到最上面

3.将该行第一个系数变为1

4.将下面行该列的系数消为0

最后就可以得到一个三角形的形状,求解就一次代入就行

#include<iostream>
#include<cstdio>
using namespace std;

int n, a[105][105];

int gauss()
{
    int r, l;
    for (r = l = 1; l <= n; l++)
    {
        int t = r;
        for (int i = r; i <= n; i++)
            if (a[i][l])
                t = i;
        if (!a[t][l])
            continue;
        for (int i = l; i <= n + 1; i++)
            swap(a[t][i], a[r][i]);
        for (int i = r + 1; i <= n; i++)
            if (a[i][l])
                for (int j = l; j <= n + 1; j++)
                    a[i][j] ^= a[r][j];
        r++;
    }
    if (r <= n)
    {
        for (int i = r; i <= n; i++)
            if (a[i][n + 1])
                return 2;            
        return 1;
    }
    for (int i = n; i >= 1; i--)
        for (int j = i + 1; j <= n; j++)
            a[i][n + 1] ^= a[i][j] & a[j][n + 1];
    return 0;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n + 1; j++)
            scanf("%d", &a[i][j]);
    int t = gauss();
    if (t == 2)
        printf("No solution");
    else if (t == 1)
        printf("Multiple sets of solutions");
    else
    {
        for (int i = 1; i <= n; i++)
            printf("%d\n", a[i][n + 1]);
    }
}

高斯消元解异或线性方程组

与解线性方程组类似

#include<iostream>
#include<cstdio>
using namespace std;

int n, a[105][105];

int gauss()
{
    int r, l;
    for (r = l = 1; l <= n; l++)
    {
        int t = r;
        for (int i = r; i <= n; i++)
            if (a[i][l])
                t = i;
        if (!a[t][l])
            continue;
        for (int i = l; i <= n + 1; i++)
            swap(a[t][i], a[r][i]);
        for (int i = r + 1; i <= n; i++)
            if (a[i][l])
                for (int j = l; j <= n + 1; j++)
                    a[i][j] ^= a[r][j];
        r++;
    }
    if (r <= n)
    {
        for (int i = r; i <= n; i++)
            if (a[i][n + 1])
                return 2;            
        return 1;
    }
    for (int i = n; i >= 1; i--)
        for (int j = i + 1; j <= n; j++)
            a[i][n + 1] ^= a[i][j] & a[j][n + 1];
    return 0;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n + 1; j++)
            scanf("%d", &a[i][j]);
    int t = gauss();
    if (t == 2)
        printf("No solution");
    else if (t == 1)
        printf("Multiple sets of solutions");
    else
    {
        for (int i = 1; i <= n; i++)
            printf("%d\n", a[i][n + 1]);
    }
}