高斯消元——数学知识

1.高斯消元解线性方程组：

883. 高斯消元解线性方程组 - AcWing题库

步骤：

　　c=0，r=0 （c是列，r是行）

　　枚举每一列c

　　　　找到c列对应绝对值最大的那一行t

　　　　将t行移到r行（目前的顶部）

　　　　将转换后的r行c列系数变为1

　　　　将大于r的行的c列系数全消为0

 1 #include 
 2 using namespace std;
 3 const int N=120;
 4 const double eps=1e-6;
 5 int n;
 6 double a[N][N];
 7 
 8 int guass()
 9 {
10     int col,row;
11     for(col=0,row=0;col)
12     {
13         int t=row;
14         for(int i=t;i)
15         {
16             if(fabs(a[i][col])>fabs(a[t][col]))
17                 t=i;
18         }
19         if(fabs(a[t][col])continue;    //如果找到的绝对值最大为0，那就没必要进行之后的步骤了
20         
21         for(int i=0;i<=n;i++)swap(a[t][i],a[row][i]);
22         
23         for(int i=n;i>=col;i--)a[row][i]/=a[row][col];      //从后往前计算，防止首位数值被污染
24         for(int i=row+1;i)
25         {
26             if(fabs(a[i][col])continue;
27             for(int j=n;j>=col;j--)                         //从后往前计算，防止首位数值被污染
28             {
29                 a[i][j]-=a[row][j]*a[i][col];
30             }
31         }
32         
33         row++;
34     }
35     
36     if(row<n)
37     {
38         for(int i=row;i)
39             if(fabs(a[i][n])>eps)return 2;      //0！= （！0）
40         return 1;
41     }
42     else
43     {
44         for(int i=n-1;i>=0;i--)
45         {
46             for(int j=i+1;j)
47                 a[i][n]-=a[j][n]*a[i][j];
48         }
49         return 3;
50     }
51     
52 }
53 
54 int main()
55 {
56     scanf("%d",&n);
57     for(int i=0;i)
58         for(int j=0;j<=n;j++)
59             scanf("%lf",&a[i][j]);
60     
61     
62     int ans=guass();
63     if(ans==1)puts("Infinite group solutions");
64     else if(ans==2)puts("No solution");
65     else if(ans==3)
66     {
67         for(int i=0;i)
68         {
69             if(fabs(a[i][n])"0.00");
70             else printf("%.2lf\n",a[i][n]);
71         }
72     }
73     
74     
75     
76     return 0;
77 }

2.高斯消元解异或线性方程组：

884. 高斯消元解异或线性方程组 - AcWing题库

中心思想：把异或运算看作不会进位的加法就可以啦

步骤：　

　　c=0，r=0 （c是列，r是行）

　　枚举每一列c

　　　　找到c列对应的第一个系数为1的那一行t

　　　　将t行移到r行（目前的顶部）

　　　　将大于r的行的c列系数全消为0

 1 #include 
 2 using namespace std;
 3 const int N=120;
 4 int n,a[N][N];
 5 
 6 int guass()
 7 {
 8     int col,row;
 9     for(col=0,row=0;col)
10     {
11         int t=row;
12         for(int i=row;i)
13         {
14             if(a[i][col])
15             {
16                 t=i;
17                 break;
18             }
19         }
20         if(!a[t][col])continue;
21         
22         for(int i=col;i<=n;i++)swap(a[t][i],a[row][i]);
23         
24         for(int i=row+1;i)
25         {
26             if(a[i][col])
27             {
28                 for(int j=n;j>=col;j--)
29                     a[i][j]^=a[row][j];
30             }
31         }
32         row++;
33     }
34     
35     if(row<n)
36     {
37         for(int i=row;i)
38             if(a[i][n])return 2;
39         return 1;
40     }
41     
42     for(int i=n-1;i>=0;i--)
43     {
44         for(int j=i+1;j)
45         {
46             a[i][n]^=a[j][n]*a[i][j];
47         }
48     }
49     return 3;
50 }
51 
52 int main()
53 {
54     scanf("%d",&n);
55     for(int i=0;i)
56         for(int j=0;j<=n;j++)
57             scanf("%d",&a[i][j]);
58             
59     int ans=guass();
60     if(ans==1)puts("Multiple sets of solutions");
61     else if(ans==2)puts("No solution");
62     else if(ans==3)
63     {
64         for(int i=0;i"%d\n",a[i][n]);
65     }
66     
67     
68     return 0;
69 }