algorithm - 将 (0, 1) 中的有理数舍入到最接近的单位分数

Question

以下问题的好的算法是什么？

Given a rational a / b strictly between 0 and 1, find a natural n that minimizes |a / b - 1 / n|.

我能想到的最简单的算法是比较 a/b 和 1/m 为 m = b, b - 1, ..., 当 a/b ≤ 1/m< 时停止/em>，然后比较 |a/b - 1/m|和 |a/b - 1/(m + 1)|。那是 O( b )。你能做得更好吗？

Answer 1

令 k = floor(b/a) 然后 n 必须等于 k ​​或 k+1。尝试 2 个候选人，看看哪一个获胜。这是 O(1)。

这是真的，因为 1/(k+1) <= a/b <= 1/k 反过来又从不等式 k <= b/a <= k+1 推导出来。