10

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

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

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

示例输入和输出可能是：

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

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

谢谢

编辑：

其他意见：

  • 尽管两个给定的有理数之间有无限多个有理数，但确实有有限多个比这两个更简单的有理数。
  • 简单的解决方案可能只是尝试分子/分母的所有组合（分别从 1 到最高分子或分母），减少它们，看看数字是否介于两者之间。我不确定它的 O 复杂性是多少，但我猜想像 n 2之类的东西。
4

4 回答 4

7

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

这是一个 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)))
于 2016-07-01T18:22:45.150 回答
4

如果有一些分母导致您的输入之间有一个有理数，那么假设分子是好的。

您可以检查 O(1) 中的分子是否良好。假设你想检查一个分子 n，你的输入是 w,x（对于 w/x）和 y,z（对于 y/z）。

如果 n x/w 和 n z/y之间有一个整数，则 n 是好的。

然后，您可以在 O(good numerator) 中执行此操作，方法是检查所有分子，直到找到一个好的分子。如果端点有效，则最多需要 min(w,y)。

于 2016-07-01T09:59:25.243 回答
3

这是David Eisenstat上面出色答案的变体。秘密地，它基于完全相同的原理，即找到区间端点的连分数展开的共同初始部分，但这从它的编码方式中并不明显，并且无需参考即可直接提供正确性证明连分数理论。下面进一步给出了该证明的草图。

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

编码

事不宜迟，这是我们版本的simplest_between. 解释和正确性证明的草图如下。

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- 应该是不言自明的：如果区间(x, y)完全位于负实数中，我们使用关于零的对称性并在 中找到最简单的分数(-y, -x)，然后取反。否则，如果区间(x, y)包含零，则0/1是 中最简单的分数(x, y)。否则，(x, y)位于正实数内，我们继续代码的第二部分。

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

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

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

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

在循环退出时， in 中的每个分数都(x, y)具有(ap + bq)/(cp + dq)某些分数p/q(with gcd(p, q) = 1) in的形式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)
于 2020-12-07T20:49:12.943 回答
0

您可以尝试以下O(n^2 log n)算法：

  • 从一个分子循环到另一个分子
  • 在这个循环中，从一个分母循环到另一个分母。引理是循环创建的每个分数都在两个末端分数之间。
  • 对于每个分数，通过找到分子和分母的最大公约数来简化它，然后将分子除以它。这应该使您能够找到最小的分子。欧几里得算法在 O(log n) 中完成此操作。
于 2016-07-01T09:37:16.743 回答