argius note

プログラミング関連

フィボナッチ数列

これももう、やりつくされているであろう例題。数式に近い形で関数定義ができました。

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

main = print $ map fibonacci [1..30]

確かにこれでも計算はできますが、30だとやっと耐えられる程度の処理時間です。40にすると、数分かかってしまいます。それ以降も、求められた値に比例した実行時間を浪費してしまいます。詳しくは分かりませんが、単純に値の回数分の再帰が発生しているからでしょうか。
そこで、公式を使った方法で書き直してみました(参考:フィボナッチ数 - Wikipedia)。

root5 = sqrt 5 :: Float
goldenRatio = ( 1 + root5 ) / 2 :: Float
              
fibonacci n = floor $ goldenRatio ^ n / root5 + 0.5

main = print $ map fibonacci [1..100]

この場合だと、100にしても一瞬で計算が終わります。(200だと、直前でIntがオーバーフローします。)