UVA 654 Ratio：暴力枚舉求最佳分數逼近

UVA 654 Ratio：暴力枚舉求最佳分數逼近

給定兩個整數 n 和 m，要求找出分母從 1 到 m 的所有分數 j/i，使得這些分數依序越來越接近目標值 n/m。輸出每一個比前一個更接近目標值的分數。

解題思路

對每一個可能的分母 i（1 ≤ i ≤ m），計算使分數 j/i 最接近 n/m 的分子 j。根據四捨五入原理，j = floor(i * n / m + 0.5)。維護一個變量記錄目前的最小誤差，若當前分數的誤差更小，則輸出該分數並更新最小誤差。

代碼實現

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int INF = 0x3f3f3f;
int n, m;
int main() {
    int t = 0;
    while (scanf("%d%d", &n, &m) != EOF) {
        if (t) printf("\n");
        t = 1;
        double k = n / (m * 1.0), r = INF;
        for (int i = 1; i <= m; i++) {
            int j = i * k + 0.5;
            double temp = fabs(j / (i * 1.0) - k);
            if (temp < r) {
                r = temp;
                printf("%d/%d\n", j, i);
            }
        }
    }
    return 0;
}

時間複雜度為 O(m)，空間複雜度 O(1)，完全滿足題目要求。