はじめに

今回はフィボナッチ数列のお話です
なお、本記述はMacにおいて、Railsでの開発を前提としています
また、まだまだひよっこですので、不備等ございましたらご指摘いただけると幸いです
＊追記
コメント欄に簡潔なコードがありますので、そちらもご覧ください
元の記述は自分が考えた軌跡として残しておきます

目次

フィボナッチ数列とは
プログラムで解いてみる

フィボナッチ数列とは

初項 = 1、第２項 = 1、第３項以降は、前項と前々項の和となる数列です
第３項は初項と第２項の和なので「1+1」で"2"となります
第４項は第２項と第３項の和なので"3"となります
また、フィボナッチ数列は黄金比とも関係してるので、知りたい方は調べてみてください
数列としては、「1,1,2,3,5,8,13,21,34,55,・・・」と続きます

この数列の第n項目は何になるかを求めたいと思います

プログラムで解いてみる

では、プログラムで解いてみましょう
まずは、フィボナッチ数列がどういうものだったかを思い出しましょう

.rb

fib(n) = fib(n-2) + fib(n-1)

第n項は前(n-1)項と前々(n-2)項の和でしたよね
しかし、初項と第２項は決まっています
付け加えましょう

.rb

fib(n) = fib(n-2) + fib(n-1)
fib(0) = 1
fib(1) = 1

できました
このままではプログラムとしては成り立っていませんので、組み立てましょう

.rb

def fib(n)
  if n == 0 || n == 1
    return 1
  else
    fib(n-2) + fib(n-1)
  end
end

できました

しかし、このプログラムには欠点があります
fib(4)で解説しましょう

.rb

fib(4) = fib(3) + fib(2)

ですね
でも、fib(3)とfib(2)も求めないといけないですよね
そうすると

.rb

fib(4) = fib(3) + fib(2)
fib(3) = fib(2) + fib(1)
fib(2) = fib(1) + fib(0)

こうなりますが、fib(3)の中にもfib(2)が入っていますね
そうするとこうなります

.rb

fib(4) = fib(3) + fib(2)
  fib(3) = fib(2) + fib(1)  #fib(4)の中のfib(3)を求める式
    fib(2) = fib(1) + fib(0)  #fib(3)の中のfib(2)を求める式
  fib(2) = fib(1) + fib(0)  #fib(4)の中のfib(2)を求める式

ここで違和感というか、無駄が発生していることにお気づきでしょうか
fib(2)は２回、fib(1)とfib(0)は３回出てきています
nが小さい時はあまり問題がありませんが、n=30くらいになると、答えが返ってくるまでに時間がかかります
n=35で２秒ほどかかります
n=100では計算が終わらないようですので、実行はしないようにしましょう

メモ化を使う

問題が発見されたので、変更しないといけませんね
使えないこともないコードならまだしも、n=100程度でギブアップするなんて使えないコードです
そこで、メモ化というものを使います
配列に入れてしまいましょう
メモ化の特徴としては、記憶領域と引き換えに、時間のコストを削減するというものがあります
いわゆるトレードオフをする必要があるということです

.rb

F = []
def fib(n)
  if n == 0 || n == 1
    return 1
  elsif F[n] != nil #ここだけのプログラムであれば不要（関与しない）
    return F[n]
  else
    F[n] = fib(n - 2) + fib(n - 1)
  end
end

できました
変更点は、配列をつくって、それに入れている部分です
しかしこれでは数学的には間違っているので、対話型のプログラムにしつつ正しくしましょう

.rb

F = []
def fib(n)
  if n == 0 || n == 1
    return 1
  elsif F[n] != nil 
    return F[n]
  else
    F[n] = fib(n - 2) + fib(n - 1)
  end
end

p "フィボナッチ数列の何項目が知りたいん？うちが教えたるで"

num = gets.to_i

if num >= 1
  p fib(num-1)
else
  p "ちゃんと入力しやん人はいややぁ"
end

できました
数学的な一般項はなかなか複雑ですが、プログラム上での一般項（？）はわかりやすくていいですね