详细的高斯消元法求解线性方程组的解的c代码。虽然博主的代码有点乱，可是他的解释还是很清楚的，而且也给出了一些oj上的用高斯消元法求解的题目 http://hi.baidu.com/czyuan_acm/blog/item/ebf41f8fdc0e1ee6f01f36e9.html
poj 2947 http://poj.org/problem?id=2947
题目的意思就是：给你 n 种零件和 m 个技术工人，然后有 2 * m行输入，首先给一个 k 表示该技术工人在他工作时间内生产了哪些种类的零件，然后给出这个工人开始工作的星期数，和结束工作的星期数。问 n 种不同的零件各用多少天生产，如果解唯一，则输出该解。如果解不唯一和无解时按题目要求输出
思路：设 n 种零件所需要 的天数为 x1 ，x2 ，x3 ，~~~~ xn。
则根据m个技术工人的工作时间和生产的零件种类可以列出方程 m个这样的方程
(a1 * x1 + a2 * x2 + a3 * x3 ~~~~~ an * xn ) % 7 = 工作天数
注意题目提到每个零件的生产时间最多是9天，最少是3天
View Code
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <math.h> 5 #include <string> 6 #include <stdlib.h> 7 #include <map> 8 #include <algorithm> 9 #define N 310 10 #define _clr(a,val) (memset(a,val,sizeof(a))) 11 12 using namespace std; 13 14 map<string,int>ma; 15 int a[N][N]; 16 int equ,val; 17 int x[N],flag; 18 int gcd(int a,int b) 19 { 20 if(!b) return a; 21 else return gcd(b,a % b); 22 } 23 int lcm(int a,int b) 24 { 25 int t_gcd = gcd(a,b); 26 return a / t_gcd * b; 27 } 28 int guass() 29 { 30 int i,j,k; 31 int max_r,col,ta,tb,lc,temp; 32 col = 0; 33 for(k = 0; k < equ && col < val; k++,col++) 34 { 35 max_r = k; 36 for(i = k + 1; i < equ; i++) 37 { 38 if(abs(a[i][col]) > abs(a[max_r][col])) max_r = i; 39 } 40 if(max_r != k) 41 { 42 for(j = k; j < val + 1; j++) 43 swap(a[k][j],a[max_r][j]); 44 } 45 if(a[k][col] == 0) 46 { 47 k--;continue; 48 } 49 for(i = k + 1; i < equ; i++) 50 { 51 if(a[i][col] != 0) 52 { 53 lc = lcm(abs(a[i][col]),abs(a[k][col])); 54 ta = lc / abs(a[i][col]) ,tb = lc / abs(a[k][col]); 55 if(a[i][col] * a[k][col] < 0) tb = -tb; 56 for(j = 0; j < val + 1; j++) 57 { 58 a[i][j] = ((a[i][j] * ta) % 7 - (a[k][j] * tb) % 7 + 7) % 7; 59 } 60 } 61 } 62 } 63 for(i = k ; i < equ; i++) 64 if(a[i][col] % 7 != 0) return -1; 65 if(k < val) return 1; 66 for(i = val - 1; i >= 0; i--) 67 { 68 temp = a[i][val]; 69 for(j = i + 1; j < val; j++) 70 if(a[i][j] != 0) temp -= a[i][j] * x[j]; 71 while(temp % a[i][i] != 0) temp += 7; 72 x[i] = temp / a[i][i]; 73 if(x[i] < 3) 74 { 75 while(x[i] < 3) x[i] += 7; 76 if(x[i] > 9) flag = 1; 77 } 78 else if(x[i] > 9) 79 { 80 while(x[i] > 9) x[i] -= 7; 81 if(x[i] < 3) flag = 1; 82 } 83 } 84 return 0; 85 } 86 int main() 87 { 88 int i; 89 int n,m,k; 90 string st,sb; 91 int tx; 92 //freopen("data.txt","r",stdin); 93 ma["MON"] = 1; 94 ma["TUE"] = 2; 95 ma["WED"] = 3; 96 ma["THU"] = 4; 97 ma["FRI"] = 5; 98 ma["SAT"] = 6; 99 ma["SUN"] = 7; 100 while(scanf("%d%d",&n,&m) != EOF) 101 { 102 if(!n && !m) break; 103 _clr(a,0); 104 _clr(x,0); 105 for(i = 0; i < m; i++) 106 { 107 cin>>k>>st>>sb; 108 int tval = ma[sb] - ma[st] + 1; 109 while(k--) 110 { 111 scanf("%d",&tx); 112 a[i][tx - 1] ++; 113 a[i][tx - 1] %= 7; 114 } 115 a[i][n] = tval % 7; 116 } 117 equ = m, val = n; 118 flag = 0; 119 int ans = guass(); 120 if(ans == -1) printf("Inconsistent data.\n"); 121 else if(ans == 1) printf("Multiple solutions.\n"); 122 else 123 { 124 if(flag) {printf("Inconsistent data.\n");} 125 else 126 { 127 cout<<x[0]; 128 for(i = 1; i < val; i++) 129 printf(" %d",x[i]); 130 printf("\n"); 131 } 132 } 133 } 134 return 0; 135 }
poj 2065 http://poj.org/problem?id=2065 这道题目一开始读题就读了好长时间啊，因为没有在意题目上面的it was discovered that if each message is assumed to be transmitted as a sequence of integers a0, a1, ...an-1 the function f (k) = ∑0<=i<=n-1aiki (mod p) always evaluates to values 0 <= f (k) <= 26 for 1 <= k <= n, provided that the correct value of p is used这句话，所以一直不知道这个线性方程怎么构造
注意到f (k) = ∑0<=i<=n-1aiki (mod p)，就可以知道每个变量的系数是就是根据这个函数求出来的，增光矩阵的最后一列就是给出的一串字符串转化为整型数字
思路：知道线性方程怎么构造后，直接根据高斯消元法的模板就可以求出了。其实这个比2947还要简单，因为这个不需要判断是否有多组解和无解的情况
View Code
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <algorithm> 5 #define N 80 6 #define _clr(a,va) (memset(a,va,sizeof(a))) 7 8 using namespace std; 9 10 typedef long long ll; 11 int mod; 12 int equ,val; 13 ll a[N][N],x[N]; 14 inline ll f(ll x,ll y) // 快速幂求线性方程系数 15 { 16 ll tmp = 1; 17 while(y--) 18 { 19 tmp = tmp * x % mod; 20 } 21 return tmp; 22 } 23 ll gcd(ll a,ll b) 24 { 25 if(!b) return a; 26 else return gcd(b, a % b); 27 } 28 ll LCM(ll a,ll b) 29 { 30 return a / gcd(a,b) * b; 31 } 32 void gaos() 33 { 34 int i,k,j,max_r; 35 ll ta,tb,temp,lc; 36 int col = 1; 37 for(k = 1; k <= equ && col <= val; k++,col++) 38 { 39 max_r = k; 40 for(i = k + 1; i <= equ; i++) 41 { 42 if(abs(a[i][col]) > abs(a[k][col])) 43 max_r = i; 44 } 45 if(max_r != k) 46 { 47 for(i = col; i <= val + 1; i++) 48 swap(a[max_r][i],a[k][i]); 49 } 50 if(a[k][col] == 0) {k--;continue;} 51 for(i = k + 1; i <= equ; i++) 52 { 53 lc = LCM(abs(a[i][col]),abs(a[k][col])); 54 ta = lc / abs(a[i][col]), tb = lc / abs(a[k][col]); 55 if(a[i][col] * a[k][col] < 0) tb = -tb; 56 for(j = col; j <= val + 1; j++) a[i][j] = (a[i][j] * ta - a[k][j] * tb) % mod; 57 } 58 } 59 { 60 _clr(x,0); 61 for(i = val; i >= 1; i--) 62 { 63 temp = a[i][val + 1]; 64 for(j = i + 1;j <= val; j++) 65 { 66 temp -= a[i][j] * x[j]; 67 } 68 while(temp % a[i][i]) temp += mod; 69 x[i] = temp / a[i][i]; 70 x[i] = (x[i] % mod + mod) % mod; 71 } 72 } 73 printf("%lld",x[1]); 74 for(i = 2; i <= val; i++) 75 { 76 printf(" %lld",x[i]); 77 } 78 printf("\n"); 79 } 80 int main() 81 { 82 //freopen("data.txt","r",stdin); 83 int cas,j,i; 84 char s1[100]; 85 scanf("%d",&cas); 86 while(cas--) 87 { 88 _clr(a,0); 89 scanf("%d %s",&mod,s1); 90 int len = strlen(s1); 91 equ = len, val = len; 92 for(i = 0; i < len; i++) 93 { 94 if(s1[i] == '*') a[i + 1][len + 1] = 0; // 转化字符串为增广矩阵的最后一列 95 else a[i + 1][len + 1] = (s1[i] - 'a' + 1); 96 for(j = 1; j <= len; j++) 97 a[i + 1][j] = f(i + 1,j - 1); 98 } 99 gaos(); 100 } 101 return 0; 102 }