題目：http://poj.org/problem?id=1222

?

題意：5*6矩陣中有30個燈，操作一個燈，周圍的上下左右四個燈會發(fā)生相應變化 即由滅變亮，由亮變滅，如何操

???? 作使燈全滅？

?

分析：這個問題是很經典的高斯消元問題。同一個按鈕最多只能被按一次，因為按兩次跟沒有按是一樣的效果。那么

???? 對于每一個燈，用1表示按，0表示沒有按，那么每個燈的狀態(tài)的取值只能是0或1。列出30個方程，30個變

???? 元，高斯消元解出即可，因為解只能是0或者1，所以方程組是一定有解。

?

代碼：

#include <iostream> #include <string.h> #include <algorithm> #include <stdio.h> #include <math.h>using namespace std; const int N = 35;int gcd(int a,int b) {return b ? gcd(b,a%b):a; }int lcm(int a,int b) {return a / gcd(a,b) * b; }void Gauss(int a[][N],int n,int m,int &r,int &c) {r = c = 0;for(; r<n && c<m; r++,c++){int maxi = r;for(int i=r+1; i<n; i++)if(abs(a[i][c]) > abs(a[maxi][c]))maxi = i;if(maxi != r){for(int i=r; i<m+1; i++)swap(a[r][i],a[maxi][i]);}if(a[r][c] == 0){r--;continue;}for(int i=r+1; i<n; i++){if(a[i][c] != 0){int x = abs(a[i][c]);int y = abs(a[r][c]);int LCM = lcm(x,y);int tx = LCM / x;int ty = LCM / y;if(a[i][c] * a[r][c] < 0)ty = -ty;for(int j=c; j<m+1; j++)a[i][j] = ((a[i][j] % 2 * tx % 2 - a[r][j] % 2 * ty % 2) % 2 + 2) % 2;}}} }int Rewind(int a[][N],int x[],int r,int c) {for(int i=r-1; i>=0; i--){int t = a[i][c] % 2;for(int j=i+1; j<c; j++){if(a[i][j] != 0)t -= a[i][j] % 2 * x[j] % 2;}x[i] = t / a[i][i] % 2;x[i] = (x[i] + 2) % 2;}return 0; }int a[N][N]; int x[N];int main() {int cas = 1;int n,m,T;scanf("%d",&T);while(T--){n = m = 30;memset(a,0,sizeof(a));for(int i=0; i<5; i++){for(int j=0; j<6; j++){if(i >= 1) a[6*i+j][6*(i-1)+j] = 1;if(i <= 3) a[6*i+j][6*(i+1)+j] = 1;if(j >= 1) a[6*i+j][6*i+j-1] = 1;if(j <= 4) a[6*i+j][6*i+j+1] = 1;a[6*i+j][6*i+j] = 1;scanf("%d",&a[6*i+j][30]);}}int r,c;int cnt = 0;Gauss(a,n,m,r,c);Rewind(a,x,r,c);printf("PUZZLE #%d\n",cas++);for(int i=0; i<30; i++){cnt++;if(cnt % 6) printf("%d ",x[i]);else printf("%d\n",x[i]);}}return 0; }

?

題目：http://poj.org/problem?id=1830

?

題意：給定個開關，其中，然后給定這個開關的初始狀態(tài)和最終狀態(tài)，再給定一些關系，表示操作一

???? 個開關另一些開關的變化情況，求有多少種方法能從初始狀態(tài)變?yōu)樽罱K狀態(tài)。

?

分析：如果只有唯一解，則輸出1，如果有多個變元，變元個數為，那么答案等于，否則沒有解。

?

代碼：

