PythonプログラムのN番目のフィボナッチ数

この記事では、n番目のフィボナッチ数を計算します。

フィボナッチ番号 以下に示す繰り返し関係によって定義されます：

Fn =Fn-1 + Fn-2

F ₀を使用 =0およびF₁ =1。

最初のいくつかのフィボナッチ番号は0、1、1、2、3、5、8、13、..................

再帰と動的計画法の方法を使用してフィボナッチ数を計算できます。

それでは、Pythonスクリプトの形式での実装を見てみましょう

アプローチ1：再帰方法​​

例

#recursive approach
def Fibonacci(n):
   if n<0:
      print("Fibbonacci can't be computed")
   # First Fibonacci number
   elif n==1:
      return 0
   # Second Fibonacci number
   elif n==2:
      return 1
   else:
      return Fibonacci(n-1)+Fibonacci(n-2)
# main
n=10
print(Fibonacci(n))

出力

34

宣言されたすべての変数のスコープを以下に示します

アプローチ2：動的計画法

例

#dynamic approach
Fib_Array = [0,1]
def fibonacci(n):
   if n<0:
      print("Fibbonacci can't be computed")
   elif n<=len(Fib_Array):
      return Fib_Array[n-1]
   else:
      temp = fibonacci(n-1)+fibonacci(n-2)
      Fib_Array.append(temp)
      return temp
# Driver Program
n=10
print(fibonacci(n))

出力

34

宣言されたすべての変数のスコープを以下に示します

結論

この記事では、再帰と動的計画法のアプローチを使用したn番目のフィボナッチ数の計算について学びました。