XTU 1236 Fraction：小數轉最簡分數（分母≤1000）枚舉解法

XTU 1236 Fraction：小數轉最簡分數（分母≤1000）枚舉解法

題目描述

給定 0~1 之間的有限小數 x，將其轉換為分數 p/q，要求：
1. 分母 q ∈ [1, 1000]
2. |p/q - x| 最小（絕對誤差最小）
3. 若多解，選分數值最小者（即 p/q 最小）
4. 輸出最簡形式（p、q 互質）

輸入輸出範例

輸入：
3
0.9999999999999
0.3333333333333
0.2222222222222

輸出：
1/1
1/3
2/9

解題思路

分母範圍極小（≤1000），直接枚舉所有分母 q=1..1000：
- 對每個 q，最佳分子 p = round(x × q)（四捨五入）
- 計算誤差 |p/q - x|，記錄誤差最小的 (p,q)
- 最後約分：p/=gcd(p,q), q/=gcd(p,q)

注意：題目說「若多解選最小分數」，但誤差最小通常唯一；若真有並列，枚舉 q 從小到大，p 取 round，自然先遇到分數值較小的解（需驗證）。代碼中直接用 `>` 更新，保留首個最小誤差解，符合要求。

參考代碼 (C++)

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

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        double x; scanf("%lf", &x);
        double bestErr = x; // 初始誤差設為 x (對應 0/1)
        int bestP = 0, bestQ = 1;
        for (int q = 1; q <= 1000; q++) {
            int p = int(x * q + 0.5); // 四捨五入
            double err = fabs((double)p / q - x);
            if (err < bestErr - 1e-12) { // 避免浮點誤差
                bestErr = err;
                bestP = p;
                bestQ = q;
            }
        }
        int g = __gcd(bestP, bestQ);
        printf("%d/%d\n", bestP / g, bestQ / g);
    }
    return 0;
}

關鍵點

• 枚舉分母 1..1000，O(1000) 極快，T≤10000 總 10⁷ 運算毫無壓力。
• 浮點比較加小 epsilon（1e-12）避免精度問題。
• 用 `double` 存儲 x 足夠（題目提示）。
• 輸出前必須約分到最簡形式（`__gcd` / `std::gcd`）。