#include <iostream> #include <string.h> #include <algorithm> #include <stdio.h> #include <math.h>using namespace std; typedef long long LL; const int N = 35;int gcd(int a,int b) {return b ? gcd(b,a%b):a; }int lcm(int a,int b) {return a / gcd(a,b) * b; }void Gauss(int a[][N],int n,int m,int &r,int &c) {r = c = 0;for(; r<n && c<m; r++,c++){int maxi = r;for(int i=r+1; i<n; i++)if(abs(a[i][c]) > abs(a[maxi][c]))maxi = i;if(maxi != r){for(int i=r; i<m+1; i++)swap(a[r][i],a[maxi][i]);}if(a[r][c] == 0){r--;continue;}for(int i=r+1; i<n; i++){if(a[i][c] != 0){int x = abs(a[i][c]);int y = abs(a[r][c]);int LCM = lcm(x,y);int tx = LCM / x;int ty = LCM / y;if(a[i][c] * a[r][c] < 0)ty = -ty;for(int j=c; j<m+1; j++)a[i][j] = ((a[i][j] % 2 * tx % 2 - a[r][j] % 2 * ty % 2) % 2 + 2) % 2;}}} }LL Rewind(int a[][N],int n,int m,int r,int c) {for(int i=r; i<n; i++)if(a[i][c] != 0)return -1;if(m == r) return 1;if(m > r) return (LL)1<<(m-r);if(m < r) return -1; }int a[N][N]; int t1[N],t2[N];int main() {int T;scanf("%d",&T);while(T--){int num,n,m;scanf("%d",&num);n = m = num;memset(a,0,sizeof(a));for(int i=0; i<num; i++)scanf("%d",&t1[i]);for(int i=0; i<num; i++){scanf("%d",&t2[i]);if(t2[i] != t1[i])a[i][num] = 1;a[i][i] = 1;}while(1){int x,y;scanf("%d%d",&x,&y);if(x == 0 && y == 0) break;a[y-1][x-1] = 1;}int r,c;Gauss(a,n,m,r,c);LL ans = Rewind(a,n,m,r,c);if(ans == -1) puts("Oh,it's impossible~!!");else printf("%I64d\n",ans);}return 0; }

?

題目：http://acm.hdu.edu.cn/showproblem.php?pid=3359

?

題意：有一個圖像模糊處理的算法，圖像設置為一定灰度后是一個不太大的矩陣，對這個矩陣通過一個算法處理后得

???? 到另一個矩陣，那么圖像就會變得模糊，這個算法就是求某個元素周圍距離在內的平均值。現在給定模糊圖

???? 像的矩陣，把它還原為清晰圖像對應的矩陣。具體變換如下圖所示

?

????????????????

?

?

分析：這個題比較有意思，涉及到圖像處理的算法，當然這個我們可以設每個矩陣里的元素對應一個未知數，那么一

???? 共有個未知數，而某個元素在距離為以內的所有元素都與它有關系，那么可以得到個方程形成的

???? 方程組。注意這里的數字為實數，所以不必像整數求最大公約數那樣消元，直接做就行了。

?

代碼：

#include <iostream> #include <string.h> #include <algorithm> #include <stdio.h> #include <math.h>using namespace std; const int N = 105;void Gauss(double a[][N],int n,int m,int &r,int &c) {r = c = 0;for(; r<n && c<m; r++,c++){int maxi = r;for(int i=r+1; i<n; i++)if(fabs(a[i][c]) > fabs(a[maxi][c]))maxi = i;if(maxi != r){for(int i=r; i<m+1; i++)swap(a[r][i],a[maxi][i]);}for(int i=r+1; i<n; i++){if(a[i][c]){double t = -a[i][r] / a[r][r];for(int j=r; j<m+1; j++)a[i][j] += t * a[r][j];}}} }void Rewind(double a[][N],double x[],int n,int m,int r,int c) {for(int i=r-1; i>=0; i--){double t = a[i][c];for(int j=i+1; j<c; j++)t -= a[i][j] * x[j];x[i] = t / a[i][i];} }int dist(int x1,int y1,int x2,int y2) {return abs(x1 - x2) + abs(y1 - y2); }double a[N][N]; double t[N][N]; double x[N];int main() {int n,m;int w,h,d;bool flag = 1;while(scanf("%d%d%d",&w,&h,&d)!=EOF){if(w == 0 && h == 0 && d == 0) break;if(flag) flag = 0;else puts("");for(int i=0; i<h; i++){for(int j=0; j<w; j++)scanf("%lf",&t[i][j]);}n = m = w * h;memset(a,0,sizeof(a));for(int i=0; i<h; i++){for(int j=0; j<w; j++){int cnt = 0;for(int k=0; k<h; k++){for(int r=0; r<w; r++){if(dist(i,j,k,r) <= d){a[i*w+j][k*w+r] = 1;cnt++;}}}a[i*w+j][m] = t[i][j] * cnt;}}int r,c;Gauss(a,n,m,r,c);Rewind(a,x,n,m,r,c);for(int i=0; i<h; i++){for(int j=0; j<w; j++)printf("%8.2f",x[i*w+j]);puts("");}}return 0; }

?

?

?

總結

以上是生活随笔為你收集整理的高斯消元基础题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。