1

Project Eulerの問題＃2を実行しようとしています。それは次のとおりです。

フィボナッチ数列の新しい各項は、前の 2 つの項を追加することによって生成されます。1 と 2 から始めると、最初の 10 項は次のようになります。

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

値が 400 万を超えないフィボナッチ数列の項を考慮して、偶数値の項の合計を見つけます。

ただし、次のコードを 4000000 で使用すると、ターミナル ウィンドウがハングします。小さい数値でも問題なく動作します。このコードには本当に効率が悪いものがあるのでしょうか?

n = int(raw_input("Enter the start number: "))

def fib_generator():
    a, b = 0, 1
    yield 0
    while True:
        a, b = b, a + b
        yield a

def even_sum(fib_seq):
    seq = []
    seq = [next(fib_seq) for number in range(n)]
    seq = [number for number in seq if number % 2 == 0]
    return sum(seq)

def start():
    fib = fib_generator()
    even_sum = even_sum(fib)
    print even_sum

start()
4

4 に答える 4

4

バグがあります。最初の 4,000,000 個のフィボナッチ数を生成していますが、問題ステートメントは、値が 4,000,000 以下のフィボナッチ数のみを求めています。

フィボナッチ数は指数関数的に増加するため (F n ~ 1.618 n )、桁数が非常に多い数 (log 10 F n ~ n / 5) を生成することになり、膨大な時間がかかります。

バグを修正すれば、大丈夫です。

于 2013-07-25T01:01:12.083 に答える
2

次のフィボナッチ数が 4000000 を超えたときに停止するロジックを追加するだけです。

また、次の行の潜在的な問題をスパイします。

def start():
    fib = fib_generator()
    even_sum = even_sum(fib) #<--- right here
    print even_sum

関数名と変数名を同じにするのはよくありません。

于 2013-07-25T01:04:32.273 に答える
0

はい、あなたのコードには非効率的なものがあります.2つのseq = ...ステートメントで非常に長いリストを2回メモリにロードします. 2 つのリスト内包表記ではなく、1 つのジェネレーター式を試してみませんか? また、特定の数値で停止するようにフィボナッチ ジェネレーターを変更することもできます。

def fib_generator(n):
    a, b = 0, 1
    while a < n:
        yield a
        a, b = b, a + b

def even_sum(fib_seq):
    seq = (number for number in fib_seq if not number % 2)
    return sum(seq)

def start():
    n = int(raw_input('Enter max constraint: '))
    fib_seq = fib_generator(n)
    even_sum1 = even_sum(fib_seq)
    print even_sum1

start()
于 2013-07-25T05:33:50.017 に答える