Округление рациональных чисел в (0, 1) до ближайшей дроби

Question

Какой хороший алгоритм для следующей задачи?

Учитывая рациональное a / b строго между 0 и 1, найдите натуральное n , которое минимизирует | a / b - 1 / n |.

Самый простой алгоритм, который я могу придумать, - это сравнить a / b и 1 / m для m = b , b - 1,…, остановка при a / b ≤ 1 / m , а затем сравнение | 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. </p>

Answer 2

Я считаю, что вы можете сделать это в O (1), используя непрерывные дроби. Любое рациональное число в диапазоне (0, 1] можно записать в виде

1 / (a0 + 1 / (a1 + 1 / (a2 + 1 / (... an))))

Кроме того, это представление обладает некоторыми замечательными свойствами. Для начала, если вы урежете представление в любой точке, вы получите очень хорошее приближение к рациональному числу. В частности, если вы просто урежете это представление на

1 / a0

Тогда доля a / b будет между 1 / a0 и 1 / (a0 + 1). Следовательно, если мы можем получить значение a0, то вы можете просто проверить два вышеуказанных числа, чтобы увидеть, какое из них ближе.

Вторым важным свойством является то, что существует отличный способ получить значение a0: оно определяется отношением b / a. Другими словами, вы можете найти ближайшую дробь следующим образом:

1. Вычислить x = b / a, используя целочисленное деление.
2. Проверьте, ближе ли 1 / x или 1 / (x + 1) к a / b, и выведите результат.

Если a и b вписываются в машинные слова, это выполняется за O (1) раз.

Answer 3

Как указано в комментариях, лучше всего использовать функции «Потолок» и «Пол».

Если ваш рациональный a / b задан как 0 <= x <= 1, то вы можете просто сделать это:

int Rationalize(double x)
{
    int n1 = floor(1 / x);
    int n2 = ceiling(1 / x);

    double e1 = abs(x - 1.0 / n1);
    double e2 = abs(x - 1.0 / n2);

    if (e1 < e2) return n1;
    else return n2;
}

(где предполагается, что абс, пол и потолок заданы заранее)