Какой алгоритм подходит для следующей задачи?
При рациональном a / b строго между 0 и 1 найдите натуральный n , который минимизирует | a / b - 1 / n |.
Простейший алгоритм, который я могу придумать of - это сравнение a / b и 1 / m для m = b , b - 1,…, остановка, когда a / b ≤ 1 / m , а затем сравнить | a / ] b - 1 / m | и | a / b - 1 / (m + 1) |. Это O ( b ). Можете ли вы сделать что-нибудь лучше?