algorithm - 在两个给定的有理数之间找到最简单的有理数

Question

我发现了一个与有理数相关的问题。

给定两个有理数，任务是找出它们之间最简单的有理数。

对于这个问题，有理数的简单性可以定义为分子最小的有理数，尽管我对这个指标的其他建议持开放态度，例如similar question to Math stack exchange ，如果它使解决方案更容易。

示例输入和输出可能是:

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

关于如何解决这个问题有任何想法或至少是建议吗？我在挣扎。

谢谢

编辑:

补充观察:

• 虽然给定的两个有理数之间有无穷多个有理数，但比这两个更简单的有理数确实有无穷多个。
• 简单的解决方案可能只是尝试分子/分母的所有组合(分别从 1 到最高分子或分母)，减少它们，然后查看数字是否介于两者之间。我不确定它的 O 复杂度是多少，但我猜应该是 n²。

Answer 1

相关数学在维基百科文章中描述 continued fractions .简而言之，您计算下端点和上限端点的两个连分数，然后尝试四种组合，其中连分数在公共(public)端点之后被截断。

这是一个 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)))