高斯消元模板

照着czyuan的那个模板，手敲了一遍，存一下。

貌似今天一整天就看了一下高斯消元的知识，然后看了模板，又手敲了一遍。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <cmath>
  6 #include <algorithm>
  7 #define LL __int64
  8 const int maxn = 100+10;
  9 using namespace std;
 10 int equ, var, fn;
 11 int a[maxn][maxn], x[maxn];
 12 bool free_x[maxn];
 13 
 14 int gcd(int a, int b)
 15 {
 16     return b==0?a:gcd(b, a%b);
 17 }
 18 int lcm(int a, int b)
 19 {
 20     return a*b/gcd(a, b);
 21 }
 22 int Gauss()
 23 {
 24     int i, j, k, max_r, col;
 25     int ta, tb, LCM, tmp, fx_num;
 26     int free_index;
 27     col = 0;
 28 
 29     for(k = 0; k<equ && col<var; k++, col++)
 30     {
 31         max_r = k;
 32         for(i = k+1; i < equ; i++)
 33             if(abs(a[i][col])>abs(a[max_r][col]))
 34             max_r = i;
 35 
 36         if(max_r != k)
 37             for(j = k; j < var+1; j++)
 38             swap(a[k][j], a[max_r][j]);
 39 
 40         if(a[k][col]==0)
 41         {
 42             k--;
 43             continue;
 44         }
 45         for(i = k+1; i < equ; i++)
 46         {
 47             if(a[i][col] != 0)
 48             {
 49                 LCM = lcm(abs(a[i][col]), abs(a[k][col]));
 50                 ta = LCM/abs(a[i][col]);
 51                 tb= LCM/abs(a[k][col]);
 52                 if(a[i][col]*a[k][col] < 0) tb = -tb;
 53 
 54                 for(j = col; j < var+1; j++)
 55                 a[i][j] = a[i][j]*ta - a[k][j]*tb;
 56             }
 57         }
 58     }
 59     for(i = k; i < equ; i++)
 60     if(a[i][col] != 0)
 61     return -1;
 62 
 63     if(k < var)
 64     {
 65         for(i = k-1; i >= 0; i--)
 66         {
 67             fx_num = 0;
 68             for(j = 0; j < var; j++)
 69                 if(a[i][j]!=0 && free_x[j])
 70                 {
 71                     fx_num ++;
 72                     free_index = j;
 73                 }
 74             if(fx_num > 1) continue;
 75 
 76             tmp = a[i][var];
 77             for(j = 0; j < var; j++)
 78                 if(a[i][j] != 0 && j!=free_index)
 79                 tmp -= a[i][j]*x[j];
 80 
 81             x[free_index] = tmp/a[i][free_index];
 82             free_x[free_index] = 0;
 83         }
 84         return var-k;
 85     }
 86     for(i = var-1; i >= 0; i--)
 87     {
 88         tmp = a[i][var];
 89         for(j = i+1; j < var; j++)
 90         if(a[i][j] != 0)
 91         tmp -= a[i][j]*x[j];
 92 
 93         if(tmp%a[i][i] != 0) return -2;
 94         x[i] = tmp/a[i][i];
 95     }
 96     return 0;
 97 }
 98 int main()
 99 {
100     int i, j;
101     while(cin>>equ>>var)
102     {
103         memset(a, 0, sizeof(a));
104         memset(x, 0, sizeof(x));
105         memset(free_x, 1, sizeof(free_x));
106         for(i = 0; i < equ; i++)
107         {
108             for(j = 0; j < var+1; j++)
109             cin>>a[i][j];
110         }
111 
112         fn = Gauss();
113         if(fn == -1) cout<<"无解"<<endl;
114         else if(fn == -2)
115         cout<<"有浮点数解， 无整数解"<<endl;
116         else if(fn > 0)
117         {
118             printf("无穷多解! 自由变元个数为%d
", fn);
119             for(i = 0; i < var; i++)
120             {
121                 if(free_x[i]) printf("x%d行 是不确定的
", i + 1);
122                 else printf("x%d: %d
", i + 1, x[i]);
123             }
124         }
125         else
126         {
127             for(i = 0; i < var; i++)
128             printf("x%d: %d
", i + 1, x[i]);
129         }
130         cout<<endl;
131     }
132     return 0;
133 }

浮点型的模板

eps那里和整型不一样

 1 #define eps 1e-8
 2 const int maxn = 100+10;
 3 using namespace std;
 4 int equ, var;
 5 double a[maxn][maxn], x[maxn];
 6 
 7 int Gauss()
 8 {
 9     int i, j, k, max_r, col;
10     double tmp;
11     col = 0;
12 
13     for(k = 0; k<equ && col<var; k++, col++)
14     {
15         max_r = k;
16         for(i = k+1; i < equ; i++)
17             if(fabs(a[i][col])-fabs(a[max_r][col]) > eps)
18             max_r = i;
19 
20         if(max_r != k)
21             for(j = k; j < var+1; j++)
22             swap(a[k][j], a[max_r][j]);
23 
24         if(fabs(a[k][col]) < eps)
25         {
26             k--;
27             continue;
28         }
29         for(i = k+1; i < equ; i++)
30         {
31             if(fabs(a[i][col]) > eps)
32             {
33                 double t = a[i][col]/a[k][col];  //这里和整型的不同。
34                 a[i][col] = 0.0;
35 
36                 for(j = col; j < var+1; j++)
37                 a[i][j] -= a[k][j]*t;
38             }
39         }
40     }
41     for(i = var-1; i >= 0; i--)
42     {
43         if(fabs(a[i][i]) < eps) continue;
44         tmp = a[i][var];
45         for(j = i+1; j < var; j++)
46         if(a[i][j] != 0)
47         tmp -= a[i][j]*x[j];
48 
49         //if(tmp%a[i][i] != 0) return -2;
50         x[i] = tmp/a[i][i];
51     }
52     return 0;
53 }

模mo的情况下的模板：

根据上面的模板改的，但是正确性有待验证

 1 int gcd(int a, int b)
 2 {
 3     return b==0?a:gcd(b, a%b);
 4 }
 5 int lcm(int a, int b)
 6 {
 7     return a*b/gcd(a, b);
 8 }
 9 int Gauss()
10 {
11     int x_mo;
12     x_mo = 2;  //初始化为2了。
13     int i, j, k, max_r, col;
14     int ta, tb, LCM, tmp, fx_num;
15     int free_index;
16     col = 0;
17 
18     for(k = 0; k<equ && col<var; k++, col++)
19     {
20         max_r = k;
21         for(i = k+1; i < equ; i++)
22             if(abs(a[i][col])>abs(a[max_r][col]))
23                 max_r = i;
24 
25         if(max_r != k)
26             for(j = k; j < var+1; j++)
27                 swap(a[k][j], a[max_r][j]);
28 
29         if(a[k][col]==0)
30         {
31             k--;
32             continue;
33         }
34         for(i = k+1; i < equ; i++)
35         {
36             if(a[i][col] != 0)
37             {
38                 LCM = lcm(abs(a[i][col]), abs(a[k][col]));
39                 ta = LCM/abs(a[i][col]);
40                 tb= LCM/abs(a[k][col]);
41                 if(a[i][col]*a[k][col] < 0) tb = -tb;
42 
43                 for(j = col; j < var+1; j++)
44                     a[i][j] = ((a[i][j]*ta - a[k][j]*tb)%x_mo+x_mo)%x_mo;
45             }
46         }
47     }
48     for(i = k; i < equ; i++)
49         if(a[i][col] != 0)
50             return -1;
51 
52     if(k < var)  //正确性有待验证
53     {
54         for(i = k-1; i >= 0; i--)
55         {
56             fx_num = 0;
57             for(j = 0; j < var; j++)
58                 if(a[i][j]!=0 && free_x[j])
59                 {
60                     fx_num ++;
61                     free_index = j;
62                 }
63             if(fx_num > 1) continue;
64 
65             tmp = a[i][var];
66             for(j = 0; j < var; j++)
67                 if(a[i][j] != 0 && j!=free_index)
68                     tmp = ((tmp-a[i][j]*x[j])%x_mo+x_mo)%x_mo;
69             if(a[i][free_index]==0)  //这里我也改了，因为也会出现0的情况。
70                 x[free_index] = 0;
71             else
72             {
73                 while(tmp%a[i][free_index]!=0)  //正确性有待验证
74                     tmp += x_mo;  //正确性有待验证
75                 x[free_index] = (tmp/a[i][free_index])%x_mo; //正确性有待验证
76             }
77             free_x[free_index] = 0;
78         }
79         return var-k;
80     }
81 
82     for(i = var-1; i >= 0; i--)
83     {
84         tmp = a[i][var];
85         for(j = i+1; j < var; j++)
86             if(a[i][j] != 0)
87                 tmp = ((tmp-a[i][j]*x[j])%x_mo+x_mo)%x_mo;
88 
89         if(a[i][i]==0) //这我改了，因为做题的时候发现有a[][]等于0的情况，会出现除0
90             x[i] = 0;
91         else
92         {
93             if(tmp%a[i][i] != 0) return -2;  //这个的位置应该放这。
94             while(tmp%a[i][i]!=0) tmp += x_mo;
95             x[i] = (tmp/a[i][i])%x_mo;
96         }
97     }
98     return 0;
99 }

这个和上面的模板不一样，也有判断多解和无解的情况。

 1 int Gauss ()
 2 {
 3     int x_mo;
 4     x_mo = 7;  //初始为7了。
 5     int i, j, mr, row, col;
 6     int ta, tb, l, tmp;
 7     row = col = 0;
 8     while ( row < equ && col < var )
 9     {
10         mr = row;
11         for ( i = row + 1; i < equ; i++ )
12             if ( abs(a[i][col]) > abs(a[mr][col]) ) mr = i;
13 
14 
15         if ( mr != row )
16             for ( j = col; j <= var; j++ )
17                 swap ( a[row][j], a[mr][j] );
18         if ( a[row][col] == 0 )
19         {
20             col++;
21             continue;
22         }
23 
24 
25         for ( i = row + 1; i < equ; i++ )
26         {
27             if ( a[i][col] != 0 )
28             {
29                 l = lcm(abs(a[i][col]), abs(a[row][col]));
30                 ta = l / abs(a[i][col]), tb = l / abs(a[row][col]);
31                 if ( a[i][col] * a[row][col] < 0 ) tb = -tb;
32                 for ( j = col; j <= var; j++ )
33                     a[i][j] = ((a[i][j]*ta-a[row][j]*tb)%x_mo+x_mo) % x_mo;
34             }
35         }
36         row++;
37         col++;
38     }
39 
40     for ( i = row; i < equ; i++ )
41         if ( a[i][var] != 0 ) return -1;
42 
43 
44     if ( row < var )
45         return var - row;
46 
47 
48     for ( i = var - 1; i >= 0; i-- )
49     {
50         tmp = a[i][var];
51         for ( j = i + 1; j < var; j++ )
52             tmp = ((tmp-a[i][j]*x[j])%x_mo+x_mo)%x_mo;
53         while ( tmp % a[i][i] != 0 ) tmp += x_mo;
54         x[i] = ( tmp / a[i][i] ) % x_mo;
55     }
56     return 0;
57 }

这个是判断模2 情况下的模板，注意只是模2，不会出现除0的情况，但是没有找自由变元的处理：

 1 int  Gauss()
 2 {
 3     int i,j,k;
 4     int max_r;
 5     int col;
 6     int temp;
 7 
 8     int free_x_num;
 9     int free_index;
10 
11     col=0;
12     for(k=0;k<equ&&col<var;k++,col++)
13     {
14         max_r=k;
15         for(i=k+1;i<equ;i++)
16         {
17             if(abs(a[i][col])>abs(a[max_r][col]))max_r=i;
18         }
19         if(max_r!=k)
20         {
21             for(j=col;j<var+1;j++)swap(a[k][j],a[max_r][j]);
22         }
23         if(a[k][col]==0)
24         {
25             k--;
26             continue;
27         }
28         for(i=k+1;i<equ;i++)
29         {
30             if(a[i][col]!=0)
31             {
32                 for(j=col;j<var+1;j++)
33                   a[i][j]^=a[k][j];
34             }
35         }
36     }
37     for(i=k;i<equ;i++)
38     {
39         if(a[i][col]!=0)return -1;//无解
40     }
41 
42     if(k < var)
43     return var-k;
44 
45     for(i=var-1;i>=0;i--)
46     {
47         x[i]=a[i][var];
48         for(j=i+1;j<var;j++)
49           x[i]^=(a[i][j]&&x[j]);
50     }
51     return 0;
52 }

高斯消元 模板

高斯消元模板