pythonで制限時間内に最大のフィボナッチ数を見つける

Question

フィッシュナッチ数を計算するコードと、それを計算するのに使われた時間をPythonで求めるコードが必要です。

def fib(n): 
    if n==0 or n==1: return 1 
    else: return fib(n-1)+fib(n-2) 

数値ステップの計算では、このような方法を使用する必要があります。

Answer 1

は、時間に関数をtimeitモジュールを使用します。

import timeit 

def fib(x): 
    if x==0 or x==1: return 1 
    else: return fib(x-1)+fib(x-2) 

print timeit.Timer('fib(5)', 'from __main__ import fib').timeit() 

出力：

3.12172317505 

を

time.time()を使用すると、エポックからの現在の時間を秒単位で取得し、制限時間に達するまで次のフィボナッチ数を計算し続けることができます。私は、あなたにこのコンセプトのより良いデモンストレーションを与えるために、以下のフィボナッチ数を計算する効率的な方法を使用することを選択しました。

def fibTimeLimited(limit): 
    start = time.time() 
    n, f0, f1 = 1, 0, 1 
    while time.time() < start + limit: 
    n += 1 
    f0, f1 = f1, f0+f1 
    return (n, f1) 

出力例：

Calculated 1st fibonacci number as 1 in 0.000001 seconds 
Calculated 31st fibonacci number as 1346269 in 0.000010 seconds 
Calculated 294th fibonacci number as 12384578529797304192493293627316781267732493780359086838016392 in 0.000100 seconds 

Answer 2

これはメモの問題を伴う古典的な動的プログラミング/再帰です。あなたのコードでは、fib(x-1)lotを再帰的に呼び出します。これは大きな労力を浪費します。一度計算したら、後で使用するために保存して、再度計算する必要はありません。誰もがまだのPython 3.2を使用しないためのPython 3ではあなたは、栄光のfunctools.lru_cache残念ながら

@lru_cache(maxsize=None) 
def fib(n): 
    if n < 1: 
     return n 
    else: 
     return fib(n - 1) + fib(n - 2) 

でこれを行うことができ、あなた自身を記述する必要があります。ここではいくつかの擬似コードです：

cache = {0: 0, 1: 1} 
def fib(n): 
    if n in cache: 
     return the cached value 
    else: 
     calculate fib(n) recursively 
     store the value in the cache 
     return the value 

この技術は、メモ化再帰と呼ばれています。時間に

fibs = [0, 1] 
for i in range(2, n): 
    calculate fibs[i] using the previous values in fibs 
    append the new value 

---

これらの関数、モジュール（.pyで終わるファイル）でそれらを入れてからtimeitを使用します。ボトムアップからの値を計算する：等価的に、あなたは動的プログラミングを使用することができますコマンドライン：ところで

(change directory to the one containing your module) 
python -mtimeit "import <name of module>" "fib(3000)" 

---

、n番目のフィボナッチ数の閉形式があり、これはより高速/より有用であることを証明し得る：

Answer 3

ここでは、代わりに再帰のPythonのタプルを使用して非常に簡単な例です。

import time 

def fib(n): 
    cnt = 1 
    if n == 0: 
     return a 
    a = 0 
    b = 1 
    while n > cnt: 
     (a, b) = (b, b+a) 
     cnt += 1 
    return b 

start = time.time() 
result = fib(15) 
runTime = time.time() - start 

print result, runTime