b099. E. 聯立多元一次方程式 (優化重製)＠Morris' Blog

2011-08-09 07:59:50| 人氣5,339| 回應0 | 上一篇 | 下一篇

b099. E. 聯立多元一次方程式 (優化重製)

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

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

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

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

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

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

A₁₁X₁ + A₁₂X₂ + A₁₃X₃ + … + A_1NX_N = B₁

A₂₁X₁ + A₂₂X₂ + A₂₃X₃ + … + A_2NX_N = B₂

A₃₁X₁ + A₃₂X₂ + A₃₃X₃ + … + A_3NX_N = B₃

A_N1X₁ + A_N2X₂ + A_N3X₃ + … + A_NNX_N = B_N

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

A₁₁X₁ + A₁₂X₂= B₁

A₂₁X₁ + A₂₂X₂= B₂

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

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元一次方程組中的係數A_ij(小數點後至多給至六位數字且-999.999999 ≤ A_ij ≤ 999.999999)，任兩個正整數間以恰一個空白字元隔開。B的值本題不需要考慮。

輸出說明：

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

範例輸入：

範例輸出：

yes
yes
yes
no

提示：

出處：

2005 NPSC 國中組初賽

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;
}

我要檢舉

#b099#E. 聯立多元一次方程式

台長： Morris

您可能對以下文章有興趣

b238. A. 腹黑、傲嬌

[ZJ][KM算法] d210. 老問題

b043. B. 踩地雷回來了

b046. E. 智慧型單字查詢

人氣(5,339) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: NPSC |
此分類下一篇:d956. G. 失落的維京戰機
此分類上一篇:b018. F. 營地

回應(0)