Toyota Programming Contest 2023#8（AtCoder Beginner Contest 333）G. Nearest Fraction（有理实数求分母不超过n的最优逼近）

题目

给一个不超过1的实数r，r最多18位小数，

和一个分母n(n<=1e10)，求分母不超过n的与该有理实数的最优逼近，即二者绝对值之差最小

有理实数显然可以转成分数

思路来源

官方题解

farey序列论文 一类分数问题的研究.pdf

题解

1. 采用python的limit_denominator的函数，注意加上一个eps

2. 采用Yang Zhe《一类分数问题的研究》一论文中提供的方式

3. 在stern-brocot树上二分套二分，或考虑参考官方题解

代码

人生苦短，我选python

from fractions import Fraction
a=input().split(".")[1]
n=int(input())
r=(Fraction(int(a),10**len(a))-Fraction(1,10**100)).limit_denominator(n)
print(r.numerator,r.denominator)

from fractions import *
from decimal import *
x=Fraction(Decimal(input())-Decimal(1e-25)).limit_denominator(int(input()))
print(x.numerator,x.denominator)