Aby*_*sal 5 algorithm math fractions
对于以下问题,什么是一个好的算法？
给定一个严格在0和1之间的理性a/b,找到一个最小化| 的自然n a/b - 1/n |.
我能想到的最简单的算法是比较一/b和1/米为米 = b,b - 1,...,停车时一/b ≤1/米,然后比较| a/b - 1/m | 和| a/b - 1/(m + 1) |.那是O(b).你可以做的更好吗？
设k = floor(b/a),然后n必须等于k或k + 1.尝试2名候选人,看看哪一名获胜.这是O(1).
这是真实的,因为1 /(k + 1)<= a/b <= 1/k,其又来自不等式k <= b/a <= k + 1.