ZeroJudge 解題筆記：d854. NOIP2001 1.一元三次方程求解

作者：王一哲
日期：2026年5月7日


ZeroJudge 題目連結：d854. NOIP2001 1.一元三次方程求解

解題想法

先檢查高次項的係數 $a$，如果 $a<0$ 則將所有的係數都乘以 $-1$，確保圖形為最右側朝上。下圖是以範例測資的數據繪製，$f(x) = x^3 - 5 x^2 - 4 x + 20$，可以由兩個極值 $x_1, x_2$ 將曲線分為 $3$ 個區域，左側遞增、中間遞減、右側遞增。接下來分別對 $3$ 個區域求根。 左側的根範圍為 $[-100, x_1]$，對答案二分搜 $100$ 次，將中間值 $mid = (high + low) / 2$ 代入 $f(x) = a x^3 + b x^2 + c x + d$，如果 $f(mid) < 0$ 代表 $mid$ 在根的左側，提高下限 $low = mid$，反之則降低上限 $high = mid$。 中間的根範圍為 $[x_1, x_2]$，對答案二分搜 $100$ 次，將中間值 $mid = (high + low) / 2$ 代入 $f(x) = a x^3 + b x^2 + c x + d$，如果 $f(mid) < 0$ 代表 $mid$ 在根的右側，提高下限 $low = mid$，反之則降低上限 $high = mid$。 右側的根範圍為 $[x_2, 100]$，對答案二分搜 $100$ 次，將中間值 $mid = (high + low) / 2$ 代入 $f(x) = a x^3 + b x^2 + c x + d$，如果 $f(mid) < 0$ 代表 $mid$ 在根的左側，提高下限 $low = mid$，反之則降低上限 $high = mid$。

Python 程式碼

使用時間約為 15 ms，記憶體約為 8.8 MB，通過測試。

def f(a, b, c, d, x):
    return a*x*x*x + b*x*x + c*x + d

def solve():
    import sys
    
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        # 係數，浮點數格式
        a, b, c ,d = map(float, data[ptr:ptr+4])
        ptr += 4
        # 將高次項係數調整成正的
        if a < 0:
            a, b, c, d = -a, -b, -c, -d
        # 找 dx 的根，dx = 3*a x**2 + 2*b x + c
        D = 4*b*b - 12*a*c
        x1 = (-2*b - D**0.5) / (6*a)
        x2 = (-2*b + D**0.5) / (6*a)
        # 區間 [-100, x1] 的根 r1，線段左下、右上
        low, high = -100, x1
        for _ in range(100):
            mid = (low + high) / 2
            y = f(a, b, c, d, mid)
            if y < 0:  # mid 在根的左側
                low = mid
            else:  # mid 在根的右側
                high = mid
        r1 = mid
        # 區間 [x1, x2] 的根 r2，線段左上、右下
        low, high = x1, x2
        for _ in range(100):
            mid = (low + high) / 2
            y = f(a, b, c, d, mid)
            if y > 0:  # mid 在根的右側
                low = mid
            else:  # mid 在根的左側
                high = mid
        r2 = mid
        # 區間 [x2, -100] 的根 r3，線段左下、右上
        low, high = x2, 100
        for _ in range(100):
            mid = (low + high) / 2
            y = f(a, b, c, d, mid)
            if y < 0:  # mid 在根的左側
                low = mid
            else:  # mid 在根的右側
                high = mid
        r3 = mid
        result.append(f"{r1:.2f} {r2:.2f} {r3:.2f}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

C++ 程式碼

使用時間約為 1 ms，記憶體約為 2 MB，通過測試。

#include 
#include 

double f(double a, double b, double c, double d, double x) {
    return a*x*x*x + b*x*x + c*x + d;
}

int main() {
    double a, b, c, d;  // 係數，浮點數格式
    while(scanf("%lf %lf %lf %lf", &a, &b, &c, &d) != EOF) {
        // 將高次項係數調整成正的
        if (a < 0) {
            a = -a; b = -b; c = -c; d = -d;
        }
        // 找 dx 的根，dx = 3*a x**2 + 2*b x + c
        double D = 4*b*b - 12*a*c;
        double x1 = (-2*b - sqrtf(D)) / (6*a), x2 = (-2*b + sqrtf(D)) / (6*a);
        // 區間 [-100, x1] 的根 r1，線段左下、右上
        double low = -100.0, high = x1, mid = 0.0;
        for(int i=0; i<100; i++) {
            mid = (high + low) / 2.0;
            if (f(a, b, c, d, mid) < 0) low = mid;
            else high = mid;
        }
        double r1 = mid;
        // 區間 [x1, x2] 的根 r2，線段左上、右下
        low = x1; high = x2;
        for(int i=0; i<100; i++) {
            mid = (high + low) / 2.0;
            if (f(a, b, c, d, mid) > 0) low = mid;
            else high = mid;
        }
        double r2 = mid;
        // 區間 [x2, -100] 的根 r3，線段左下、右上
        low = x2; high = 100.0;
        for(int i=0; i<100; i++) {
            mid = (high + low) / 2.0;
            if (f(a, b, c, d, mid) < 0) low = mid;
            else high = mid;
        }
        double r3 = mid;
        printf("%.2lf %.2lf %.2lf\n", r1, r2, r3);
    }
    return 0;
}