1、高斯消元法，是線性代數中的一個算法，可用來求解線性方程組，并可以求出矩陣的秩，以及求 出可逆方陣的逆矩陣。高斯消元法的原理是：若用初等行變換將增廣矩陣 化為，則AX = B與CX = D是同解方程組。所以我們可以用初等行變換把增廣矩陣轉換為行階梯陣，然后回代求出方程的解。以上是線性代數課的回顧，下面來說說高斯消元法在編程中的應用。首先，先介紹程序中高斯消元法的步驟：（我們設方程組中方程的個數為equ，變元的個數為var，注意：一般情況下是n個方程，n個變 元，但是有些題目就故意讓方程數與變元數不同）把方程組轉換成增廣矩陣。利用初等行變換來把增廣矩陣轉換成行階梯陣。枚舉k從0到equ - 1，當

2、前處理的列為col（初始為0），每次找第k行以下（包括第k行），col列中 元素絕對值最大的列與第k行交換。如果col列中的元素全為0，那么則處理col + 1列，k不變。轉換為行階梯陣，判斷解的情況。無解當方程中出現（0, 0,，0, a）的形式，且a != 0時，說明是無解的。唯一解條件是k = equ，即行階梯陣形成了嚴格的上三角陣。利用回代逐一求出解集。無窮解。條件是k k）。顯然如果akk特別小的話，不僅有可能損失精度，還有可能 造成出。為了避免這種情況，我們需要選取主元：在系數矩陣右下角選取n-k+1階子矩陣中絕對值最大的元素a”，交換第行與第i行，交換第 k列與殉列。注意到列的交

3、換會使得解的順序混亂，因此我們需要記錄列的交換過程，以便 最后還原。當然由于交換后akk的絕對值是最大的，所以如果akk=我們就可以直接終止 計算了，因為這時無法找到唯一的一組解。（選取主元的過程并不影響時間復雜度，整個過 程的時間復雜度仍然是O（n3）高斯約當消元法高斯約當消元法是一種不需要回代的消元法，可以算是高斯消元法的一種改進，它與高斯消 元法唯一的不同是：高斯約當消元法每次不僅要把主對角線以下的元素消為0,還要把主對角 線以上的元素消為0。自然消完后系數矩陣只有主對角線上有非0元素，所以就不需要回代了。其他解法除了高斯消元法與高斯約當消元法外，我們還可以使用迭代法或者共軛梯度法來解線

4、性方程 組。練習題zoj2296 Spread Sheethdu2449 Gauss EliminationNOIP2004 蟲食算參考資料徐士良數值分析與算法機械工業出版社何江舟用高斯消元法解線性方程組下面講解幾道OJ上的高斯消元法求解線性方程組的題目：POJ 1222 EXTENDED LIGHTS OUT HYPERLINK /JudgeOnline/prohlem?id=1222 /JudgeOnline/prohlem?id=1222POJ 1681 Painters Problem HYPERLINK /JudgeOnline/problem?id=1681 /JudgeOnlin

5、e/problem?id=1681POJ 1753 Flip Game HYPERLINK /JudgeOnline/problem?id=1753 /JudgeOnline/problem?id=1753POJ 1830開關問題 HYPERLINK /JiidgeOnline/problem?id=1830 /JiidgeOnline/problem?id=1830POJ 3185 The Water Bowls HYPERLINK /JudgeOnline/problem?id=3185 /JudgeOnline/problem?id=3185開關窗戶，開關燈問題，很典型的求解線性方程組的

6、問題。方程數和變量數均為行數*列數，直 接套模板求解即可。但是，當出現無窮解時，需要枚舉解的情況，因為無法判斷哪種解是題目要 求最優的。POJ 2947 Widget Factory HYPERLINK /JudgeOnline/problem?id=2947 /JudgeOnline/problem?id=2947求解同余方程組問題。與一般求解線性方程組的問題類似，只要在求解過程中加入取余即可。 注意：當方程組唯一解時，求解過程中要保證解在3, 9之間。POJ 1166 The Clocks HYPERLINK /JudgeOnline/problem?id=1166 /JudgeOnlin

7、e/problem?id=1166經典的BFS問題，有各種解法，也可以用逆矩陣進行矩陣相乘。但是這道題用高斯消元法解決好像有些問題（困擾了我N天持續困擾中），由于周期4不是素 數，故在求解過程中不能進行取余（因為取余可能導致解集變大），但最后求解集時，還是需要進 行取余操作，那么就不能保證最后求出的解是正確的在discuss里提問了好幾天也沒人回答. 希望哪位路過的大牛指點下POJ 2065 SETI HYPERLINK /JudgeOnline/problem?id=2065 /JudgeOnline/problem?id=2065同樣是求解同余方程組問題，由于題目中的p是素數，可以直接在求

