Найдите ближайшую дробь к данной дроби, имеющую минимальную абсолютную разность

Опубликовано: 22 Сентября, 2022

По трем целым числам x , y и n задача состоит в том, чтобы найти такую пару целых чисел a, b (1 <= b <= n; 0 <= a) , что значение |x/y – a/b| минимально возможно, где |x| представляет собой абсолютное значение x.

Примеры:

Input: x = 3, y = 7, n = 6
Output: 2/5
Explanation: a=2 and b=5 and b<=6 then 3/7 – 2/5 = 1/35, which is the minimum difference possible

Input: x = 12, y = 37, n = 5
Output: 1/3

Подход: Итерация по знаменателю. Пусть знаменатель будет i . Затем требуется выбрать такой числитель d , что |x/y – d/i| минимален. d = (x*i)/y — хороший выбор. Также проверьте d+1 . Обновляя ответ с A/B на d/i, проверьте, не является ли x/y – d/i < x/y -A/B или (B*xy*A) * (i*y) > (i*xy* г) * (Б*у). Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте переменные A и B как -1 , чтобы сохранить ответы.
  • Переберите диапазон [1, N], используя переменную i , и выполните следующие шаги:
    • Инициализируйте переменную d как (i*x)/y как ближайший возможный числитель.
    • Если d больше 0 , а A равно -1 или ABS(B * x – y * A) * ABS(i * y) больше, чем ABS(i * x – y * d) * ABS(B * y), затем установите значение A как d и B как i.
    • Увеличьте значение d на 1.
    • Если d больше 0 , а A равно -1 или ABS(B * x – y * A) * ABS(i * y) больше, чем ABS(i * x – y * d) * ABS(B * y), затем установите значение A как d и B как i.
  • После выполнения вышеуказанных шагов выведите значение A/B в качестве ответа.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N)
Вспомогательное пространство: O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