主要作用
求解线性方程组
实现
引入
我们都会解一元一次方程组吧（废话）
那么二元的呢（有两个未知数），那么我们有两个不同的方程就可以解出来了
三元三个肯定大家也会解
所以我们可以猜测，有$n$个不同的方程时可以解出$n$ 元一次方程
(这个看起来很显然，但是详细证明起来很麻烦，想知道的可以自行上网找资料)
好了，我们来解一下一万元一次方程吧。。。
这就是计算机应该解决的问题了
原理
回想一下我们平时是怎么解这类方程的
肯定是消元啊就是不停的拿两个方程相减，逐渐减少未知量的个数
（这个不会建议重新学习小学课程）
那么，我们就把我们平时的思想用代码来实现一下吧
思想
首先我们找第$i$行的第$i$个数，用第$i$行的这个数把$1 - n$行的第$i$个数都消去
我们考虑一下，最后第$i$行一定只剩第$i$个数，其余的都被消去了
那么就只剩下$n$个一元一次方程组了，依次解出来就好了
没了，就这么简单
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
const int maxn = 1e2 + 1;
inline int ()
{
register int x = 0, ch = getchar(), f = 1;
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
return x * f;
}
int n;
double a[maxn][maxn], b[maxn];
int main()
{
n = read();
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= n; j ++)
{
scanf("%lf", &a[i][j]);
}
scanf("%lf", &b[i]);
}
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= n; j ++)
{
if(j == i) continue;
double temp = a[j][i] / a[i][i];
for(int k = i; k <= n; k ++)
{
a[j][k] -= a[i][k] * temp;
}
b[j] -= b[i] * temp;
}
}
for(int i = 1; i <= n; i ++)
{
printf("%.2fn",b[i] / a[i][i]);
}
}
|
那么只要我们把上面那份代码交上去，我们就会发现，红红的真喜庆
为什么会错呢？
这个引入还真失败因为题目都说了如果不存在唯一解了
很显然 $2x + y = 0$ 与$4x + 2y = 0$这个方程是等价的
所以$n$个方程并不一定能解出来，此时就会出现多解
一定只有这一种特殊情况吗？咱们做数学题有多少次忘判无解了呢？
看一下$2x + y = 0$ 与 $4x + 2y = 1$ ，不用我多解释了吧
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
const int maxn = 1e2 + 1;
inline int ()
{
register int x = 0, ch = getchar(), f = 1;
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
return x * f;
}
int n;
double a[maxn][maxn], b[maxn];
int main()
{
n = read();
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= n; j ++)
{
scanf("%lf", &a[i][j]);
}
scanf("%lf", &b[i]);
}
for(int i = 1; i <= n; i ++)
{
bool flag = 0;
for(int j = i; j <= n; j ++)
{
if(fabs(a[i][j]) > 1e-6)
{
flag = 1;
for(int k = 1; k <= n; k ++)
{
std:: swap(a[i][k], a[j][k]);
}
std:: swap(b[j], b[i]);
break ;
}
}
if(!flag){
puts("No Solution");
return 0;
}
for(int j = 1; j <= n; j ++)
{
if(j == i) continue;
double temp = a[j][i] / a[i][i];
for(int k = i; k <= n; k ++)
{
a[j][k] -= a[i][k] * temp;
}
b[j] -= b[i] * temp;
}
}
for(int i = 1; i <= n; i ++)
{
printf("%.2fn",b[i] / a[i][i]);
}
}
|
没卡精度没系数化一过了怎么回事？
还有这好像叫高斯-约旦消元法（雾）
高斯消元多了一个我看起来完全没必要的回带操作（雾）
不管了不管了我写这篇博客本来就不是为了讲高斯消元
正题（雾）高斯消元套DP
在我们做DP的时候，有时候列出的方程满足无后效性，而有时候则不那么凑巧
处理有后效性的方法有很多，高斯消元就是其中一种
我们考虑无后效性的 DP是就像一元方程
而有后效性的就会出现多个未知数，正好满足高斯消元的条件
好了，咕咕咕，以后做多一点题再补充
近期评论