数论---高斯消元

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <cmath>
 5 using namespace std;
 6 const double ac = 1e-8;
 7 const int N = 105;
 8 int n;
 9 double a[N][N];
10 int gs()
11 {
12     int r, c;
13     //根据高斯消元,每一行必须有个数(除了=右边的数)不为0
14     //否则,要不就是无解，要不就是有无数解
15     //所以我们是一行一行来看,确定每一行中有个数不为0
16     // r用来记录异常行,枚举列c
17     for (r = 0, c = 0; c < n; c++)
18     {
19         //找出第c列中第r~n行中绝对值最大数
20         int t = r;
21         for (int i = r; i < n; i++)
22             if (fabs(a[t][c]) < fabs(a[i][c]))
23                 t = i;
24         //如果这一列各行均为0,到下一列去看
25         //跳过了r++
26         if (fabs(a[t][c]) < ac)
27             continue;
28         //交换行
29         for (int i = c; i < n + 1; i++)
30             swap(a[t][i], a[r][i]);
31         //将第r行第c列数变为1,这一行的其他数相应改变
32         for (int i = n; i >= c; i--)
33             a[r][i] /= a[r][c];
34         //将第c列第r~n行的数全变成0,第c+1~n+1列第r~n行的数相应改变
35         //根据第c列第r+k行的数改变时,根据a[r+k][c]来改变的
36         //先枚举行
37         for (int i = r + 1; i < n; i++)
38             if (fabs(a[i][c]) > ac)
39                 for (int j = n; j >= c; j--)
40                     a[i][j] -= a[r][j] * a[i][c];
41         r++;
42     }
43     if (r < n)
44     {
45         //异常行,说明下面每一行都是0,枚举=右边的数，判断是无解还是无穷解
46         for (int i = r; i < n; i++)
47             if (fabs(a[i][n]) > ac)
48                 return 2;
49         return 1;
50     }
51     //向上逆算
52     //能到这一步，说明是个规范的样子
53     //枚举列
54     for (int i = n - 1; i >= 0; i--)
55     {
56         //枚举行
57         for (int j = i - 1; j >= 0; j--)
58             if (fabs(a[j][i]) > ac)
59                 a[j][n] -= a[j][i] * a[i][n];
60     }
61     return 0;
62 }
63 int main()
64 {
65     scanf("%d", &n);
66     for (int i = 0; i < n; i++)
67     {
68         for (int j = 0; j < n + 1; j++)
69             scanf("%lf", &a[i][j]);
70     }
71     int res = gs();
72     if (res == 0)
73         for (int i = 0; i < n; i++)
74         {
75             //消除-0.00的情况
76             if (fabs(a[i][n]) < ac)
77                 a[i][n] = 0;
78             printf("%.2lf\n", a[i][n]);
79         }
80     else if (res == 1)
81         printf("Infinite group solutions\n");
82     else
83         printf("No solution\n");
84     return 0;
85 }