b099. E. 聯立多元一次方程式 (優化重製)
內容 ：
在我們所學過的數學知識中，下面兩個二元一次方程式並沒有什麼不同：
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元一次聯立方程組，判斷該方程組是否能經由「改變方程式間的順序」來形成一個「強對角線主導」的方程組。
輸入說明
：
輸入檔的第一行是一個正整數T (1 ≤ T ≤ 50)，表輸入檔中共有T個多元一次方程組。每個方程組的第一行是一個正整數N (2 ≤ N ≤ 1000)，表示一個N元一次方程組。接下來的N行每行會恰有N個數(可能含有小數)，第i行的第j個數表示N元一次方程組中的係數Aij(小數點後至多給至六位數字且-999.999999 ≤ Aij ≤ 999.999999)，任兩個正整數間以恰一個空白字元隔開。B的值本題不需要考慮。
輸出說明
：
輸出應包含T行，第i行是表示第i個方程組能否調換順序形成強對角線主導的方程組。若是，請輸出yes，反之請輸出no。
範例輸入 ：
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
範例輸出 ：
yes yes yes no
提示
：
出處
：
C語言基礎優化版本
/**********************************************************************************/
/* Problem: b099 "E. 聯立多元一次方程式" from 2005 NPSC 國中組初賽 */
/* Language: C */
/* Result: AC (136ms, 196KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-05 20:27:29 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
double ReadPoint() {
static char c;
int p = 0;
double t = 1;
while((c = getchar()) >= '0')
t /= 10, p = (p << 3) + (p << 1) + (c-'0');
return (double)p*t;
}
int ReadDouble(double *x) {
static char c, neg;
while((c = getchar()) < '-') {if(c == EOF) return EOF;}
if(c == '.') {*x = ReadPoint();return 0;}
neg = (c == '-') ? -1 : 1;
*x = (neg == 1) ? c-'0' : 0;
while((c = getchar()) >= '0')
*x = (*x)*10 + c-'0';
if(c == '.') *x += ReadPoint();
*x *= neg;
return 0;
}
main() {
int t, n, maxflag;
double sum, max, m;
while(scanf("%d", &t) == 1) {
int a, b, c, flag;
while(t--) {
scanf("%d", &n);
flag = 1;
int x[1000] = {0};
for(a = 0; a < n; a++) {
sum = 0, max = -1;
for(b = 0; b < n; b++) {
ReadDouble(&m);
if(m < 0) m *= -1;
sum += m;
if(m > max)
max = m, maxflag = b;
}
sum -= max;
if(sum >= max) flag = 0;
if(flag != 0) {
if(x[maxflag]) flag = 0;
else x[maxflag] = 1;
}
}
puts(flag ? "yes" : "no");
}
}
return 0;
}
C++ 極端優化版本
/**********************************************************************************/
/* Problem: b099 "E. 聯立多元一次方程式" from 2005 NPSC 國中組初賽 */
/* Language: CPP */
/* Result: AC (70ms, 1706KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-05 20:31:09 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
inline int readchar() {
const int N = 1048576;
static char buf[N];
static char *p = buf, *end = buf;
if(p == end) {
if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
p = buf;
}
return *p++;
}
inline double ReadPoint() {
static char c;
int p = 0;
double t = 1;
while((c = readchar()) >= '0')
t /= 10, p = (p << 3) + (p << 1) + (c-'0');
return (double)p*t;
}
inline int ReadDouble(double *x) {
static char c, neg;
while((c = readchar()) < '-') {if(c == EOF) return EOF;}
if(c == '.') {*x = ReadPoint();return 0;}
neg = (c == '-') ? -1 : 1;
*x = (neg == 1) ? c-'0' : 0;
while((c = readchar()) >= '0')
*x = (*x)*10 + c-'0';
if(c == '.') *x += ReadPoint();
*x *= neg;
return 0;
}
inline int ReadInt(int *x) {
static char c, neg;
while((c = readchar()) < '-') {if(c == EOF) return EOF;}
neg = (c == '-') ? -1 : 1;
*x = (neg == 1) ? c-'0' : 0;
while((c = readchar()) >= '0')
*x = (*x << 3) + (*x << 1) + c-'0';
*x *= neg;
return 1;
}
main() {
int t, n, maxflag;
double sum, max, m;
while(ReadInt(&t) != EOF) {
int a, b, c, flag;
while(t--) {
ReadInt(&n);
flag = 1;
int x[1000] = {0};
for(a = 0; a < n; a++) {
sum = 0, max = -1;
for(b = 0; b < n; b++) {
ReadDouble(&m);
if(m < 0) m *= -1;
sum += m;
if(m > max)
max = m, maxflag = b;
}
sum -= max;
if(sum >= max) flag = 0;
if(flag) {
if(x[maxflag]) flag = 0;
else x[maxflag] = 1;
}
}
puts(flag ? "yes" : "no");
}
}
return 0;
}
上一篇：b018. F. 營地
下一篇：d956. G. 失落的維京戰機