查看“︁05-算法模板/06-高斯消元”︁的源代码


用于解线性方程组。<math>a[i][j]</math> 表示第 <math>i</math> 个方程中第 <math>j</math> 个未知数的系数，<math>a[i][n+1]</math> 是右边的常数。

== 模板 ==

<syntaxhighlight lang="cpp">
const double eps = 1e-12;
double a[105][105]; // a[i][0] 记录第 i 个方程的主元

// 无解：返回 -1
// 多解：返回 0
// 有唯一解：返回 1
int gauss(int x)
{
    int line = 1;
    for (int i = 1; i <= x; i++)
    {
        // 找到下面主元系数最大的方程
        int row = line;
        for (int j = line + 1; j <= x; j++)
            if (fabs(a[row][i]) < fabs(a[j][i]))
                row = j;
        if (row != line)
            std::swap(a[row], a[line]);
        // 系数为 0 则跳过
        double div1 = a[line][i];
        if (fabs(div1) < eps)
            continue;
        a[line][0] = i;
        // 调整当前方程，使主元系数变为 1
        for (int j = 1; j <= x + 1; j++)
            a[line][j] /= div1;
        // 消去下面方程中的该未知数
        for (int j = line + 1; j <= x; j++)
        {
            double div2 = a[j][i];
            for (int k = 1; k <= x + 1; ++k)
                a[j][k] -= a[line][k] * div2;
        }
        line++;
    }
    // 判无解和多解
    if (line <= x)
    {
        for (int i = line; i <= x; i++)
            if (fabs(a[i][x + 1]) > eps)
                return -1; // 无解
        return 0; // 多解
    }
    // 回代求唯一解
    for (int i = x; i >= 1; i--)
    {
        for (int j = i - 1; j >= 1; j--)
        {
            a[j][x + 1] -= a[j][i] * a[i][x + 1];
            a[j][i] = 0;
        }
    }
    return 1;
}
</syntaxhighlight>

== 使用说明 ==

- 读入 <math>n</math> 个方程，<math>n</math> 个未知数
- <math>a[i][j]</math>（<math>1\le j\le n</math>）为第 <math>i</math> 个方程第 <math>j</math> 个未知数的系数
- <math>a[i][n+1]</math> 为第 <math>i</math> 个方程等号右边的常数
- <code>gauss(n)</code> 返回解的情况
- 如果有唯一解，解存储在 <math>a[i][n+1]</math> 中

== 异或方程组（bitset 优化） ==

对于模 <math>2</math> 意义下的方程组，可以用 <code>bitset</code> 优化：

<syntaxhighlight lang="cpp">
bitset<1005> a[2005]; // n 个未知数，m 个方程

int gauss(int n, int m)
{
    int line = 1;
    for (int i = 1; i <= n; i++)
    {
        int row = 0;
        for (int j = line; j <= m; j++)
            if (a[j][i])
            {
                row = j;
                break;
            }
        if (!row)
            continue;
        swap(a[row], a[line]);
        for (int j = 1; j <= m; j++)
            if (j != line && a[j][i])
                a[j] ^= a[line];
        line++;
    }
    for (int i = line; i <= m; i++)
        if (a[i][n + 1])
            return -1; // 无解
    if (line <= n)
        return 0; // 多解
    return 1; // 唯一解
}
</syntaxhighlight>


[[Category:算法模板]]
[[Category:三三文档]]