线性方程组

题面:

模板高斯消元加强版。

给你$n$个方程其中含有$n$个未知数,判段方程是否有唯一解。若方程有无数个解,输出$0$,若方程无解,输出$-1$,若方程有唯一解,输出该解。

输入格式:

第一行:未知数的个数。以下$n$行$n+1$列:分别表示每一格方程的系数及方程右边的值。

输出格式:

如果方程组无实数解输出$-1$;

如果有无穷多实数解,输出$0$;

如果有唯一解,则输出解(小数点后保留两位小数)。

输入输出样例

输入样例#1: 输出样例#1:

3 x1=1.00
2 -1 1 1 x2=0
4 1 -1 5 x3=-1.00
1 1 1 0

思路

这题和高斯消元模板题一样,只是多了一个判定方程是无穷解还是无解。

无解情况是高斯消元完后方程左边的系数全为0,但方程右边不为0。

无穷解的情况是:高斯消元完后存在某一行或多行全为0。

唯一解就是不满足上述的情况。

但这题一个比较麻烦的小细节是:

洛谷P3389中的高斯消元我们是在消元的过程中发现当前行的当前要消的列的系数为0就返回false。很遗憾在这一题行不通。(什么?你问我为什么,请看一下hack数据)

Input(hack)

3
0 0 1 2
0 0 1 1
0 0 0 0

Output(hack)

-1

再发一组hack数据吧。

Input:

3
4 2 3 1
4 1 2 3
5 2 3 3

Output:

x1=2.00
x2=1.00
x3=-3.00

注:因为本题数据太水,你可能也过了,但我们追求的是正确的解法和能力的提高不是吗?

同时这一题貌似还卡精度。

所以我们可以这样处理:

遇到当前要消去的列(最大绝对值)的系数为0,就跳过,直到找到一个不为零的项为止。

代码
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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 55;
const double eps = 1e-8;
int n;
double a[maxn][maxn],del;
int main()
{
cin >> n;
for(int i = 1 ; i <= n ; ++ i)
for(int j = 1 ; j <= n + 1; ++ j)
cin >> a[i][j];
for(int i = 1 ,c = 1; i <= n ; ++ i)//枚举列,c为行
{
int k = c;
for(int j = c + 1 ; j <= n ; ++ j)if(fabs(a[j][i]) > fabs(a[k][i]))k = j;//枚举列(交换用)
if(fabs(del = a[k][i]) < eps)continue;
// 如果当前列为0,说明后面的所有都为0,接着枚举该行
// {
// many = 1;
// continue;
// }
for(int j = i ; j <= n + 1 ; ++ j)swap(a[c][j],a[k][j]);
for(int j = i ; j <= n + 1 ; ++ j)a[c][j] /= del;
for(int k = 1 ; k <= n ; ++ k)
if(k != c){
del = a[k][i];
for(int j = i ; j <= n + 1 ; ++ j)a[k][j] -= a[c][j] * del;
}
++ c;
}
/* for(int i = 1 ; i <= n ; ++ i)
{
for(int j = 1 ; j <= n + 1; ++ j)
cout << a[i][j] << " ";
cout << endl;
}*/
bool many = 0;
for(int i = 1 ; i <= n ; ++ i)
{
bool noanw = 0;
for(int j = 1 ; j <= n ; ++ j)
if(a[i][j])noanw = 1;
if(!noanw and a[i][n + 1]){
cout << -1 << endl;
return 0;
}
if(!noanw and !a[i][n + 1])
many = 1;
}
if(many){
cout << 0 << endl;
return 0;
}
for(int i = 1 ; i <= n ; ++ i)
printf("x%d=%.2lf\n",i,a[i][n + 1]);
}