10

有理数に関する問題を見つけました。

2 つの有理数が与えられ、タスクはそれらの間で最も単純な有理数を見つけることです。

この問題の場合、有理数の単純さは最小の分子を持つ有理数として定義できますが、このメトリックに対する他の提案、たとえばMath stack exchange への同様の質問など、解決が容易になる場合は自由です。

サンプルの入力と出力は次のようになります。

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

この問題に取り組む方法についてのアイデアや少なくともアドバイスはありますか? 私は苦労しています。

ありがとう

編集：

追加の観察:

  • 与えられた 2 つの有理数の間には無限に多くの有理数がありますが、実際には 2 つより単純な有理数は有限に多くあります。
  • 単純な解決策は、分子/分母のすべての組み合わせ (それぞれ 1 から最大の分子または分母までの範囲) を試し、それらを減らし、数値がその間にあるかどうかを確認することです。O の複雑さがどうなるかはわかりませんが、 n 2のようなものだと思います。
4

4 に答える 4

7

関連する数学は、連分数に関するウィキペディアの記事で説明されています。簡単に言うと、下端と上端の 2 つの連分数を計算し、共通端点の後で連分数が切り捨てられる 4 つの組み合わせを試します。

これが 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 に答える
0

O(n^2 log n)次のアルゴリズムを試すことができます。

  • ある分子から別の分子へのループ
  • このループ内で、1 つの分母から別の分母にループします。レンマは、ループによって作成された各分数が 2 つの最後の分数の間にあるということです。
  • 分数ごとに、分子と分母の最大公約数を求めて単純化し、それで分子を割ります。これにより、最小の分子を見つけることができます。ユークリッドのアルゴリズムはこれを O(log n) で行います。
于 2016-07-01T09:37:16.743 に答える