P1298 最接近的分数

眼镜蛇

2026-06-12 20:31:50

发布于：江西

1阅读

0回复

0点赞

P1298 最接近的分数

题目描述

给出一个正小数，找出分子（分子 $\ge0$ ）不超过 $M$ ，分母不超过 $N$ 的最简分数或整数，使其最接近给出的小数。“最接近”是指在数轴上该分数距离给出的小数最近，如果这个分数不唯一，输出 TOO MANY。

输入格式

输入共有 $2$ 行，第一行包含两个用空格隔开的正整数 $M$ 和 $N$ ，表示要求的分数其分子不超过 $M$ ，分母不超过 $N$ ；第二行为小数 $R(R>0)$ ， $R$ 的整数部分为一个阿拉伯数字，小数部分最多有十位。

输出格式

输出仅 $1$ 行，若解唯一则输出 分子/分母（整数 $K$ 写成 $\dfrac{K}{1}$ ），否则输出 TOO MANY。

输入输出样例 #1

输入 #1

360 120
3.1415926536

输出 #1

355/113

说明/提示

数据范围及约定

对于全部数据，保证 $1\le M,N\le 10^7$ 。

AC代码

#include<bits/stdc++.h>
using namespace std;

// 辗转相除法求最大公约数
long long gcd(long long a, long long b){
	while(b){
		long long t=b;
		b=a%b;
		a=t;
	}
	return a;
}

// 避免浮点数精度误差
int f(double x) {
	return (x>1e-12)-(x<-1e-12);
}

int main(){
	long long m,n;
	long double r;
	cin>>m>>n>>r;
    // 初始化Stern-Brocot树左右边界
	long long lm=0,ln=1;
	long long rm=1,rn=0;
	long long mm=0,mn=0;
	long double ans=0.0;
    // 通过二分查找逼近目标
	while(true){
        // 计算中位分数
		mm=lm+rm;
		mn=ln+rn;
        // 超过限定范围，停止逼近
		if(mm>m || mn>n){
			break;
		}
        // 判断误差
		ans=(long double)mm/mn;
		int flag=f(r*mn-mm);
		if(flag==0){
			cout<<mm<<'/'<<mn;
			return 0;
		}
        // 更新左右边界
		if(flag>0){
			lm=mm;
			ln=mn;
		}else{
			rm=mm;
			rn=mn;
		}
	}
    // 计算左右分数与r的误差
	long double errl=fabs((long double)lm/ln-r);
	long double errr=fabs((long double)rm/rn-r);
    // 判断误差是否相等
	int flag=f((r-errl)-(errr-r));
	if(flag==0){
		cout<<"TOO MANY";
	}else if(errl<errr){
		cout<<lm/gcd(lm,ln)<<"/"<<ln/gcd(lm,ln);
	}else{
		cout<<rm/gcd(rm,rn)<<"/"<<rn/gcd(rm,rn);
	}
	return 0;
}