回分類題庫
g005: E.聯立多元一次方程式
關鍵字: NPSC 2005 國中組初賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 77 Times / 55 Users | Submit : 203 Times / 70 Users | Accepted rate : 79%
題目加入時間 : 2011-12-06 10:01

Content: 简体中文

在我們所學過的數學知識中,下面兩個二元一次方程式並沒有什麼不同:

5X + 4Y = 9         0.000001X + 8Y = 8
0.000001X + 8Y = 8     5X + 4Y = 9

這兩組聯立二元一次方程式所得到的解應該是一樣的(直觀地來看,應該非常接近於X=1, Y=1),遺憾的是我們眼前的這部電子計算機,並不這麼認為。事實上,利用電腦來計算含有浮點數的問題常常會引發各式各樣的誤差,大多時候這些誤差是可以非常渺小到我們所無法感覺,但很多時候這些誤差會使得電腦解出我們想都想不到的答案。解聯立多元一次方程式就是一個很好的例子。

重新來複習一下,所謂N元一次方程式是如下列的N組方程式:

A11X1 + A12X2 + A13X3 + … + A1NXN = B1
A21X1 + A22X2 + A23X3 + … + A2NXN = B2
A31X1 + A32X2 + A33X3 + … + A3NXN = B3
.
.
.
AN1X1 + AN2X2 + AN3X3 + … + ANNXN = BN

如果代入N=2,就是形成如下所示的二元一次方程式:

A11X1 + A12X2 = B1
A21X1 + A22X2 = B2

當然平時我們習慣以下面的符號來表示它:

AX + BY = C
DX + EY = F

過事實上它們代表著同樣一件事。

隨著工程問題日益複雜與龐大,使用電子計算機來求解大型的聯立方程式(實際地說,N從數百到數千的範圍)是勢在必行的,然而浮點數運算上的問題卻又常常困擾著我們;這裡,我們需要你的幫助。

5 X + 4Y = 9        0.00001X + 8Y = 8
0.00001X + 8 Y = 8     5X + 4Y = 9

我們說左邊這組二元一次方程式是比較「優質」的方程組,是因為它是一個「對角線主導」(diagonal dominate)的方程組,也就是說在對角線上的兩個係數5和8都是同一個方程式的係數絕對值中最大的(5 > 4, 8 > 0.00001)。

在三元一次方程組中一個對角線主導的例子:

8X + 2Y + Z = 7     (8 > 2, 8 > 1)
4X – 6Y  + Z = 10    (6 > 4, 6 > 1)
-2X – 3Y – 7Z = 0    (7 > 2, 7 > 3)

我們發現,上面這個方程組不但是對角線主導,它還有更好的性質。就是對角線上的元素不但是同方程式中絕對值最大的係數,它甚至大於其他係數絕對值的總和:(8>1+2, 6>1+4, 7>2+3),我們稱這是一個「強對角線主導」的方程組。

數學家幫我們證明了,強對角線主導的方程組用計算機做運算必定可以達到高精準的結果,現在必須要請求你的幫忙,能否寫一個程式,對於一給定的N元一次聯立方程組,判斷該方程組是否能經由「改變方程式間的順序」來形成一個「強對角線主導」的方程組。

Input:

輸入檔的第一行是一個正整數T (1 ≤ T ≤ 50),表輸入檔中共有T個多元一次方程組。每個方程組的第一行是一個正整數N (2 ≤ N ≤ 1000),表示一個N元一次方程組。接下來的N行每行會恰有N個數(可能含有小數),第i行的第j個數表示N元一次方程組中的係數Aij(小數點後至多給至六位數字且-999.999999 ≤ Aij ≤ 999.999999),任兩個正整數間以恰一個空白字元隔開。B的值本題不需要考慮。

Output:

輸出應包含T行,第i行是表示第i個方程組能否調換順序形成強對角線主導的方程組。若是,請輸出yes,反之請輸出no。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
4
2
5 4
0.000001 8
2
0.000001 8
5 4
3
8 2 1
4 -6 1
-2 -3 -7
3
8 2 1
4 -6 1
-2 -3 -4

Sample Output :

yes
yes
yes
no

Hint :

Author :

NPSC 2005 國中組初賽 (管理員:sagit)

  Solve it!   Status Forum