3

現在、私はProject Euler 71を解決しようとしています。

n と d が正の整数である分数 n/d を考えてみましょう。nの場合

d ≤ 8 の簡約された固有分数のセットをサイズの昇順にリストすると、次のようになります。

1/8、1/7、1/6、1/5、1/4、2/7、1/3、3/8、2/5、3/7、1/2、4/7、3/ 5、5/8、2/3、5/7、3/4、4/5、5/6、6/7、7/8

2/5 は 3/7 のすぐ左側の分数であることがわかります。

d ≤ 1,000,000 の簡約された固有分数のセットをサイズの小さい順にリストすることにより、3/7 のすぐ左にある分数の分子を見つけます。

現在のコード:

from fractions import Fraction
import math

n = 428572
d = 1000000

x = Fraction(3,7)

best = Fraction(0)

while d > 1:
    if Fraction(n,d) >= x:
        n-=1
    else:
        y = Fraction(n,d)
        if (x - y) < (x - best):
            best = y
        d -= 1
        n = int(math.ceil(d*0.428572))

print(best.denominator)

説明：

from fractions import Fraction
import math

分数と math.ceil に必要です。

n = 428572
d = 1000000

これら 2 つの変数は、元の問題で述べられているnと を表します。d数値はこのように始まります。これは、3/7(後で Fraction に変換されます) のわずかに大きな表現であるためです。

x = Fraction(3,7)

best = Fraction(0)

x は単なるクイック リファレンスなFraction(3,7)ので、入力し続ける必要はありません。どの分数が最も近いが、まだ残ってbestいるかを追跡するために使用されます。3/7

while d > 1:

d <= 1andnが以下でなければならない場合1、チェックのポイントは何ですか? チェックを停止します。

if Fraction(n,d) >= x:
    n-=1

分数が左にない以上の分数になる場合は、左にあるまで3/7から減算し続けます。n3/7

    else:
        y = Fraction(n,d)
        if (x - y) < (x - best):
        best = y

それが の左側にある3/7場合は、3/7マイナスbestまたはy(チェックする必要がある分数に等しい) が 0 に近いかどうかを確認し3/7ます。

        d -= 1
        n = int(math.ceil(d*0.428572))

ベストが変わるかどうかに関係なく、分母を変更する必要があります。したがって、分母から 1 を引き、Fraction(n,d) の n を少し大きく設定します (それが大きくなることを確認するために追加の ceil メソッドを追加しました!) 3/7、テスト スペースを削除します。

print(best.denominator)

最後に、質問が求めているものを出力します。

ノート

dto8とnto を4(テスト ケースのように)変更すると5、分母の目的の結果が得られます。そのままにしておくと、次のようになります999997。

誰かが私が間違っていることを説明してもらえますか?

4

3 に答える 3

4

これは正しいやり方ではありません。Stern-Brocot ツリーを使用することになっています。浮動小数点をいじる必要はまったくありません。

于 2012-07-01T05:01:02.473 に答える
2

あなたが間違っていること：

分子を見つける

それとは別に、@Antimony のアドバイスに従い、Stern-Brocot ツリーについて学びましょう。これは便利で楽しいものです。

于 2012-07-01T05:06:13.330 に答える
1

愚かな気分にさせないために。しかし、あなたの答えは完全に正しいです。質問をもう一度読んで、最後の行を次のように変更してください。

print( best.numerator )

また、記録のために、これを計算するはるかに効率的な方法があります。

于 2012-07-01T05:12:45.873 に答える