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

Question

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

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

对于这个问题,有理数的简单性可以定义为具有最小分子的有理数,尽管我对这个度量的其他建议持开放态度,例如类似于数学堆栈交换的问题,如果它使解决方案更容易.

样本输入和输出可能是:

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

关于如何处理这个问题的任何想法或至少一个建议？我正在挣扎.

谢谢

编辑:

补充意见:

• 虽然在两个给定的有理数之间存在无限多的有理数,但确实有限的许多有理数比两者更简单.
• 平凡的解决方案可能只是尝试分子/分母的所有组合(分别从1到最高分子或分母),减少它们,并查看数字是否介于两者之间.我不确定它的O复杂性是什么,但我猜想有点像n ².

Answer 1

\n

这是大卫·艾森斯塔特上述出色答案的变体。秘密地，它基于完全相同的原理，即找到区间端点的连分数展开式的公共初始部分，但这从它的编码方式来看并不明显，而且它是直接给出正确性证明，无需参考连分数理论。下面进一步给出该证明的概要。

\n

提醒一下，我们的目标是找到给定区间内最简单的分数。这里最简单的有一个特定的（而且相当强烈的）含义：如果和且这两个不等式中至少有一个是严格的，我们会说分数x = s/t比分数更简单y = u/v（两者都用最简单的术语写成） 。请注意，使用此定义更简单并不会产生全排序：分数或都不比另一个更简单；尽管如此，这是一个（不是立即显而易见的）定理，即包含至少一个分数的实线的任何子区间都包含一个最简单的分数\xe2\x80\x94a 一个分数，该分数比子区间中的所有其他分数都简单。abs(s) <= abs(u) t <= v 2/53/4

\n

代码

\n

言归正传，这里是我们版本的simplest_between. 下面是解释和正确性证明的草图。

\n

def simplest_between(x: Fraction, y: Fraction) -> Fraction:\n    """\n    Simplest fraction strictly between fractions x and y.\n    """\n    if x == y:\n        raise ValueError("no fractions between x and y")\n\n    # Reduce to case 0 <= x < y\n    x, y = min(x, y), max(x, y)\n    if y <= 0:\n        return -simplest_between(-y, -x)\n    elif x < 0:\n        return Fraction(0, 1)\n\n    # Find the simplest fraction in (s/t, u/v)\n    s, t, u, v = x.numerator, x.denominator, y.numerator, y.denominator\n    a, b, c, d = 1, 0, 0, 1\n    while True:\n        q = s // t\n        s, t, u, v = v, u - q * v, t, s - q * t\n        a, b, c, d = b + q * a, a, d + q * c, c\n        if t > s:\n            return Fraction(a + b, c + d)\n

\n

解释

\n

代码的第一部分\xe2\x80\x94减少到\xe2\x80\x94的情况0 <= x < y应该是不言自明的：如果区间(x, y)完全位于\n负实数，我们使用关于零的对称性并找到最简单的分数\ nin (-y, -x)，然后取反。否则，如果区间(x, y)包含零，则0/1是 中最简单的分数(x, y)。否则，(x, y)位于正实数范围内，我们继续执行代码的第二部分。

\n

第二部分变得更有趣。在算法的每一步：

\n

\n
• s、t、u和是非负整数，描述正实线的v子区间（可以为零，因此表示无限端点）。J = (s/t, u/v)vu/v
\n
• a、b、c和d是描述线性分数变换 的非负整数T : z \xe2\x86\xa6 (az + b) / (cz + d)。
\n
• TJ给出和 原始区间之间的双射(x, y)
\n
• ad-bc = \xc2\xb11（符号随着每次迭代而交替）
\n

\n

最初，J = (s/t, u/v)是原始区间(x, y)，T是恒等变换（由a = d = 1,给出b = c = 0）。while 循环重复替换J为间隔1/(J - q)，其中q是 的左端点的下限J，并同时相应地更新a、 、和b，以维持\n和之间的双射。cdTJ(x, y)

\n

一旦间隔J包含，循环就会退出1。循环的终止是有保证的：总和s + t + u + v是一个正整数，每次迭代都会严格减少，但第一次迭代可能例外（其中q可以0）。

\n

在循环退出时， in 中的每个分数都具有 ; 中某个分数（带有）的(x, y)形式；此外，该表达式已经是最低级的：这来自于。由于、、和都是非负数，因此是 中最简单的分数。(ap + bq)/(cp + dq)p/qgcd(p, q) = 1J(ap + bq)/(cp + dq)gcd(p, q) = 1ad - bc = \xc2\xb11abcd(a+b)/(c+d)(x, y)

\n

那么闭区间呢？

\n

与大卫的答案一样，总是在给定端点之间严格simplest_between产生一个分数。下一个变体非常相似，但会生成给定闭区间内的最简单分数\n 。[x, y]

\n

def simplest_between_lax(x: Fraction, y: Fraction) -> Fraction:\n    """\n    Simplest fraction between fractions x and y, inclusive of x and y.\n    """\n    # Reduce to case 0 < x <= y\n    x, y = min(x, y), max(x, y)\n    if y < 0:\n        return -simplest_between_lax(-y, -x)\n    elif x <= 0:\n        return fractions.Fraction(0, 1)\n\n    # Find the simplest fraction in [s/t, u/v]\n    s, t, u, v = x.numerator, x.denominator, y.numerator, y.denominator\n    a, b, c, d = 1, 0, 0, 1\n    while True:\n        q = (s - 1) // t\n        s, t, u, v = v, u - q * v, t, s - q * t\n        a, b, c, d = b + q * a, a, d + q * c, c\n        if t >= s:\n            return fractions.Fraction(a + b, c + d)\n

\n

以下是 OP 输入的示例：

\n

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

\n

当然，闭区间版本会产生相同的结果：

\n

>>> simplest_between_lax(F(1110, 416), F(1110, 417))\nFraction(8, 3)\n>>> simplest_between_lax(F(500, 166), F(500, 167))\nFraction(3, 1)\n

\n

但simplest_between_lax允许考虑端点：

\n

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

\n

Answer 2

有关数学的内容，请参见Wikipedia上有关连续分数的文章。简而言之，您可以计算上下端点的两个连续分数，然后尝试四种组合，其中连续分数在公共端点之后被截断。

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