求解最接近某个无理数的分数

未分类

题意：
给定一个无理数（用浮点数表示）$x$,且$x\in (0,1)$，求出一个$a/b$，满足$1\leq b\leq 100000,使|\frac{a}{b}-x|最小$.

考虑使用类似二分的方法逼近正解，假设当前左边界是$a/b$,右边界是$c/d$,如何求一个“好的”中点出来进行计算就成了一个问题.
这里使用的中点是$(a+c)/(b+d)$,显然$a/b < (a+c)/(b+d) < c/d$.
判断$x$和$(a+c)/(b+d)$的大小关系，然后递推计算即可.
初始边界是$0/1和1/1$，结束条件是$b+d>100000$.
最后得到两个边界，选距离$x$最小的边界作为答案即可.

在随机输入一个浮点数进行计算的时候，能在$200$次迭代内结束计算.
如果不是无理数而是特殊设置的数据例如$0.1,0.333333,0.9$，该迭代方法效率会比较慢.

原题链接：2017 Qingdao Online http://acm.hdu.edu.cn/showproblem.php?pid=6209
参考程序：https://paste.ubuntu.com/p/8jRDHqvWSH/