はじめに
今回はフィボナッチ数列のお話です
なお、本記述はMacにおいて、Railsでの開発を前提としています
また、まだまだひよっこですので、不備等ございましたらご指摘いただけると幸いです
＊追記
コメント欄に簡潔なコードがありますので、そちらもご覧ください
元の記述は自分が考えた軌跡として残しておきます
目次
- フィボナッチ数列とは
- プログラムで解いてみる
フィボナッチ数列とは
初項 = 1、第２項 = 1、第３項以降は、前項と前々項の和となる数列です
第３項は初項と第２項の和なので「1+1」で"2"となります
第４項は第２項と第３項の和なので"3"となります
また、フィボナッチ数列は黄金比とも関係してるので、知りたい方は調べてみてください
数列としては、「1,1,2,3,5,8,13,21,34,55,・・・」と続きます
この数列の第n項目は何になるかを求めたいと思います
プログラムで解いてみる
では、プログラムで解いてみましょう
まずは、フィボナッチ数列がどういうものだったかを思い出しましょう
fib(n) = fib(n-2) + fib(n-1)
第n項は前(n-1)項と前々(n-2)項の和でしたよね
しかし、初項と第２項は決まっています
付け加えましょう
fib(n) = fib(n-2) + fib(n-1)
fib(0) = 1
fib(1) = 1
できました
このままではプログラムとしては成り立っていませんので、組み立てましょう
def fib(n)
if n == 0 || n == 1
return 1
else
fib(n-2) + fib(n-1)
end
end
できました
しかし、このプログラムには欠点があります
fib(4)で解説しましょう
fib(4) = fib(3) + fib(2)
ですね
でも、fib(3)とfib(2)も求めないといけないですよね
そうすると
fib(4) = fib(3) + fib(2)
fib(3) = fib(2) + fib(1)
fib(2) = fib(1) + fib(0)
こうなりますが、fib(3)の中にもfib(2)が入っていますね
そうするとこうなります
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程度でギブアップするなんて使えないコードです
そこで、メモ化というものを使います
配列に入れてしまいましょう
メモ化の特徴としては、記憶領域と引き換えに、時間のコストを削減するというものがあります
いわゆるトレードオフをする必要があるということです
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
できました
変更点は、配列をつくって、それに入れている部分です
しかしこれでは数学的には間違っているので、対話型のプログラムにしつつ正しくしましょう
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
できました
数学的な一般項はなかなか複雑ですが、プログラム上での一般項（？）はわかりやすくていいですね