数论--高斯消元解线性方程组

一：概念
高斯消元法(Gaussian elimination)是求解线性方阵组的一种算法，它也可用来求矩阵的秩，以及求可逆方阵的逆矩阵。它通过逐步消除未知数来将原始线性系统转化为另一个更简单的等价的系统。它的实质是通过初等行变化(Elementary row operations)，将线性方程组的增广矩阵转化为行阶梯矩阵(row echelon form).

二：模板

//  高斯消元法求方程组的解

const int MAXN = 300;
//  有equ个方程，var个变元。增广矩阵行数为equ，列数为var＋1，分别为0到var
int equ, var;
int a[MAXN][MAXN];  //  增广矩阵
int x[MAXN];        //  解集
int free_x[MAXN];   //  用来存储自由变元（多解枚举自由变元可以使用）
int free_num;       //  自由变元的个数

//  返回值为－1表示无解，为0是唯一解，否则返回自由变元个数
int Gauss()
{
    int max_r, col, k;
    free_num = 0;
    for (k = 0, col = 0; k < equ && col < var; k++, col++)
    {
        max_r = k;
        for (int i = k + 1; i < equ; i++)
        {
            if (abs(a[i][col]) > abs(a[max_r][col]))
            {
                max_r = i;
            }
        }
        if (a[max_r][col] == 0)
        {
            k--;
            free_x[free_num++] = col;   //  这是自由变元
            continue;
        }

        if (max_r != k)
        {
            for (int j = col; j < var + 1; j++)
            {
                swap(a[k][j], a[max_r][j]);
            }
        }
        for (int i = k + 1; i < equ; i++)
        {
            if (a[i][col] != 0)
            {
                for (int j = col; j < var + 1; j++)
                {
                    a[i][j] ^= a[k][j];
                }
            }
        }
    }
    for (int i = k; i < equ; i++)
    {
        if (a[i][col] != 0)
        {
            return -1;  //  无解
        }
    }

    if (k < var)
    {
        return var - k; //  自由变元个数
    }

    //  唯一解，回代
    for (int i = var - 1; i >= 0; i--)
    {
        x[i] = a[i][var];
        for (int j = i + 1; j < var; j++)
        {
            x[i] ^= (a[i][j] && x[j]);
        }
    }

    return 0;
}

三：应用案例
1.高斯消元求解开关问题
这类问题一般就是反转一个位置，那么和它相邻的其他位置也跟着反转，求全部反转成一样的最少反转次数。
在构造增广矩阵时，要将每个开关看成一个变元，并给每个开关列一个方程。即若有n个开关，就要列n个方程，每个方程含有n个变元。若开关i需要反转，则将第i个方程的解设为1(a[i][var]=1)，否则为0(a[i][var]=0)。若反转开关j会使开关i同时反转，则在系数矩阵中a[i][j] = 1.
构造完增广矩阵后，用高斯消元求解。
若方程组无解，则返回无解。
若有唯一解，带回求出解，xi中1的个数就是所需的反转次数
若有多解，枚举解（解的个数为1<<(自由变元个数)），找出其中反转次数最小的。

2.题目举例：
（1）poj -- 3185 The Water Bowls
有一个长度为20的01序列，要将其翻成全0，每次翻动也会将其两侧的字符反转。求最小反转次数。
（2）poj--1681 Painter's Problem
给一个n*n的矩阵将其全部反转成‘y’，求最少的反转次数
（3）poj--1830 开关问题
给n个开关，并给出他们之间的相互联系求有多少种到达指定状态的方法。
方法数就是1 << 自由变元的个数

数论--高斯消元解线性方程组

全站热榜