8、解時取余，套用模板求解即 可。（雖然AC的人很少，但它還是比較水的一道題，）POJ 1487 Single-Player Games HYPERLINK /JudgeOnline/problem2idT487 /JudgeOnline/problem2idT487很麻煩的一道題目題目中的敘述貌似用到了編譯原理中的詞法定義（看了就給人不想做的感 覺.）解方程組的思想還是很好看出來了 （前提是通讀題目不下5遍.），但如果把樹的字符串表達式轉換 成方程組是個難點，我是用棧+遞歸的做法分解的。首先用棧的思想求出該結點的孩子數，然 后遞歸分別求解各個孩子。這題解方程組也與眾不同首先是求解浮點數方程組，要

9、注意精度問題，然后又詢問不確定的變 元，按前面說的方法求解。一頓折騰后，這題居然寫了6000+B.而且冏的是巨人C+ WA，G+ AC，可能還是精度的問題 吧看這題目，看這代碼，就沒有改的欲望hdu OJ 2449 HYPERLINK /showproblem.php?pid=2449 /showproblem.php?pid=2449哈爾濱現場賽的一道純高斯題，當時鶴牛敲了 1個多小時主要就是寫一個分數類，套個高精模 板（偷懶點就Java.）搞定注意下0和負數時的輸出即可。fze OJ 1704 HYPERLINK /problem.php?pid=1704 /problem.php?pid

10、=1704福大月賽的一道題目，還是經典的開關問題，但是方程數和變元數不同(考驗模板的時候到了)，最后要求增廣陣的階，要用到高精度這里提供下自己寫的還算滿意的求解整數線性方程組的模板(浮點數類似，就不提供了)/*用于求整數解得方程組.*/#include #include #include using namespace std;const int maxn = 105;int equ, var; /有equ個方程，var個變元。增廣陣行數為equ,分別為0到equ - 1，列數為var + 1， 分別為0到 amaxnmaxn;int xmaxn; / 解集.bool free_xmaxn;

11、/判斷是否是不確定的變元.int free_num;void Debug(void)(int i, j;for (i = 0; i equ; i+)(for (j = 0; j var + 1; j+)(cout aij ;cout endl;cout endl;inline int gcd(int a, int b)(int t;while (b != 0)(t = b;b = a % b;a = t;return a;inline int lcm(int a, int b)(return a * b / gcd(a, b);/高斯消元法解方程組(Gauss-Jordan eliminati

12、on).(-2表示有浮點數解，但無整數解，-1表示無解，0表示唯一解，大于0表示無窮解，并返回自由變元的個數)int Gauss(void)(int i, j, k;int max_r; /當前這列絕對值最大的行.int col; /當前處理的列.int ta, tb;int LCM;int temp;int free_x_num;int free_index;/轉換為階梯陣.col = 0; /當前處理的列.for (k = 0; k equ & col var; k+, col+)( /枚舉當前處理的行./找到該col列元素絕對值最大的那行與第k行交換.(為了在除法時減小誤差) max_r

13、 = k;for (i = k + 1; i abs(amax_rcol) max_r = i;if (max_r != k)( /與第k行交換.for (j = k; j var + 1; j+) swap(akj, amax_rj);if (akcol = 0)( /說明該col列第k行以下全是0了，則處理當前行的下一列.k-; continue;for (i = k + 1; i equ; i+)( /枚舉要刪去的行.if (aicol != 0)LCM = lcm(abs(aicol), abs(akcol);ta = LCM / abs(aicol), tb = LCM / abs(

14、akcol);if (aicol * akcol 0) tb = -tb; / 異號的情況是兩個數相加.for (j = col; j var + 1; j+)(aij = aij * ta - akj * tb;Debug();/ 1.無解的情況：化簡的增廣陣中存在(0,0, ., a)這樣的行(a != 0).for (i = k; i equ; i+)( /對于無窮解來說，如果要判斷哪些是自由變元，那么初等行變換中的交換就會影響，則 要記錄交換.if (aicol != 0) return -1;/ 2.無窮解的情況：在var * (var + 1)的增廣陣中出現(0,0, ., 0)這

15、樣的行，即說明沒有形成 嚴格的上三角陣./且出現的行數即為自由變元的個數.if (k = 0; i-)(/第i行一定不會是(0, 0, ., 0)的情況，因為這樣的行是在第k行到第equ行./同樣，第i行一定不會是(0, 0, ., a), a != 0的情況，這樣的無解的.free_x_num = 0; /用于判斷該行中的不確定的變元的個數，如果超過1個，則無法 求解，它們仍然為不確定的變元.for (j = 0; j 1) continue; /無法求解出確定的變元./說明就只有一個不確定的變元free_index，那么可以求解出該變元，且該變元是 確定的.temp = aivar;for

16、 (j = 0; j = 0; i-)(temp = aivar;for (j = i + 1; j var; j+)(if (aij != 0) temp -= aij * xj;if (temp % aii != 0) return -2; /說明有浮點數解，但無整數解. xi = temp / aii;return 0;int main(void)(freopen(Input.txt”, r, stdin);int i, j;while (scanf(%d %d, &equ, &var) != EOF)(memset(a, 0, sizeof(a);memset(x, 0, sizeof(x);memset(free_x, 1, sizeof(free_x); / 一開