消-分析題解模板

1、消(Gauimination) 分析 & 題解 & 模板czyuan日 22:292009 年 04 月 26 日消，是線性代數(shù)中的一個(gè)算法，可用來(lái)求解線性方程組，并可以求出矩陣的秩，以及求出可逆方陣的逆矩陣。消的原理是：若用初等行變換將增廣矩陣 化為 ，則 AX = B 與 CX = D 是同解方程組。所以解。可以用初等行變換把增廣矩陣轉(zhuǎn)換為行階梯陣，然后回代求出方程的以上是線性代數(shù)課的回顧，下面來(lái)說(shuō)說(shuō)消在編程中的應(yīng)用。首先，先介紹程序中消的步驟：(設(shè)方程組中方程的個(gè)數(shù)為 equ，變?cè)膫€(gè)數(shù)為 var，注意：一般情況下是 n個(gè)方程，n 個(gè)變?cè)?，但是有些題目就故意讓方程數(shù)與變?cè)獢?shù)不同)1. 把

2、方程組轉(zhuǎn)換成增廣矩陣。2. 利用初等行變換來(lái)把增廣矩陣轉(zhuǎn)換成行階梯陣。枚舉 k 從 0 到 equ 1，當(dāng)前處理的列為 col(初始為 0) ，每次找第 k 行以下(包括第 k 行)，col 列中元素絕對(duì)值最大的列與第 k 行交換。如果 col 列中的元素全為 0，那么則處理 col + 1 列，k 不變。3. 轉(zhuǎn)換為行階梯陣，判斷解的情況。 無(wú)解當(dāng)方程中出現(xiàn)(0, 0, , 0, a)的形式，且 a != 0 時(shí)，說(shuō)明是無(wú)解的。 唯一解條件是 k = equ，即行階梯陣形成了嚴(yán)格的上三角陣。利用回代逐一求出解集。 無(wú)窮解。條件是 k equ，即不能形成嚴(yán)格的上三角形，但有些題目要求判斷哪些變

3、元是不缺定的。這里單獨(dú)介紹下這種解法：變?cè)膫€(gè)數(shù)即為 equ k，首先，變?cè)?var - k 個(gè)，即不確定的變?cè)辽儆?var - k 個(gè)。先把所有的變?cè)暈椴淮_定的。在每個(gè)方程中判斷不確定變?cè)膫€(gè)數(shù)，如果大于 1 個(gè)，則該方程無(wú)法求解。如果只有 1 個(gè)變?cè)敲丛撟冊(cè)纯汕蟪?，即為確定變?cè)?。以上介紹的是求解整數(shù)線性方程組的求法，復(fù)雜度是 O(n3)。浮點(diǎn)數(shù)線性方程組的求法類似，但是要在判斷是否為 0 時(shí)，加入 EPS，以消除精度問題。下面講解幾道 OJ 上的消求解線性方程組的題目：POJ 1222httpEXTENDED LIGHTS OUT/JudgeOnline/problem?id=

4、1222POJ 1681httpPaersProblem/JudgeOnline/problem?id=1681POJ 1753httpFlipGame/JudgeOnline/problem?id=1753POJ 1830http開關(guān)問題/JudgeOnline/problem?id=1830POJ 3185The WaterBowlshttp/JudgeOnline/problem?id=3185開關(guān)窗戶，開關(guān)燈問題，很典型的求解線性方程組。方程數(shù)和變量數(shù)均為行數(shù)*列數(shù)，直接套模板求解即可。但是，當(dāng)出現(xiàn)無(wú)窮解時(shí)，需要枚舉解的情況，因?yàn)闊o(wú)法判斷哪種解是題目要求最優(yōu)的。POJ 2947 Wid

5、get Factoryhttp/JudgeOnline/problem?id=2947求解同余方程組問題。與一般求解線性方程組入取余即可。類似，只要在求解過程中加注意：當(dāng)方程組唯一解時(shí)，求解過程中要保證解在3, 9之間。POJ 1166 The Clocks http/JudgeOnline/problem?id=1166經(jīng)典的 BFS 問題，有各種解法，也可以用逆矩陣進(jìn)行矩陣相乘。但是這道題用消解決好像有些問題(困擾了我 N 天.持續(xù)困擾中.)，由于周期 4 不是素?cái)?shù)，故在求解過程中不能進(jìn)行取余(因?yàn)槿∮嗫赡軐?dǎo)致解集變大)，但最后求解集時(shí)，還是需要進(jìn)行取余操作，那么就不能保證最后求出的解是正

