1

私は Python にはかなり慣れていませんが、この言語を使いこなすために、フィボナッチ ジェネレーターを再帰的に作成するという課題に直面しました。問題は、フィボナッチ数が 3226/3227 を超えると、Python がクラッシュすることです。(パイソン3)

注: 私は PHP、JavaScript、VBA と Java で多くのプログラミングを行ってきましたが、Python はまったくの初心者です。もしこれが単純に間違ったデータ型か何かの問題であるなら、本当に申し訳ありません。

import sys
sys.setrecursionlimit(1000000000)

cache = dict()

 def fibonacci(n, arr = False):
    global cache

    if n == 0 or n == 1:
         r = n
    else:
        nVal1 = n - 1
        nVal2 = n - 2
        if (not nVal1 in cache):
            num1 = cache[nVal1] = fibonacci(nVal1, arr)
        else:
            num1 = cache[nVal1]
        if (not nVal2 in cache):
            num2 = cache[nVal2] = fibonacci(nVal2)
        else:
            num2 = cache[nVal2]

        r = num1 + num2


     if arr != False:
        arr.append(r)


    return r

fib = list()
# 3227 is max without generating a list.
# 3226 is max when generating a list.
fibonacci(3226, fib)
for x in fib: print(x)

これよりも先に進めるにはどうすればよいですか?これは遅いi3ラップトップで約2秒で実行されるため、メモリが不足しているとは思いません..

4

2 に答える 2

2

sys.setrecursionlimitからメモを読む

可能な上限はプラットフォームによって異なります。深い再帰を必要とするプログラムと、より高い制限をサポートするプラットフォームがある場合、ユーザーはより高い制限を設定する必要がある場合があります。制限が高すぎるとクラッシュする可能性があるため、これは慎重に行う必要があります。

私はそのようにfiboを実装します

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

fibs = fib()
fibo = [next(fibs) for i in xrange(100)]
于 2013-01-26T23:42:26.320 に答える
2

Pythonインタープリターで許可されている最大スタック深度を超えていると思います。新しい関数にさらに進むと、最終的にスタックに収まるように Python VM によって割り当てられたメモリの量を使い果たします。

http://docs.python.org/library/sys.html#sys.setrecursionlimitを特定のポイントに変更できますが、深さの最大値は実装で定義されています。

于 2013-01-26T23:42:47.207 に答える