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

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

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

对于这个问题，可以将有理数的简单性定义为分子最小的有理数，尽管我愿意接受其他有关此指标的建议，例如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复杂度是多少，但是我猜想像n2这样的东西。

最佳答案

相关数学在continued fractions上的Wikipedia文章中进行了描述。简而言之，您可以计算上下端点的两个连续分数，然后尝试四种组合，其中连续分数在公共(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)))