高斯消元

任务

给一个 $n$ 元一次方程,求它们的解集。

说明

将方程组做成矩阵形式,再利用三种初等矩阵变换,得到上三角矩阵,最后回代得解集。

接口

复杂度 $O(n^3)$
输入 a 方程组对应的矩阵
n 未知数个数
l, ans 存储解,l[] 表示是否为自由元
输出 解空间的维数

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
inline int solve(double a[][MAXN], bool l[], double ans[], const int& n){
int res = 0, r = 0;
for(int i=0; i<n; ++i)
l[i] = false;
for(int i=0; i<n; ++i){
for(int j=r; j<n; ++j)
if(fabs(a[j][i]) > EPS){
for(int k=i; k<=n; ++k)
swap(a[j][k], a[r][k]);
break;
}
if(fabs(a[r][i]) < EPS){
++res;
continue;
}
for(int j=0; j<n; ++j)
if(j!=r && a[j][i]) > EPS){
double tmp = a[j][i] / a[r][i];
for(int k=i; k<=n; ++k)
a[j][k] -= tmp * a[r][k];
}
l[i] = true;
++r;
}
for(int i=0; i<n; ++i)
if(l[i])
for(int j=0; j<n; ++j)
if(a[j][i]) > 0)
ans[i] = a[j][n] /a[j][i];
return res;
}
文章目录
  1. 1. 任务
  2. 2. 说明
  3. 3. 接口
  4. 4. 代码

20160607-acm-13/

本页二维码