高斯消元法是線性代數(shù)中的一個(gè)算法可用來(lái)求解線性方

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

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

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

4、性方程 組。練習(xí)題zoj2296 Spread Sheethdu2449 Gauss EliminationNOIP2004 蟲食算參考資料徐士良數(shù)值分析與算法機(jī)械工業(yè)出版社何江舟用高斯消元法解線性方程組下面講解幾道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開關(guān)問(wèn)題 HYPERLINK /JiidgeOnline/problem?id=1830 /JiidgeOnline/problem?id=1830POJ 3185 The Water Bowls HYPERLINK /JudgeOnline/problem?id=3185 /JudgeOnline/problem?id=3185開關(guān)窗戶，開關(guān)燈問(wèn)題，很典型的求解線性方程組的

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

7、e/problem?id=1166經(jīng)典的BFS問(wèn)題，有各種解法，也可以用逆矩陣進(jìn)行矩陣相乘。但是這道題用高斯消元法解決好像有些問(wèn)題（困擾了我N天持續(xù)困擾中），由于周期4不是素 數(shù)，故在求解過(guò)程中不能進(jìn)行取余（因?yàn)槿∮嗫赡軐?dǎo)致解集變大），但最后求解集時(shí)，還是需要進(jìn) 行取余操作，那么就不能保證最后求出的解是正確的在discuss里提問(wèn)了好幾天也沒(méi)人回答. 希望哪位路過(guò)的大牛指點(diǎn)下POJ 2065 SETI HYPERLINK /JudgeOnline/problem?id=2065 /JudgeOnline/problem?id=2065同樣是求解同余方程組問(wèn)題，由于題目中的p是素?cái)?shù)，可以直接在求

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

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

10、=1704福大月賽的一道題目，還是經(jīng)典的開關(guān)問(wèn)題，但是方程數(shù)和變?cè)獢?shù)不同(考驗(yàn)?zāi)０宓臅r(shí)候到了)，最后要求增廣陣的階，要用到高精度這里提供下自己寫的還算滿意的求解整數(shù)線性方程組的模板(浮點(diǎn)數(shù)類似，就不提供了)/*用于求整數(shù)解得方程組.*/#include #include #include using namespace std;const int maxn = 105;int equ, var; /有equ個(gè)方程，var個(gè)變?cè)Ｔ鰪V陣行數(shù)為equ,分別為0到equ - 1，列數(shù)為var + 1， 分別為0到 amaxnmaxn;int xmaxn; / 解集.bool free_xmaxn;

11、/判斷是否是不確定的變?cè)?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表示有浮點(diǎn)數(shù)解，但無(wú)整數(shù)解，-1表示無(wú)解，0表示唯一解，大于0表示無(wú)窮解，并返回自由變?cè)膫€(gè)數(shù))int Gauss(void)(int i, j, k;int max_r; /當(dāng)前這列絕對(duì)值最大的行.int col; /當(dāng)前處理的列.int ta, tb;int LCM;int temp;int free_x_num;int free_index;/轉(zhuǎn)換為階梯陣.col = 0; /當(dāng)前處理的列.for (k = 0; k equ & col var; k+, col+)( /枚舉當(dāng)前處理的行./找到該col列元素絕對(duì)值最大的那行與第k行交換.(為了在除法時(shí)減小誤差) 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)( /說(shuō)明該col列第k行以下全是0了，則處理當(dāng)前行的下一列.k-; continue;for (i = k + 1; i equ; i+)( /枚舉要?jiǎng)h去的行.if (aicol != 0)LCM = lcm(abs(aicol), abs(akcol);ta = LCM / abs(aicol), tb = LCM / abs(

14、akcol);if (aicol * akcol 0) tb = -tb; / 異號(hào)的情況是兩個(gè)數(shù)相加.for (j = col; j var + 1; j+)(aij = aij * ta - akj * tb;Debug();/ 1.無(wú)解的情況：化簡(jiǎn)的增廣陣中存在(0,0, ., a)這樣的行(a != 0).for (i = k; i equ; i+)( /對(duì)于無(wú)窮解來(lái)說(shuō)，如果要判斷哪些是自由變?cè)?，那么初等行變換中的交換就會(huì)影響，則 要記錄交換.if (aicol != 0) return -1;/ 2.無(wú)窮解的情況：在var * (var + 1)的增廣陣中出現(xiàn)(0,0, ., 0)這

15、樣的行，即說(shuō)明沒(méi)有形成 嚴(yán)格的上三角陣./且出現(xiàn)的行數(shù)即為自由變?cè)膫€(gè)數(shù).if (k = 0; i-)(/第i行一定不會(huì)是(0, 0, ., 0)的情況，因?yàn)檫@樣的行是在第k行到第equ行./同樣，第i行一定不會(huì)是(0, 0, ., a), a != 0的情況，這樣的無(wú)解的.free_x_num = 0; /用于判斷該行中的不確定的變?cè)膫€(gè)數(shù)，如果超過(guò)1個(gè)，則無(wú)法 求解，它們?nèi)匀粸椴淮_定的變?cè)?for (j = 0; j 1) continue; /無(wú)法求解出確定的變?cè)?/說(shuō)明就只有一個(gè)不確定的變?cè)猣ree_index，那么可以求解出該變?cè)?，且該變?cè)?確定的.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; /說(shuō)明有浮點(diǎn)數(shù)解，但無(wú)整數(shù)解. 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); / 一開