Найти простейшее рациональное число между двумя данными рациональными числами

Question

Я нашел проблему, связанную с рациональными числами.

Даны два рациональных числа, и задача состоит в том, чтобы найти простейшее рациональное число между ними.

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

Пример входных и выходных данных может быть:

Inputs: 1110/416 and 1110/417, Output: 8/3
Inputs: 500/166 and 500/167, Output: 3/1

Есть идеи или хотя бы совет, как подойти к этой проблеме? Я пытаюсь.

Спасибо

РЕДАКТИРОВАТЬ:

Дополнительные наблюдения:

• Хотя между двумя данными рациональными числами бесконечно много рациональных чисел, на самом деле существует конечное число рациональных чисел, которые проще, чем два.
• Тривиальное решение может состоять в том, чтобы просто попробовать все комбинации числитель / знаменатель (в диапазоне от 1 до самого высокого числителя или знаменателя соответственно), уменьшить их и посмотреть, находится ли число между ними. Я не уверен, какова будет его сложность, но я бы предположил что-то вроде n².

Answer 1

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

Вот реализация Python.

import fractions


F = fractions.Fraction


def to_continued_fractions(x):
    a = []
    while True:
        q, r = divmod(x.numerator, x.denominator)
        a.append(q)
        if r == 0:
            break
        x = F(x.denominator, r)
    return (a, a[:-1] + [a[-1] - 1, 1])


def combine(a, b):
    i = 0
    while i < len(a) and i < len(b):
        if a[i] != b[i]:
            return a[:i] + [min(a[i], b[i]) + 1]
        i += 1
    if i < len(a):
        return a[:i] + [a[i] + 1]
    if i < len(b):
        return a[:i] + [b[i] + 1]
    assert False


def from_continued_fraction(a):
    x = fractions.Fraction(a[-1])
    for i in range(len(a) - 2, -1, -1):
        x = a[i] + 1 / x
    return x


def between(x, y):
    def predicate(z):
        return x < z < y or y < z < x

    return predicate


def simplicity(x):
    return x.numerator


def simplest_between(x, y):
    return min(filter(between(x, y), (from_continued_fraction(combine(a, b)) for a in to_continued_fractions(x) for b in to_continued_fractions(y))), key=simplicity)


print(simplest_between(F(1110, 416), F(1110, 417)))
print(simplest_between(F(500, 166), F(500, 167)))

Answer 2

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

Напомним, что цель состоит в том, чтобы найти простейшую дробь в заданном интервале. Здесь простейший имеет специфический (и довольно сильный) смысл: скажем, что дробь x = s/tпроще дроби _y = u/v(оба написаны в самых низких терминах), если abs(s) <= abs(u) а также t <= v и по крайней мере одно из этих двух неравенств является строгим. Обратите внимание, что с этим определением проще не приводит к полному упорядочению: ни одна из дробей 2/5или же 3/4проще другого; тем не менее, это (не сразу очевидная) теорема о том, что любой подинтервал реальной строки, содержащий хотя бы одну дробь, содержит простейшую дробь — дробь, которая проще, чем все другие дроби в подинтервале.

Код

Без лишних слов, вот некоторый код Python для нашей версии . Далее следуют пояснения и набросок доказательства правильности.

      def simplest_between(x: Fraction, y: Fraction) -> Fraction:
    """
    Simplest fraction strictly between fractions x and y.
    """
    if x == y:
        raise ValueError("no fractions between x and y")

    # Reduce to case 0 <= x < y
    x, y = min(x, y), max(x, y)
    if y <= 0:
        return -simplest_between(-y, -x)
    elif x < 0:
        return Fraction(0, 1)

    # Find the simplest fraction in (s/t, u/v)
    s, t, u, v = x.numerator, x.denominator, y.numerator, y.denominator
    a, b, c, d = 1, 0, 0, 1
    while True:
        q = s // t
        s, t, u, v = v, u - q * v, t, s - q * t
        a, b, c, d = b + q * a, a, d + q * c, c
        if t > s:
            return Fraction(a + b, c + d)

Объяснение

Первая часть кода — сведение к случаю, когда 0 <= x < y— должно говорить само за себя: если интервал полностью лежит в отрицательных числах, мы используем симметрию относительно нуля и находим простейшую дробь в (-y, -x), а затем отрицать. В противном случае, если интервал содержит ноль, то 0/1самая простая дробь в . В противном случае лежит в пределах положительных реалов, и мы переходим ко второй части кода.

