以下问题的好算法是什么？
给定一个严格介于0和1之间的有理a/b，找到一个使a/b-1/n最小化的自然n。
我能想到的最简单的算法是比较m=b，b-1，…，当a/b≤1/m时停止的a/b和1/m，然后比较a/b-1/m和a/b-1/（m+1）。那是O（B）。你能做得更好吗？
最佳答案
设k=楼层（b/a），则n必须等于k或k+1。试试这两个候选人，看哪一个获胜。这是O（1）。
这是真的，因为1/（k+1）
以下问题的好算法是什么？
给定一个严格介于0和1之间的有理a/b，找到一个使a/b-1/n最小化的自然n。
我能想到的最简单的算法是比较m=b，b-1，…，当a/b≤1/m时停止的a/b和1/m，然后比较a/b-1/m和a/b-1/（m+1）。那是O（B）。你能做得更好吗？
最佳答案
设k=楼层（b/a），则n必须等于k或k+1。试试这两个候选人，看哪一个获胜。这是O（1）。
这是真的，因为1/（k+1）