Fibonacciシーケンス計算機python

Question

こんにちは私はかなり新しいPythonで、入力された数値がシーケンス内にない場合は、次のフィボナッチ数を加算して、指定された数値まですべての値を出力するフィボナッチ計算関数を作成しようとしています。リスト。たとえば、10を入力すると、[0, 1, 1, 2, 3, 5, 8, 13]が返されます。関数は再帰的でなければならない。私は大規模なプログラムを変更することなく、それをスピードアップすることができますとにかく（私は再帰によるものと仮定）

def fibonacci(n): 
    n = int(n) 
    # The nested sub_fib function computes the Fibonacci sequence 

    def sub_fib(n): 
     if n < 2: 
      return n 
     else: 
      return (sub_fib(n-1) + sub_fib(n-2)) 

    #This aspect of the main fib function applies the condition if the number 
    # input is not in the sequence then it returns the next value up 

    fib_seq= [sub_fib(i) for i in range(0,n) if sub_fib(i)<=n] 
    if fib_seq[-1] < n: 
     fib_seq.append(fib_seq[-1] + fib_seq[-2]) 
     return fib_seq 
    else: 
     return fib_seq 
print(fibonacci(input("Input a number to print sequence up to: "))) 

が、私はそれが仕事を得ることができたが、それは非常に遅いですがされています。ここに私の現在のコードはありますか？

Answer 1

あなたのプログラムが遅い2つの主な理由：

• あなたは、あなたが以前の番号を見つけるに投資していない再利用努力を行い、別途各フィボナッチ数を計算します。
• 最初にnフィボナッチ数を計算しますが、の条件が満たされない瞬間から、を停止することができます。

は、あなたはまだ再帰するプログラムを変更することができますが、再利用仕事は、以前の数を計算し、あなたがリストを構築した瞬間から停止します。

あなたは、単に次の関数を使用する必要があります。

def fibon(a,b,n,result): 
    c = a+b 
    result.append(c) 
    if c < n: 
     fibon(b,c,n,result) 
    return result 

を、我々はで初期化：fibon(0,1,n,[])。各反復では、次のフィボナッチ数c = a+bを計算し、resultに追加します。数字がまだc < nより小さい場合は、次の数値を計算して再帰呼び出しを実行する必要があります。

def fibonacci(n): 
    n = int(n) 

    def fibon(a,b,n,result): 
     c = a+b 
     result.append(c) 
     if c < n: 
      fibon(b,c,n,result) 
     return result 

    return fibon(0,1,n,[]) 

print(fibonacci(input("Input a number to print sequence up to: "))) 

Answer 2

これは、再帰を使用していますが、はるかに高速素朴な​​再帰的な実装よりも

def fib(n): 
    if n == 1: 
     return [1] 
    elif n == 2: 
     return [1, 1] 
    else: 
     sub = fib(n - 1) 
     return sub + [sub[-1] + sub[-2]]