33DAI：导入1个版本

2026-05-20T18:12:11Z

导入1个版本

←上一版本		2026年5月20日 (三) 18:12的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:50:33Z

批量导入三三文档

←上一版本		2026年5月20日 (三) 16:50的版本
（没有差异）

33DAI：导入1个版本

2026-05-20T16:25:35Z

导入1个版本

←上一版本		2026年5月20日 (三) 16:25的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:22:29Z

批量导入三三文档

新页面

用于解线性方程组。<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:三三文档]]

05-算法模板/06-高斯消元 - 版本历史

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档