フィボナッチ数列を求めるプログラム

フィボナッチ数列のn項目を求めるプログラムを複数の記述で書いてみる。

フィボナッチ数列とは？

２つ前の項と１つ前の項を足し合わせていくことでできる数列。

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

足していくと大きな長方形ができていく。

アンモナイトの渦巻や宇宙などだんだん大きくなる渦巻がフィボナッチ数列。

スティール・ボール・ランの黄金の長方形もフィボナッチ数列。

## 【方法１】メソッドの活用

def fib(n):
  arr = [1,1]
  for j in range(n-1):
    val = arr[j] + arr[j+1] 
    arr.append(val) 

  return (arr[len(arr)-1])

確認

n=35
for i in range(1, n):
  print(fib(i))

## 【方法２】再帰処理を使う関数の中で自身の関数を呼び出す、再帰処理(recrusive process)を使う。

forで指定条件を満たすまで繰り返すのと似ていて、return条件に該当するまで、同じ処理を繰り返す。

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

# 確認
n=35
for i in range(1, n):
  print(fib(i))

この処理は比較的時間がかかる。
これは、fib(n-1)とfib(n-2)の中でそれぞれ同じ計算を個別に計算しているためである。

fib(n-2)の方が一足先に計算をしてるのだから、その解をfib(n-1)にも応用すれば、計算時間をグッと減らすことができる。

この画期的な方法を動的計画法という。

## 【方法３】動的計画法を使う（再帰法）

# 変数のみだとmemoがグローバル変数になるため、defで囲みローカル変数にする
def fib_memo(n):
  #関数処理が終わっても値が残るようfib(n)の外に出す
  memo = [None]*(n+1)  #n+1個の空要素が入った配列を用意

  def _fib(n):
    if n==0 or n==1:
      return 1
    if memo[n] != None:  #指定した値の要素がNone以外なら、その値を利用（※初期値は全てNone）
      return memo[n]
    memo[n] = _fib(n-1) + _fib(n-2) #Noneの場合は足し合わせた数値を代入
    return memo[n]
  
  return _fib(n)

確認

n=40
for i in range(0, n):
  print(fib_memo(i))

・None：空であることを明示（noneオブジェクト）
・_関数名: ローカルでのみ使用する関数を示唆

計算処理はかなり早くなる。

## 【方法４】動的計画法（for文）

再帰法ではなく、メモ法で小さい数値から一つづつ計算していくパターンも可能。

def fib_dp(n):
  memo = [None]*n
  memo[0] = 1
  memo[1] = 1
  for i in range(2, n):
    memo[i] = memo[i-1] + memo[i-2]
  return memo