6、確的.在 discuss 里提問了好幾天也沒人回答.希望哪位路過的大牛指點(diǎn)下POJ 2065 SETIhttp/JudgeOnline/problem?id=2065同樣是求解同余方程組問題，由于題目中的 p 是素?cái)?shù)，可以直接在求解時(shí)取余，套用模板求解即可。(雖然 AC 的人很少，但它還是比較水的一道題，)POJ 1487 Single-Player Gameshttp/JudgeOnline/problem?id=1487很麻煩的一道題目.題目中的敘述貌似用到了編譯原理中的詞法定義(看了就給人不解方程組的感覺.)還是很好看出來(lái)了(前提是通讀題目不下 5 遍.)，但如果把樹的字符串表達(dá)式轉(zhuǎn)換成

7、方程組是個(gè)難點(diǎn)，我是用棧 + 遞歸的做法分解的。首先用棧的求出該結(jié)點(diǎn)的孩子數(shù)，然后遞歸分別求解各個(gè)孩子。這題解方程組也與眾不同.首先是求解浮點(diǎn)數(shù)方程組，要注意精度問題，然后又詢問不確定的變?cè)?，按前面說(shuō)的方法求解。一頓折騰后，這題居然寫了 6000+B.而且囧的是巨人 C+ WA，G+ AC，可能還是精度吧.看這題目，看這代碼，就沒有改的.hdu OJ 2449http/showproblem.?=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 1704http/problem.?

8、=1704福大月賽的一道題目，還是經(jīng)典的開關(guān)問題，但是方程數(shù)和變?cè)獢?shù)不同(考驗(yàn)?zāi)０宓臅r(shí)候到了)，最后要求增廣陣的階，要用到度Sgu 275 To xor or not to xor題解: h/czyuan%5Facm/blog/item/be3403d32549633d970a16ee.html這里提供下自己寫的還算滿意的求解整數(shù)線性方程組的模板(浮點(diǎn)數(shù)類似，就不提供了)/* 用于求整數(shù)解得方程組. */#include #include #includeusing namespatd;constmaxn =105;equ, var; /有 equ 個(gè)方程，var 個(gè)變?cè)?。增廣陣行數(shù)為 equ

9、,分別為 0到 equ - 1，列數(shù)為 var + 1，分別為 0 到 var. amaxnmaxn;xmaxn; / 解集.bool free_xmaxn; / 判斷是否是不確定的變?cè)? free_num;void Debug(void)i, j;for (i = 0; i equ; i+)for (j = 0; j cout var + 1; j+)aij;cout endl;cout endl;inline(a,b)t; while (b !=0)t b a=b; a % t;b;return a;inlinelcm(a,b)return a * b /(a,b);/消解方程組(Gaus

10、s-Jordan elimination).(-2 表示有浮點(diǎn)數(shù)解，但無(wú)整數(shù)解，-1 表示無(wú)解，0 表示唯一解，大于 0 表示無(wú)窮解，并返回個(gè)數(shù))Gauss(void)i, j, k;max_r; / 當(dāng)前這列絕對(duì)值最大的行. col; / 當(dāng)前處理的列.ta, tb; LCM;temp; free_x_num; free_index;/ 轉(zhuǎn)換為階梯陣.col = 0; / 當(dāng)前處理的列.for (k = 0; k equ & col var; k+, col+) / 枚舉當(dāng)前處理的行.變?cè)? 找到該col列元素絕對(duì)值最大的那行與第k行交換.(為了在除法時(shí)減小誤差)max_r = k;for

11、 (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(ak

12、col);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)這樣的

13、行，即說(shuō)明沒有形成嚴(yán)格的上三角陣./ 且出現(xiàn)的行數(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ù)，如果超過 1 個(gè)，則無(wú)法求解，它們?nèi)匀粸椴淮_定的變?cè)?for (j = 0; j 1) continue; / 無(wú)法求解出確定的變?cè)?/ 說(shuō)明就只有一個(gè)不確定的變?cè)猣ree_index，那么可以求解出該變?cè)?，且該變?cè)谴_定的.temp = aivar;for (j

14、 = 0; j = 0; i-)aivar;= 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;0;returnmain(void)freopen(Input.txt, r, stdin);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); / for (i = 0; i