当前位置：首页 > article >正文

高斯消元法及其C++实现

article 2026/4/26 14:53:09

深入浅出高斯消元法及其C++实现

本文章代码由博主编写但是文章由ChatGPT-o1-mini生成
博客食用更佳

在计算机算法竞赛中，线性方程组的求解是一个常见且基础的问题。高斯消元法作为一种经典的算法，因其高效和直观的特性，广泛应用于各种编程竞赛和实际问题中。本文将通过一个具体的C++实现，深入浅出地讲解高斯消元法的核心概念、实现细节以及如何应对实际编程中的挑战。

一、问题背景

高斯消元法（Gaussian Elimination）是一种用于求解线性方程组的算法。给定一个由 $n$ 个方程组成的线性方程组，每个方程包含 $n$ 个未知数，我们希望通过高斯消元法找到这些未知数的解。

题目描述

我们需要编写一个程序，输入一个 $\times (n+1)$ 的矩阵，其中前 $n$ 列代表方程组的系数，最后一列代表常数项。程序需要输出方程组的唯一解，如果方程组无解或有无穷多解，则输出No Solution。

输入输出示例

输入示例：

输出示例：

-0.97
5.18
-2.39

二、高斯消元法基础

1. 基本思想

高斯消元法通过一系列行变换，将原始的线性方程组转化为上三角矩阵形式。具体步骤如下：

选主元（Pivoting）： 对于每一列，选择绝对值最大的元素作为主元，以提高数值稳定性。
消元（Elimination）： 利用主元，将其下方所有元素归零。
回代（Back Substitution）： 从上到下求解未知数。

2. 处理特殊情况

在实际应用中，可能会遇到以下几种情况：

无解： 方程组中出现矛盾，如 $0 x + 0 y + 0 z = 1$ 。
有无穷多解： 自由变量存在，方程组没有唯一解。
唯一解： 每个未知数都有确定的值。

三、C++实现解析

让我们逐步解析提供的C++代码，理解高斯消元法在代码中的具体实现。

1. 代码结构概述

#include <cmath>
#include <cstdint>
#include <iomanip>
#include <ios>
#include <iostream>
#include <utility>using ll = int64_t;template<class T>
T read(){T t;std::cin>>t;return t;
}constexpr ll maxn = 100;
ll n;
double im[maxn+5][maxn+5], tmp[maxn+5];void cp(double*f,double*t){for(ll i=1;i<=n+1;i++){t[i]=f[i];}
}void sp(double*f,double*t){for(ll i=1;i<=n+1;i++){std::swap(f[i],t[i]);}
}int main(){std::cin>>n;for(ll i=1;i<=n;i++){for(ll j=1;j<=n+1;j++){std::cin>>im[i][j];}}for(ll i=1;i<=n;i++){for(ll k=i;k<=n;k++){if(im[k][i]!=0){if(k!=i){sp(im[k],im[i]);}break;}}double fact = im[i][i];for(ll j=1;j<=n+1;j++){im[i][j]/=fact;}for(ll k=1;k<=n;k++){if(k==i)continue;double fact = im[k][i];for(ll j=1;j<=n+1;j++){im[k][j]-=fact*im[i][j];}}}if([]()->bool{for(ll i=1;i<=n;i++){bool isAllZero=true;for(ll j=1;j<=n;j++){if(im[i][j]!=0){isAllZero=false;}}if(isAllZero){return false;}}for(ll i=1;i<=n;i++){if(std::isnan(im[i][n+1])){return false;}}return true;}()){std::cout<<std::fixed<<std::setprecision(2);for(ll i=1;i<=n;i++){std::cout<<im[i][n+1]<<'\n';}}else{std::cout<<"No Solution\n";}
}

2. 代码详解

2.1 数据输入

std::cin>>n;
for(ll i=1;i<=n;i++){for(ll j=1;j<=n+1;j++){std::cin>>im[i][j];}
}

首先读取方程组的规模 $n$ 。
然后逐行读取矩阵数据，其中每一行包含 $n$ 个系数和1个常数项。

2.2 主元选择与行交换

for(ll i=1;i<=n;i++){for(ll k=i;k<=n;k++){if(im[k][i]!=0){if(k!=i){sp(im[k],im[i]);}break;}}// ...
}

对于第 $i$ 个未知数，选择列 $i$ 中第一个非零元素作为主元。
如果主元不在当前行，则交换行以将主元移至当前行。

函数sp的定义：

void sp(double*f,double*t){for(ll i=1;i<=n+1;i++){std::swap(f[i],t[i]);}
}

sp函数用于交换两行的数据。

2.3 主元归一化

