網際網路程式設計全國大賽
初賽題目
題目(5) 解線性方程組
執行檔 | LINEAR.EXE |
輸入檔 | LINEAR.IN |
輸出檔 | LINEAR.OUT |
執行時間限制 | 30 秒 |
考慮下列 n 個線性方程式︰
a1,1 x1 + a1,2 x2 + ... + a1,n xn = b1
a2,1 x1 + a2,2 x2 + ... + a2,n xn = b2
.
.
.
an,1 x1 + a2,2 x2 + ... + an,n xn = bn
假設有 n 個方程式,則利用高斯消去法可以解出未知數 x1, x2, ..., xn 之值。假設所有的係數 ai,j 以及 bi 都是有理數,其解 x1, x2, ..., xn 也必為有理數。寫一程式,利用高斯消去法求解有理係數的線性方程組。
輸入檔說明
- 輸入資料儲存在檔案 LINEAR.IN 中,此一檔案可能包含許多組線性方程式。每一組線性方程式都由一個正整數 n 開始(n <= 100),接下來就是 n 個方程式。每一個方程式均含有 n+1 個有理數 ai,1, ai,2, ... ai,n, bi。
- 有理數的表示方式有兩種,第一種為一整數 p,第二種為 p/q,其中 p 和 q 都是整數,且 q>1。
- 最後一組方程式之後會有一個 0,這表示整個資料到此為止,亦即讀到 n=0 時程式即應結束。
為了計算方便,我們假設所有數字用 32 位元有號整數計算都會正確。
輸出檔說明
針對每一組方程式,先印出此方程式,再印出其解。由於方程式間可能線性相依,在此情況下會有無窮多組解或是無解。若此組方程式的解並非唯一,則印出 infinite many solutions。 若此組方程式無解,則印出 no solutions。輸出時,每組答案間要加一行空白,而顯示方程式時,分數要約分,分母為 1 時只印分子,式子中間不可以有空白,等號兩邊最前面的數字前面也不可以有正號。若某一項係數為 0,仍要印出該項,不可省略。
範例
LINEAR.IN |
1
2 3
2
1 2 3
2 4 6
2
1 2 3
1 2 4
2
4 -5 8
3 2 12
2
1/2 -2/3 -1
1/4 1/9 3/2
1
0 0
0
|
|
LINEAR.OUT |
2x1=3
x1=3/2
1x1+2x2=3
2x1+4x2=6
infinite many solutions
1x1+2x2=3
1x1+2x2=4
no solutions
4x1-5x2=8
3x1+2x2=12
x1=76/23
x2=24/23
1/2x1-2/3x2=-1
1/4x1+1/9x2=3/2
x1=4
x2=9/2
0x1=0
infinite many solutions
|
|