PAT 乙級 1003：二分法求三次多項式根

題目描述

給定三次多項式 f(x) = a₃x³ + a₂x² + a₁x + a₀ 及區間 [a, b]，保證區間內存在唯一單根。用二分法求根，精確到小數點後 2 位。

二分法步驟

1. 若 f(a) * f(b) ≥ 0 則無根或偶數根（題目保證唯一單根，故必 < 0）
2. 計算中點 mid = (a+b)/2
3. 若 f(mid) == 0 → 直接輸出
4. 若 f(mid) * f(a) > 0 → 根在 [mid, b]，令 a = mid
5. 否則根在 [a, mid]，令 b = mid
6. 重複直到區間長度 < ε（如 1e-8）

C++ 實現

#include <cstdio>
#include <cmath>
using namespace std;

double a3, a2, a1, a0;
double L, R;
const double EPS = 1e-8;

double f(double x) {
    return a3*x*x*x + a2*x*x + a1*x + a0;
}

int main() {
    scanf("%lf %lf %lf %lf", &a3, &a2, &a1, &a0);
    scanf("%lf %lf", &L, &R);
    double mid;
    while (R - L > EPS) {
        mid = (L + R) / 2;
        if (f(mid) == 0) break;
        if (f(mid) * f(L) > 0) L = mid;
        else R = mid;
    }
    printf("%.2lf\n", mid);
    return 0;
}

注意事項

• 多項式求值用 x*x*x 而非 pow(x,3)，效率更高且精度更好
• ε 取 1e-8 足夠保證小數點後 2 位正確
• 題目保證唯一單根，無需處理多根或無根情況

複雜度

• 時間：O(log((b-a)/ε)) ≈ 30 次迭代
• 空間：O(1)