double fact = im[i][i];
for(ll j=1;j<=n+1;j++){im[i][j]/=fact;
}

将主元所在的整行都除以主元，使得主元变为1，简化后续消元过程。

2.4 消元过程

for(ll k=1;k<=n;k++){if(k==i)continue;double fact = im[k][i];for(ll j=1;j<=n+1;j++){im[k][j]-=fact*im[i][j];}
}

对于除了当前主行之外的每一行，消去所在列的元素，使得每列只有主元为1，其他元素为0。

2.5 判断解的唯一性

if([]()->bool{for(ll i=1;i<=n;i++){bool isAllZero=true;for(ll j=1;j<=n;j++){if(im[i][j]!=0){isAllZero=false;}}if(isAllZero){return false;}}for(ll i=1;i<=n;i++){if(std::isnan(im[i][n+1])){return false;}}return true;
}()){std::cout<<std::fixed<<std::setprecision(2);for(ll i=1;i<=n;i++){std::cout<<im[i][n+1]<<'\n';}
}else{std::cout<<"No Solution\n";
}

通过一个lambda表达式判断方程组是否有唯一解。
检查所有主元行：
- 如果存在某一行系数全为0，但常数项不为0，说明方程组无解。
检查解的合理性：
- 如果某个解为NaN（非数），说明方程组无唯一解。
如果满足唯一解的条件，则输出结果，保留两位小数。
否则，输出No Solution。

3. 代码中的关键点

3.1 数组下标从1开始

在这段代码中，数组的下标从1开始，而不是C++中常见的从0开始。这种设计可能是为了更贴近数学表达的习惯，使得代码更容易理解。

3.2 行交换与主元选择

选择主元并交换行是高斯消元法中的关键步骤，能够有效避免在消元过程中遇到除以0的情况，并提高算法的数值稳定性。

3.3 消元与归一化

通过对主元所在行进行归一化处理，使得主元为1，然后利用主元消去其他行同一列的元素，最终将矩阵转化为简化的上三角矩阵或单位矩阵。

3.4 解的判断

判断方程组是否有唯一解是高斯消元法中的重要部分。通过检查消元后的矩阵，可以确定方程组的解的性质。

4. 代码优化建议（不修改代码的前提下）

尽管用户要求不修改代码，但从学习的角度，可以提出一些优化建议：

使用零近似判断： 由于浮点数的精度问题，直接比较im[k][i] != 0可能不可靠。可以引入一个极小的阈值，例如1e-9，判断abs(im[k][i]) > 1e-9。
更智能的主元选择： 当前代码选择的是首个非零元素作为主元，可以改为选择绝对值最大的元素以提高数值稳定性。
使用vector替代固定大小的数组： 虽然本题数据范围较小，但在更复杂的场景下，vector提供了更大的灵活性。

四、实例解析

让我们通过给定的输入示例，手动模拟高斯消元法的过程，帮助理解代码的执行流程。

输入：

步骤：

初始增广矩阵：
```
1  3  4 | 5
1  4  7 | 3
9  3  2 | 2
```
第1步：选择第1列的主元
- 最大绝对值在第3行，元素为9。
- 交换第1行与第3行。
```
9  3  2 | 2
1  4  7 | 3
1  3  4 | 5
```

第2步：归一化主元行

主元为9，将整个第1行除以9。

1  0.3333  0.2222 | 0.2222
1  4       7      | 3
1  3       4      | 5

第3步：消元
- 消去第2行和第3行的第1列元素。
- 第2行减第1行：
```
0  3.6667  6.7778 | 2.7778
```
- 第3行减第1行：
```
0  2.6667  3.7778 | 4.7778
```
重复以上步骤，直到矩阵达到单位矩阵形式。

最终得到：

1  0  0 | -0.97
0  1  0 | 5.18
0  0  1 | -2.39

即：

x = -0.97
y = 5.18
z = -2.39

五、总结

本文通过一个具体的C++实现，详细解析了高斯消元法的基本原理和编程实现细节。高斯消元法作为求解线性方程组的经典算法，具有广泛的应用场景和重要的理论价值。在竞赛编程中，理解并掌握高斯消元法的实现，不仅能够帮助解决相关问题，还能提高对线性代数基础知识的理解。

在实际编程中，注意数值稳定性和特殊情况的处理至关重要。通过合理的主元选择和精确的浮点数运算，可以有效避免算法中的潜在问题。同时，合理的数据结构和优化技巧也能提升代码的性能和可读性。

希望通过本文，读者能够对高斯消元法有更深入的理解，并能在编程竞赛中灵活运用这一强大的工具。