#
高斯消元法，是線性代數中的一個算法，可用來求解線性方程組，并可以求出矩陣的秩，以及求出可逆方陣的逆矩陣。
高斯消元法的原理是：
若用初等行變換將增廣矩陣 化為 ，則AX = B與CX = D是同解方程組。
所以我們可以用初等行變換把增廣矩陣轉換為行階梯陣，然后回代求出方程的解。
以上是線性代數課的回顧，下面來說說高斯消元法在編程中的應用。
首先，先介紹程序中高斯消元法的步驟：
(我們設方程組中方程的個數為equ，變元的個數為var，注意：一般情況下是n個方程，n個變元，但是有些題目就故意讓方程數與變元數不同)
1. 把方程組轉換成增廣矩陣。
2. 利用初等行變換來把增廣矩陣轉換成行階梯陣。
枚舉k從0到equ – 1，當前處理的列為col(初始為0) ，每次找第k行以下(包括第k行)，col列中元素絕對值最大的列與第k行交換。如果col列中的元素全為0，那么則處理col + 1列，k不變。
3. 轉換為行階梯陣，判斷解的情況。
① 無解
當方程中出現(0, 0, …, 0, a)的形式，且a != 0時，說明是無解的。
② 唯一解
條件是k = equ，即行階梯陣形成了嚴格的上三角陣。利用回代逐一求出解集。
③ 無窮解。
條件是k < equ，即不能形成嚴格的上三角形，自由變元的個數即為equ – k，但有些題目要求判斷哪些變元是不缺定的。
這里單獨介紹下這種解法：
首先，自由變元有var - k個，即不確定的變元至少有var - k個。我們先把所有的變元視為不確定的。在每個方程中判斷不確定變元的個數，如果大于1個，則該方程無法求解。如果只有1個變元，那么該變元即可求出，即為確定變元。
以上介紹的是求解整數線性方程組的求法，復雜度是O(n3)。浮點數線性方程組的求法類似，但是要在判斷是否為0時，加入EPS，以消除精度問題。
下面講解幾道OJ上的高斯消元法求解線性方程組的題目：
POJ 1222 EXTENDED LIGHTS OUT
http://acm.pku.edu.cn/JudgeOnline/problem?id=1222
POJ 1681 Painter's Problem
http://acm.pku.edu.cn/JudgeOnline/problem?id=1681
POJ 1753 Flip Game
http://acm.pku.edu.cn/JudgeOnline/problem?id=1753
POJ 1830 開關問題
http://acm.pku.edu.cn/JudgeOnline/problem?id=1830
POJ 3185 The Water Bowls
http://acm.pku.edu.cn/JudgeOnline/problem?id=3185
開關窗戶，開關燈問題，很典型的求解線性方程組的問題。方程數和變量數均為行數*列數，直接套模板求解即可。但是，當出現無窮解時，需要枚舉解的情況，因為無法判斷哪種解是題目要求最優的。
POJ 2947 Widget Factory
http://acm.pku.edu.cn/JudgeOnline/problem?id=2947
求解同余方程組問題。與一般求解線性方程組的問題類似，只要在求解過程中加入取余即可。
注意：當方程組唯一解時，求解過程中要保證解在[3, 9]之間。
POJ 1166 The Clocks
http://acm.pku.edu.cn/JudgeOnline/problem?id=1166
經典的BFS問題，有各種解法，也可以用逆矩陣進行矩陣相乘。
但是這道題用高斯消元法解決好像有些問題(困擾了我N天...持續困擾中...)，由于周期4不是素數，故在求解過程中不能進行取余(因為取余可能導致解集變大)，但最后求解集時，還是需要進行取余操作，那么就不能保證最后求出的解是正確的...在discuss里提問了好幾天也沒人回答...希望哪位路過的大牛指點下～～
POJ 2065 SETI
http://acm.pku.edu.cn/JudgeOnline/problem?id=2065
同樣是求解同余方程組問題，由于題目中的p是素數，可以直接在求解時取余，套用模板求解即可。(雖然AC的人很少，但它還是比較水的一道題，)
POJ 1487 Single-Player Games
http://acm.pku.edu.cn/JudgeOnline/problem?id=1487
很麻煩的一道題目...題目中的敘述貌似用到了編譯原理中的詞法定義(看了就給人不想做的感覺...)
解方程組的思想還是很好看出來了(前提是通讀題目不下5遍...)，但如果把樹的字符串表達式轉換成方程組是個難點，我是用棧 + 遞歸的做法分解的。首先用棧的思想求出該結點的孩子數，然后遞歸分別求解各個孩子。
這題解方程組也與眾不同...首先是求解浮點數方程組，要注意精度問題，然后又詢問不確定的變元，按前面說的方法求解。
一頓折騰后，這題居然寫了6000+B...而且囧的是巨人C++ WA，G++ AC，可能還是精度的問題吧...看這題目，看這代碼，就沒有改的欲望...
hdu OJ 2449
http://acm.hdu.edu.cn/showproblem.php?pid=2449
哈爾濱現場賽的一道純高斯題，當時鶴牛敲了1個多小時...主要就是寫一個分數類，套個高精模板(偷懶點就Java...)搞定～～
注意下0和負數時的輸出即可。
fze OJ 1704
http://acm.fzu.edu.cn/problem.php?pid=1704
福大月賽的一道題目，還是經典的開關問題，但是方程數和變元數不同(考驗模板的時候到了～～)，最后要求增廣陣的階，要用到高精度～～
Sgu 275 To xor or not to xor
http://acm.sgu.ru/problem.php?contest=0&problem=275
題解:
http://hi.baidu.com/czyuan%5Facm/blog/item/be3403d32549633d970a16ee.html
這里提供下自己寫的還算滿意的求解整數線性方程組的模板(浮點數類似，就不提供了)～～
/* 用于求整數解得方程組. */
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
const int maxn = 105;
int equ, var; // 有equ個方程，var個變元。增廣陣行數為equ, 分別為0到equ - 1，列數為var + 1，分別為0到var.
int a[maxn][maxn];
int x[maxn]; // 解集.
bool free_x[maxn]; // 判斷是否是不確定的變元.
int free_num;
void Debug(void)
{
int i, j;
for (i = 0; i < equ; i++)
{
for (j = 0; j < var + 1; j++)
{
cout << a[i][j] << " ";
}
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 elimination).(-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 = k;
for (i = k + 1; i < equ; i++)
{
if (abs(a[i][col]) > abs(a[max_r][col])) max_r = i;
}
if (max_r != k)
{ // 與第k行交換.
for (j = k; j < var + 1; j++) swap(a[k][j], a[max_r][j]);
}
if (a[k][col] == 0)
{ // 說明該col列第k行以下全是0了，則處理當前行的下一列.
k--; continue;
}
for (i = k + 1; i < equ; i++)
{ // 枚舉要刪去的行.
if (a[i][col] != 0)
{
LCM = lcm(abs(a[i][col]), abs(a[k][col]));
ta = LCM / abs(a[i][col]), tb = LCM / abs(a[k][col]);
if (a[i][col] * a[k][col] < 0) tb = -tb; // 異號的情況是兩個數相加.
for (j = col; j < var + 1; j++)
{
a[i][j] = a[i][j] * ta - a[k][j] * tb;
}
}
}
}
Debug();
// 1. 無解的情況: 化簡的增廣陣中存在(0, 0, ..., a)這樣的行(a != 0).
for (i = k; i < equ; i++)
{ // 對于無窮解來說，如果要判斷哪些是自由變元，那么初等行變換中的交換就會影響，則要記錄交換.
if (a[i][col] != 0) return -1;
}
// 2. 無窮解的情況: 在var * (var + 1)的增廣陣中出現(0, 0, ..., 0)這樣的行，即說明沒有形成嚴格的上三角陣.
// 且出現的行數即為自由變元的個數.
if (k < var)
{
// 首先，自由變元有var - k個，即不確定的變元至少有var - k個.
for (i = k - 1; i >= 0; i--)
{
// 第i行一定不會是(0, 0, ..., 0)的情況，因為這樣的行是在第k行到第equ行.
// 同樣，第i行一定不會是(0, 0, ..., a), a != 0的情況，這樣的無解的.
free_x_num = 0; // 用于判斷該行中的不確定的變元的個數，如果超過1個，則無法求解，它們仍然為不確定的變元.
for (j = 0; j < var; j++)
{
if (a[i][j] != 0 && free_x[j]) free_x_num++, free_index = j;
}
if (free_x_num > 1) continue; // 無法求解出確定的變元.
// 說明就只有一個不確定的變元free_index，那么可以求解出該變元，且該變元是確定的.
temp = a[i][var];
for (j = 0; j < var; j++)
{
if (a[i][j] != 0 && j != free_index) temp -= a[i][j] * x[j];
}
x[free_index] = temp / a[i][free_index]; // 求出該變元.
free_x[free_index] = 0; // 該變元是確定的.
}
return var - k; // 自由變元有var - k個.
}
// 3. 唯一解的情況: 在var * (var + 1)的增廣陣中形成嚴格的上三角陣.
// 計算出Xn-1, Xn-2 ... X0.
for (i = var - 1; i >= 0; i--)
{
temp = a[i][var];
for (j = i + 1; j < var; j++)
{
if (a[i][j] != 0) temp -= a[i][j] * x[j];
}
if (temp % a[i][i] != 0) return -2; // 說明有浮點數解，但無整數解.
x[i] = temp / a[i][i];
}
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)); // 一開始全是不確定的變元.
for (i = 0; i < equ; i++)
{
for (j = 0; j < var + 1; j++)
{
scanf("%d", &a[i][j]);
}
}
// Debug();
free_num = Gauss();
if (free_num == -1) printf("無解!\n");
else if (free_num == -2) printf("有浮點數解，無整數解!\n");
else if (free_num > 0)
{
printf("無窮多解! 自由變元個數為%d\n", free_num);
for (i = 0; i < var; i++)
{
if (free_x[i]) printf("x%d 是不確定的\n", i + 1);
else printf("x%d: %d\n", i + 1, x[i]);
}
}
else
{
for (i = 0; i < var; i++)
{
printf("x%d: %d\n", i + 1, x[i]);
}
}
printf("\n");
}
return 0;
}
轉自：http://hi.baidu.com/czyuan_acm/blog/item/ebf41f8fdc0e1ee6f01f36e9.html
Sometimes the most important history, is the history we are making today~
聽說電視連續劇《蝸居》被禁了，據說是因為臺詞有點黃。果真如此嗎？帶著好奇，我從網上在線看了《蝸居》。一集一集地、認認真真地看了一遍。邊看邊同情、邊看邊感嘆，邊看邊思考。不把心里的話說出來，我悶得慌。
我看《蝸居》的被禁，跟臺詞黃不黃沒關系，大多是個禁它的借口。再熱播下去，怕要出大亂子。一個月來，這部電視劇引起了很多人的關注和網上的熱烈討論。它將鏡頭對準了大城市中不那么光鮮的一面：房價的上漲以及由此給年輕人的理想造成的巨大沖擊。我們自己的生活就像劇中描寫的一樣，一切都暴露在了陽光下。劇中把房子帶來的社會問題推上極致，這種殘酷的生活直抵每一個因房價而困擾生活的人。
一項36萬多人參加的投票調查中，大多數人認為“幸福與房子關聯密切。” “還房貸、吃盒飯”，已經成為房價飆升年代對白領生存狀況的一種直白描摹。主人公一波三折的買房奮斗史，道出了都市無房族的困惑：房價是“一匹脫韁的野馬”，攢錢的速度永遠趕不上房價上漲的速度。
有人甘心做房奴嗎，不買房子不行嗎？答案是，不行！誰會租房租一輩子？你要說，沒錢你就去郊區甚至農村買房子呀。對，可以在郊區或農村買到便宜房子，可是你的工作單位在市區，你怎么辦？是啊，人民有廣泛的自由，有選擇的權利。可是，你要上學，就得接受高學費，你要看病就得接受高收費，你要住房就要選擇高房價，除非你不讓孩子上學、不去看病，不住房子。你有不選擇的自由嗎？沒有。買房是社會逼的，是形勢逼的，是必需的，你可以選擇這，選擇那，你能選擇不住房子嗎！
那，是誰逼著群眾做了房奴？是壟斷階層，是官商勾結，是政治腐敗！國家是人民的，資源是國家的,理應由人民共享。可是利益集團利用人民的資源，憑借其壟斷地位要挾人民。看看現實,看看中石油、中石化, 領著巨額財政補貼,買樓是10億10億的買，不漲價就斷你車子的油、不漲價就斷你家的氣,人為制造緊張。中國移動,傳播黃色淫穢網絡的先鋒,哪里還有一丁點的社會責任；有線電視,大家都看見了,獨此一家,不用也得用,不允許你安裝衛星電視,查處你！諸如此類,實在太多。還有無恥的專家為他們搖旗吶喊：不能因為窮人喝不起水就不漲水價,中國的電價嚴重偏低。漲價是為了節約資源，更好地服務于人民,能力外的資本為零,哈哈,令人笑掉大牙……見過無恥的,沒見過這么無恥的。
看看劇情吧，權力支配一切，資本動搖人性，利益逼良為娼。權貴階層可以隨便劫人祖居、淫人妻女、左右一切。同樣是過年，富人在富麗堂皇充滿溫馨的大房子里，窮人沒水沒電點著蠟燭苦熬；群眾頂著加班的壓力努力地工作，不過取得些微薄的收入，而權貴的二奶買件衣服隨便一出手就成千上萬！這是我們要的和諧社會嗎？
看到第19集，我，一個男人，哭了。小貝的幾聲大吼，你以為只是因為奪妻之恨嗎？非也，他喊出了人壓抑已久的東西！
感謝《蝸居》的七個理由？
上海電視臺制作的35集電視連續劇《蝸居》在國家廣電總局的否認禁播中還是被“禁播”了。只有上海東方衛視似乎還在播放，不過，大家多數人已經看過這部電視劇了，原因是網絡拉近了精神產品制造者與消費者的距離。各地方電視臺電視臺形式上的禁播，只是一些人的作秀。我覺得應該感謝《蝸居》。
感謝《蝸居》的第一個理由，它引起爭議。對《蝸居》的爭議恐怕還要持續下去，就讓發展見證或者證明它的必要與否吧！一部有爭議的電視劇起碼說明它是有關注度的，在被受眾的關注過程中，既實現了電視臺的播放價值，又實現了媒體的報道價值，還能教育國人，凈化心靈。在對《蝸居》的爭議中，國人慢慢接受它的存在。
感謝《蝸居》的第二理由，它沒有亂倫。如今，國人已經出離了羞恥的地步，親情、友情（同事情、戰友情）、愛情等這些永恒的主題已經有了重新闡釋的必要和必須了！而《蝸居》緊緊把握社會倫理道德的底線，沒有讓姐夫與小姨子發生任何關系，也沒有通過更進一步的亂倫實現讓受眾關注的目的，這讓一些人感動。
感謝《蝸居》的第三個理由，它寫了拆遷。隨著城市化進程的加速發展，隨著國家拉動內需政策的深入執行，城市要擴展生存空間，老舊小區以及棚戶區、平房、貧民區等都要被拆遷建新的。《蝸居》把存在于拆遷中的核心問題全部寫出來，讓觀眾自己感受，讓觀眾自己解決。不管是利益拆遷還是流氓阻遷，都在觀眾的心理。
感謝《蝸居》的第四個理由，它痛恨腐敗。腐敗是發展的毒瘤，國人恨之入骨，尤其是哪些家中或者親戚中沒有當官的人，更是恨不得“吃腐敗分子的肉，喝腐敗分子的血”。當然，家中或者親戚中如果有當官的腐敗了，那就另當別論了！他們會以此自詡，同時，也會撈取一些提高生活水平的金錢、名譽、地位，徹底揭示出國人的雙重人格。
感謝《蝸居》的第五個理由，它落筆于被社會遺忘的角落。過去組成社會機構的農民、工人、知識分子、商人的階層，現在已經發生了極大的變化：農民（農民工、農電工）、公務員、工人（礦工）、企業員工、知識分子（教師）、領導干部……這些群體都有關注，也有代言人，也有說話的地方，而有一個群體是沒有代言人的，是被遺忘的快要發霉的群體，他們生活在城市夾縫中喘不過起來，他們以打工名義無盡地奮斗著，他們是知識分子，他們有文化，有志向，有力氣，有理想，就是沒有跳起來高飛的平臺。他們每天在一個企業里面被老板殘忍的剝奪著，得到的與自己付出的根本不等價，他們的收入被以奉獻的名義剝奪了，加班合理化、扣錢流氓化、養老保險強制化……就是打個車還要為城市管理者的無能埋單。
感謝《蝸居》的第六個理由，它關注士階層。記得在中學的時候學習歷史，講到三國兩晉南北朝時期，東晉出現了士階層，他們有錢有勢，生活無聊，尋找刺激，沒有追求，攀比成風，人乳宴就是那個時候發明并且被推廣起來的。現在這個新士階層是一個高度變態的階層，他們比誰的二奶奶多，臉蛋漂亮，歲數小……并且他們不會受到內心的譴責的，這是可怕的警示。
感謝《蝸居》的第七個理由，它打造忍者神龜。好像動畫片里有個東西叫忍者神龜，《蝸居》就是告訴受眾，在這個社會生活、生存必須學會忍讓，就像烏龜那樣永遠地蜷縮著自己的腦袋，不要放出了。這樣下去，將讓這個社會失去了血性。
來看看貓撲網收集到的MOPPER的回復吧
這個電視劇惡攻精蠅的房地產政策！
沒看過，但是被禁播一定有它的理由。畢竟話語權在精英手中。
似乎東方衛視還在播。
這是我們要的和諧社會嗎？
哀民生之多艱！恨權貴之貪婪！怒官員之腐敗！愧我party之怠慢！
資本主義社會，有多少錢，就有多少自由。你以為法律不禁止，你就自由了？
看到第19集，我，一個男人，哭了。小貝的幾聲大吼，你以為只是因為奪妻之恨嗎？非也，他喊出了人壓抑已久的東西！
以人為本。以人為本。以人為本。
觸目驚心_____
權貴的二奶買件衣服隨便一出手就成千上萬！這是我們要的和諧社會嗎？
富人在富麗堂皇充滿溫馨的大房子里，窮人沒水沒電點著蠟燭苦熬；群眾頂著加班的壓力努力地工作，不過取得些微薄的收入
看看劇情吧，權力支配一切，資本動搖人性，利益逼良為娼。權貴階層可以隨便劫人祖居、淫人妻女、左右一切
無恥的專家為他們搖旗吶喊：不能因為窮人喝不起水就不漲水價,中國的電價嚴重偏低。漲價是為了節約資源
不漲價就斷你車子的油、不漲價就斷你家的氣,人為制造緊張。中國移動,傳播黃色淫穢網絡的先鋒,哪里還有一丁點的社會責任
利益集團利用人民的資源，憑借其壟斷地位要挾人民。看看現實,看看中石油、中石化, 領著巨額財政補貼,買樓是10億10億的買
是誰逼著群眾做了房奴？是壟斷階層，是官商勾結，是政治腐敗！國家是人民的，資源是國家的,理應由人民共享。
見過無恥的,沒見過這么無恥的
社會會崩潰嗎?房地產很可能就是de-tona-tor.
極有可能，動遷的，上訪的，買不起房的，買房被套的，為房當二奶的........每個故事背后都是de-tona-tor，都和房地產有關.........
這樣呵，我也去看看吧。
別當真，其實，其色情度，遠不如……手機黃段子。關鍵的“錯誤”是……歌頌二奶，大奶很生氣！
盛世危言。
《蝸居》很濫，不過目前中國……就是這么濫。濫點，一是作者濫情，二是房市濫市，三是官員濫政，四是女性濫性。
——轉自天涯
摘要: 這題最簡單的方法居然是暴力。。。時間復雜度一算大概是N^2，AC了。。。
#include<iostream>#include<cstdio>#include<cstring>using namespace std;//暴力求因子，打表 int n;int a[1000001],b[1000001]={0},c...
閱讀全文
摘要: 這個題我是用線段樹來做的，結果居然是超時。。。后來foreverlin同學告訴我他用樹狀數組過的，但我記得樹狀數組能解決的問題，線段樹一定能解決，而且線段樹的復雜度是logL級別，為什么我會超時呢？還請各位大牛指點。。。我的代碼如下：
#include<iostream>#include<cstdio>#include<cstring>#include<...
閱讀全文
久客逢馀閏，他鄉別故人。自然堪下淚，誰忍望征塵。
江上風煙積，山幽云霧多。送君南浦外，還望將如何。
桂軺雖不駐，蘭筵幸未開。林塘風月賞，還待故人來。
霜華凈天末，霧色籠江際。客子常畏人，何為久留滯。
div2的題目確實比較水，進了div1就不同了，除了第一題，后面兩道基本沒有頭緒。。。。。。不過，樓哥依然還是那么猛。。。。
光榮的回到div2...汗...
Class 1
» GeForce GTX 280M SLI
» Mobility Radeon HD 4870 X2
» GeForce GTX 260M SLI
» GeForce 9800M GTX SLI
» GeForce GTX 280M
» GeForce 9800M GT SLI
» GeForce 9800M GTS SLI
» Mobility Radeon HD 3870 X2
» GeForce 8800M GTX SLI
» Mobility Radeon HD 3850 X2
» Quadro FX 3700M
» Mobility Radeon HD 4870
» Mobility Radeon HD 4860
» FirePro M7740
» Mobility Radeon HD 4850
» GeForce GTX 260M
» GeForce 9800M GTX
» GeForce 9800M GT
» GeForce 8800M GTX
» Quadro FX 3600M
» GeForce GTS 260M
» GeForce GTS 250M
» GeForce GTS 160M
» GeForce 9800M GTS
» GeForce 9800M GS
» Mobility Radeon HD 4830
» GeForce GTS 150M
Class 2
» GeForce 8800M GTS
» Mobility Radeon HD 4670
» GeForce 9700M GTS
» Quadro FX 2700M
» Mobility Radeon HD 3870
» Mobility Radeon HD 4650
» GeForce Go 7950 GTX SLI
» GeForce Go 7900 GTX SLI
» Mobility Radeon HD 3850
» GeForce GT 240M
» GeForce Go 7950 GTX
» Quadro FX 3500M
» GeForce 8700M GT SLI
» GeForce Go 7800 GTX SLI
» GeForce Go 7900 GS SLI
» GeForce Go 7900 GTX
» Quadro FX 2500M
» GeForce 8600M GT SLI
» GeForce GT 230M
» GeForce 9700M GT
» GeForce GT 130M
» GeForce 9650M GT
» GeForce Go 7900 GS
» GeForce 9650M GS
» Quadro FX 1700M
» Quadro FX 1600M
» GeForce 8700M GT
» Quadro NVS 320M
» Quadro FX 1500M
» GeForce 9600M GT
» GeForce GT 220M
» Quadro FX 770M
» GeForce GT 120M
» GeForce Go 7800 GTX
» Mobility Radeon HD 3670
» Mobility FireGL V5725
» Mobility Radeon HD 2600 XT
» Mobility Radeon X1900
» Mobility Radeon X1800XT
» Mobility Radeon X1800
» GeForce Go 6800 Ultra
» GeForce Go 7800
» GeForce 9600M GS
» GeForce 9500M GS
» Mobility Radeon HD 4570
» Mobility Radeon HD 2700
» Mobility Radeon HD 3650
» Mobility FireGL V5700
» Quadro FX 570M
» GeForce 8600M GT
» Mobility Radeon HD 2600
» GeForce Go 7600 GT
Class 3
» GeForce G 210M
» GeForce 9500M G
» GeForce 8600M GS
» GeForce Go 7700
» GeForce Go 6800
» Quadro FX Go 1400
» Mobility Radeon X800XT
» Mobility Radeon HD 4530
» Mobility Radeon X1700
» Mobility FireGL V5250
» Mobility Radeon X2500
» GeForce Go 7600
» Quadro NVS 300M
» Mobility Radeon X800
» Mobility Radeon X1600
» Mobility FireGL V5200
» Mobility Radeon 9800
» GeForce Go 6600
» Mobility Radeon X1450
» Mobility Radeon X700
» Mobility FireGL V5000
» GeForce G 110M
» Mobility Radeon HD 4330
» GeForce 8400M GT
» Quadro NVS 140M
» GeForce G 105M
» GeForce 9500M GE
» GeForce G 102M
» GeForce 9400M (G)
» Mobility Radeon HD 3470 Hybrid X2
» GeForce 9400M GeForceBoost
» Mobility Radeon HD 3470
» GeForce 9300M G
» GeForce 9300M GS
» Quadro FX 370M
» Quadro NVS 160M
» GeForce 9200M GS
» Mobility Radeon HD 3450
» Mobility Radeon HD 3430
» Mobility Radeon HD 3410
» Radeon HD 4200
» Quadro NVS 150M
» Mobility Radeon HD 2400 XT
» Quadro FX 360M
» Mobility Radeon X1350
» Mobility Radeon X1400
» GeForce 9100M G
» GeForce 8400M GS
» Quadro NVS 135M
» Mobility Radeon HD 2400
» Radeon HD 3200
» Radeon HD 3100
» Graphics Media Accelerator (GMA) 4700MHD
» GeForce 8400M G
» Graphics Media Accelerator (GMA) 4500MHD
» Graphics Media Accelerator (GMA) 4500M
» Quadro NVS 130M
» GeForce 8200M G
» GeForce Go 7400
» Quadro FX 350M
» Quadro NVS 120M
» GeForce Go 7300
» Quadro NVS 110M
» Mobility Radeon X600
» Mobility FireGL V3200
» Mobility FireGL V3100
» Mobility Radeon X2300
» Mobility Radeon HD 2300
» Mobility Radeon 9700
» Mobility FireGL T2e
Class 4
» Mobility Radeon X1300
» GeForce4 4200 Go
» Mobility Radeon 9600
» Mobility FireGL T2
» Mobility Radeon 9550
» GeForce Go 7200
» GeForce Go 6400
» Mobility Radeon X300
» GeForce Go 6250
» GeForce Go 6200
» GeForce FX Go 5700
» Quadro FX Go 1000
» GeForce FX Go 5600 / 5650
Class 5
» Radeon Xpress X1270
» Radeon Xpress X1250
» Radeon Xpress 1250
» Radeon Xpress X1200
» Graphics Media Accelerator (GMA) X3100
» Radeon Xpress 1150
» GeForce 7150M
» GeForce Go 6150
» GeForce Go 6100
» GeForce 7000M
» Mobility Radeon 9200
» GeForce FX Go 5200
» Mobility Radeon 9000
» GeForce 4 488 Go
» GeForce 4 460 Go
» GeForce 4 440 Go
» GeForce 4 420 Go
» Graphics Media Accelerator (GMA) 950
» Mobility Radeon 7500
» Mobility FireGL 7800
» Graphics Media Accelerator (GMA) 900
» Radeon Xpress 200M
» Radeon Xpress 1100
Class 6
» Mobility FireGL 9000
» Mirage 3+ 672MX
» Mirage 3 671MX
» Graphics Media Accelerator (GMA) 500
» GeForce 3 Go
» GeForce 2 Go (200 / 100)
» Mobility Radeon 9100 IGP
» Mobility Radeon 9000 IGP
» Mobility Radeon M7
» Mobility Radeon M6
» Mobility Radeon 7000 IGP
» Chrome9 HC
» Extreme Graphics 2
» Radeon IGP 340M
» S3G UniChrome Pro II
» S3G UniChrome Pro
» Mirage 2 M760
» Mirage M661FX
» S3 Graphics ProSavage8
» Castle Rock
» Mobility 128 M3
» SM502
摘要：白盒測試作為測試人員常用的一種測試方法，越來越受到測試工程師的重視。白盒測試并不是簡單的按照代碼設計用例，而是需要根據不同的測試需求，結合不同的測試對象，使用適合的方法進行測試。因為對于不同復雜度的代碼邏輯，可以衍生出許多種執行路徑，只有適當的測試方法，才能幫助我們從代碼的迷霧森林中找到正確的方向。本文介紹六種白盒子測試方法：語句覆蓋、判定覆蓋、條件覆蓋、判定條件覆蓋、條件組合覆蓋、路徑覆蓋。
白盒測試的概述
由于邏輯錯誤和不正確假設與一條程序路徑被運行的可能性成反比。由于我們經常相信某邏輯路徑不可能被執行, 而事實上,它可能在正常的情況下被執行。由于代碼中的筆誤是隨機且無法杜絕的，因此我們要進行白盒測試。
白盒測試又稱結構測試,透明盒測試、邏輯驅動測試或基于代碼的測試。白盒測試是一種測試用例設計方法，盒子指的是被測試的軟件，白盒指的是盒子是可視的,你清楚盒子內部的東西以及里面是如何運作的。
白盒的測試用例需要做到：
·保證一個模塊中的所有獨立路徑至少 被使用一次
·對所有邏輯值均需測試 true 和 false
·在上下邊界及可操作范圍內運行所有循環
·檢查內部數據結構以確保其有效性
白盒測試的目的：通過檢查軟件內部的邏輯結構，對軟件中的邏輯路徑進行覆蓋測試；在程序不同地方設立檢查點，檢查程序的狀態，以確定實際運行狀態與預期狀態是否一致。
白盒測試的特點：依據軟件設計說明書進行測試、對程序內部細節的嚴密檢驗、針對特定條件設計測試用例、對軟件的邏輯路徑進行覆蓋測試。
白盒測試的實施步驟：
1.測試計劃階段：根據需求說明書，制定測試進度。
2.測試設計階段：依據程序設計說明書，按照一定規范化的方法進行軟件結構劃分和設計測試用例。
3.測試執行階段：輸入測試用例，得到測試結果。
4.測試總結階段：對比測試的結果和代碼的預期結果，分析錯誤原因，找到并解決錯誤。
白盒測試的方法：總體上分為靜態方法和動態方法兩大類。
靜態分析是一種不通過執行程序而進行測試的技術。靜態分析的關鍵功能是檢查軟件的表示和描述是否一致,沒有沖突或者沒有歧義。
動態分析的主要特點是當軟件系統在模擬的或真實的環境中執行之前、之中和之后 , 對軟件系統行為的分析。動態分析包含了程序在受控的環境下使用特定的期望結果進行正式的運行。它顯示了一個系統在檢查狀態下是正確還是不正確。在動態分析技術中,最重要的技術是路徑和分支測試。下面要介紹的六種覆蓋測試方法屬于動態分析方法。
白盒測試的優缺點
1. 優點
·迫使測試人員去仔細思考軟件的實現
·可以檢測代碼中的每條分支和路徑
·揭示隱藏在代碼中的錯誤
·對代碼的測試比較徹底
·最優化
2. 缺點
·昂貴
·無法檢測代碼中遺漏的路徑和數據敏感性錯誤
·不驗證規格的正確性
六種覆蓋方法
首先為了下文的舉例描述方便，這里先給出一張程序流程圖。（本文以1995年軟件設計師考試的一道考試題目為例，圖中紅色字母代表程序執行路徑）。
1、語句覆蓋
1）主要特點：語句覆蓋是最起碼的結構覆蓋要求，語句覆蓋要求設計足夠多的測試用例，使得程序中每條語句至少被執行一次。
2）用例設計：（如果此時將A路徑上的語句1—〉T去掉，那么用例如下）
|
|
X
|
Y
|
路徑
|
|
1
|
50
|
50
|
OBDE
|
|
2
|
90
|
70
|
OBCE
|
3）優點：可以很直觀地從源代碼得到測試用例，無須細分每條判定表達式。
4）缺點：由于這種測試方法僅僅針對程序邏輯中顯式存在的語句，但對于隱藏的條件和可能到達的隱式邏輯分支，是無法測試的。在本例中去掉了語句1—〉T去掉，那么就少了一條測試路徑。在if結構中若源代碼沒有給出else后面的執行分支，那么語句覆蓋測試就不會考慮這種情況。但是我們不能排除這種以外的分支不會被執行，而往往這種錯誤會經常出現。再如，在Do-While結構中，語句覆蓋執行其中某一個條件分支。那么顯然，語句覆蓋對于多分支的邏輯運算是無法全面反映的，它只在乎運行一次，而不考慮其他情況。
2、判定覆蓋
1）主要特點：判定覆蓋又稱為分支覆蓋，它要求設計足夠多的測試用例，使得程序中每個判定至少有一次為真值，有一次為假值，即：程序中的每個分支至少執行一次。每個判斷的取真、取假至少執行一次。
2）用例設計：
|
|
X
|
Y
|
路徑
|
|
1
|
90
|
90
|
OAE
|
|
2
|
50
|
50
|
OBDE
|
|
3
|
90
|
70
|
OBCE
|
3）優點：判定覆蓋比語句覆蓋要多幾乎一倍的測試路徑，當然也就具有比語句覆蓋更強的測試能力。同樣判定覆蓋也具有和語句覆蓋一樣的簡單性，無須細分每個判定就可以得到測試用例。
4）缺點：往往大部分的判定語句是由多個邏輯條件組合而成（如，判定語句中包含AND、OR、CASE），若僅僅判斷其整個最終結果，而忽略每個條件的取值情況，必然會遺漏部分測試路徑。
3、條件覆蓋
1）主要特點：條件覆蓋要求設計足夠多的測試用例，使得判定中的每個條件獲得各種可能的結果，即每個條件至少有一次為真值，有一次為假值。
2）用例設計：
|
|
X
|
Y
|
路徑
|
|
1
|
90
|
70
|
OBC
|
|
2
|
40
|
|
OBD
|
3）優點：顯然條件覆蓋比判定覆蓋，增加了對符合判定情況的測試，增加了測試路徑。
4）缺點：要達到條件覆蓋，需要足夠多的測試用例，但條件覆蓋并不能保證判定覆蓋。條件覆蓋只能保證每個條件至少有一次為真，而不考慮所有的判定結果。
4、判定/條件覆蓋
1）主要特點：設計足夠多的測試用例，使得判定中每個條件的所有可能結果至少出現一次，每個判定本身所有可能結果也至少出現一次。
2）用例設計：
|
|
X
|
Y
|
路徑
|
|
1
|
90
|
90
|
OAE
|
|
2
|
50
|
50
|
OBDE
|
|
3
|
90
|
70
|
OBCE
|
|
4
|
70
|
90
|
OBCE
|
3）優點：判定/條件覆蓋滿足判定覆蓋準則和條件覆蓋準則，彌補了二者的不足。
4）缺點：判定/條件覆蓋準則的缺點是未考慮條件的組合情況。
5、組合覆蓋
1）主要特點：要求設計足夠多的測試用例，使得每個判定中條件結果的所有可能組合至少出現一次。
2）用例設計：
|
|
X
|
Y
|
路徑
|
|
1
|
90
|
90
|
OAE
|
|
2
|
90
|
70
|
OBCE
|
|
3
|
90
|
30
|
OBDE
|
|
4
|
70
|
90
|
OBCE
|
|
5
|
30
|
90
|
OBDE
|
|
6
|
70
|
70
|
OBDE
|
|
7
|
50
|
50
|
OBDE
|
3）優點：多重條件覆蓋準則滿足判定覆蓋、條件覆蓋和判定/條件覆蓋準則。更改的判定/條件覆蓋要求設計足夠多的測試用例，使得判定中每個條件的所有可能結果至少出現一次，每個判定本身的所有可能結果也至少出現一次。并且每個條件都顯示能單獨影響判定結果。
4）缺點：線性地增加了測試用例的數量。
6、路徑覆蓋
1）主要特點：設計足夠的測試用例，覆蓋程序中所有可能的路徑。
2）用例設計：
|
|
X
|
Y
|
路徑
|
|
1
|
90
|
90
|
OAE
|
|
2
|
50
|
50
|
OBDE
|
|
3
|
90
|
70
|
OBCE
|
|
4
|
70
|
90
|
OBCE
|
3）優點：這種測試方法可以對程序進行徹底的測試，比前面五種的覆蓋面都廣。
4）缺點：由于路徑覆蓋需要對所有可能的路徑進行測試（包括循環、條件組合、分支選擇等），那么需要設計大量、復雜的測試用例，使得工作量呈指數級增長。而在有些情況下，一些執行路徑是不可能被執行的，如：
If （!A）B++；
If （!A）D--；
這兩個語句實際只包括了2條執行路徑，即A為真或假時候對B和D的處理，真或假不可能都存在，而路徑覆蓋測試則認為是包含了真與假的4條執行路徑。這樣不僅降低了測試效率，而且大量的測試結果的累積，也為排錯帶來麻煩。
總結
白盒測試是一種被廣泛使用的邏輯測試方法，是由程序內部邏輯驅動的一種單元測試方法。只有對程序內部十分了解才能進行適度有效的白盒測試。但是貫穿在程序內部的邏輯存在著不確定性和無窮性，尤其對于大規模復雜軟件。因此我們不能窮舉所有的邏輯路徑，即使窮舉也未必會帶來好運（窮舉不能查出程序邏輯規則錯誤，不能查出數據相關錯誤，不能查出程序遺漏的路徑）。
那么正確使用白盒測試，就要先從代碼分析入手，根據不同的代碼邏輯規則、語句執行情況，選用適合的覆蓋方法。任何一個高效的測試用例，都是針對具體測試場景的。邏輯測試不是片面的測試正確的結果或是測試錯誤的結果，而是盡可能全面地覆蓋每一個邏輯路徑。