Во второй части будет интереснее. На каждом шаге алгоритма:

• s, t, uи являются неотрицательными целыми числами, описывающими подынтервал положительной вещественной прямой ( vможет быть нулевым, так что u/vпредставляет бесконечную конечную точку).
• , , и — целые неотрицательные числа, описывающие дробно-линейное преобразование T : z ↦ (az + b) / (cz + d).
• дает биекцию между и исходным интервалом
• ad-bc = ±1(знак меняется при каждой итерации)

Изначально, J = (s/t, u/v)является исходным интервалом и представляет собой тождественное преобразование (заданное формулой a = d = 1, b = c = 0). Цикл while неоднократно заменяется интервалом 1/(J - q), где пол левого конца , и одновременно обновляет , , и соответственно для сохранения биекции Tмежду и .

Цикл завершается, как только интервал содержит 1. Окончание цикла гарантировано: сумма s + t + u + v— натуральное число, которое строго убывает на каждой итерации, за исключением, возможно, первой итерации (где qможет быть 0).

На выходе из цикла каждая дробь имеет вид некоторой дроби p/q(в пределах J; более того, выражение (ap + bq)/(cp + dq)находится уже в самом низком выражении: это следует из gcd(p, q) = 1вместе с ad - bc = ±1. С a, b, cа также dвсе неотрицательны, отсюда следует, что (a+b)/(c+d)самая простая дробь в (x, y).

Как насчет закрытых интервалов?

Как и в случае с ответом Дэвида, simplest_betweenвсегда производит дробь строго между заданными конечными точками. Следующий вариант очень похож, но дает простейшую дробь в заданном интервале . [x, y]вместо.

      def simplest_between_lax(x: Fraction, y: Fraction) -> Fraction:
    """
    Simplest fraction between fractions x and y, inclusive of x and y.
    """
    # Reduce to case 0 < x <= y
    x, y = min(x, y), max(x, y)
    if y < 0:
        return -simplest_between_lax(-y, -x)
    elif x <= 0:
        return fractions.Fraction(0, 1)

    # Find the simplest fraction in [s/t, u/v]
    s, t, u, v = x.numerator, x.denominator, y.numerator, y.denominator
    a, b, c, d = 1, 0, 0, 1
    while True:
        q = (s - 1) // t
        s, t, u, v = v, u - q * v, t, s - q * t
        a, b, c, d = b + q * a, a, d + q * c, c
        if t >= s:
            return fractions.Fraction(a + b, c + d)

Вот примеры входных данных OP:

      >>> F = fractions.Fraction
>>> simplest_between(F(1110, 416), F(1110, 417))
Fraction(8, 3)
>>> simplest_between(F(500, 166), F(500, 167))
Fraction(3, 1)

Конечно, версия с закрытым интервалом дает те же результаты:

      >>> simplest_between_lax(F(1110, 416), F(1110, 417))
Fraction(8, 3)
>>> simplest_between_lax(F(500, 166), F(500, 167))
Fraction(3, 1)

Но simplest_between_laxпозволяет рассматривать конечные точки:

      >>> simplest_between(3, 4)
Fraction(7, 2)
>>> simplest_between_lax(3, 4)
Fraction(3, 1)
>>> simplest_between(F(7, 6), F(6, 5))
Fraction(13, 11)
>>> simplest_between_lax(F(7, 6), F(6, 5))
Fraction(6, 5)

Answer 3

Допустим, числитель хорош, если есть некоторый знаменатель, который приводит к рациональному числу между вашими входами.

Вы можете проверить, хорош ли числитель в O(1). Скажем, вы хотите проверить числитель n, и вы вводите w,x (для w/x) и y,z (для y / z).

n хорошо, если есть целое число между nx / w и n z / y.

Затем вы можете сделать это в O (хороший числитель), проверив все числители, пока не найдете подходящий. Если конечные точки действительны, это займет максимум мин (w, y).

Answer 4

Вы можете попробовать следующее O(n^2 log n) алгоритм:

• Цикл от одного числителя до другого
• Внутри этого цикла, цикл от одного знаменателя к другому. Лемма заключается в том, что каждая дробь, созданная циклом, находится между двумя конечными дробями.
• Для каждой дроби упростите ее, найдя наибольший общий делитель числителя и знаменателя, и разделите числитель на нее. Это должно позволить вам найти самый маленький числитель. Алгоритм Евклида делает это в O(log n).