HDU 2199 方程求解 二分法詳解

問題描述

給定多項式方程 8x⁴ + 7x³ + 2x² + 3x + 6 = Y，要求在區間 [0, 100] 內求解 x，精度要求小數點後 4 位。若無解則輸出 "No solution!"。

數學分析

定義函數 f(x) = 8x⁴ + 7x³ + 2x² + 3x + 6。其導函數 f'(x) = 32x³ + 21x² + 4x + 3，在 [0, 100] 上恒大於 0，故 f(x) 嚴格單調遞增。因此方程最多有一個解。

二分法求解

1. 計算 f(0) = 6 和 f(100)（極大值）
2. 若 Y < 6 或 Y > f(100)，直接輸出 "No solution!"
3. 否則在 [0, 100] 上二分查找，直到區間長度 < 10⁻⁵（保證 4 位小數精度）
4. 每次取中點 mid，比較 f(mid) 與 Y 的大小縮小區間

代碼實現

double f(double x) {
    return 8*x*x*x*x + 7*x*x*x + 2*x*x + 3*x + 6;
    // 或使用 Horner 規則：((8*x + 7)*x + 2)*x + 3)*x + 6
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        double Y; scanf("%lf", &Y);
        double L = 0, R = 100;
        double fL = f(L), fR = f(R);
        
        if (Y < fL || Y > fR) {
            puts("No solution!");
            continue;
        }
        
        while (R - L > 1e-7) { // 精度略高於 1e-4
            double mid = (L + R) / 2;
            if (f(mid) > Y) R = mid;
            else L = mid;
        }
        printf("%.4f\n", (L + R) / 2);
    }
    return 0;
}

注意事項

• 使用 double 保證精度
• 終止條件設為 1e-7 而非 1e-4，避免邊界誤差
• f(x) 計算可用 Horner 規則減少乘法次數並提高數值穩定性
• 單調性是二分法適用的必要條件