UVA654- Ratio(暴力枚舉)

UVA654- Ratio(暴力枚舉)

題目鏈接

題意：給出兩個數n，m，求分母從1-m越來越接近n/m的序列

思路：從1-m枚舉分母i，然後維護一個值，使序列越來越靠近n/m。分子j的話，j/i趨近於n/m時，可以得到（int）j=i*n/m+0.5。

代碼：

#include 
#include 
#include 
#include 
#include 

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;
}