top page > computer > haskell > web_lecture > for_programmer > fibonacci.html
更新日:
文責: 重城良国

フィボナッチ数列

fibonacci.hs

はじめに

フィボナッチ数列の定義の美しさを見よ。

フィボナッチ数列とは

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

とりあえず隣り同士の差を

どういうルールで並んでいるのだろうか。隣りの数同士の差をとる。1 - 0 = 1, 1 - 1 = 0, 2 - 1 = 1, 3 - 2 = 1, 5 - 3 = 2, ...

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

はじめの1以外はもとの数列と同じ数列になる。

どういうことだ

フィボナッチ数列の項は直前ふたつの項の和となっている。

0, 1で始まり3項目以降は直前の2項の和になっている。

美しさへの序曲

つまりこうなる。

0 1 1 2 3 05 08 13 21 34 055 089 144 ...
+1 1 2 3 5 08 13 21 34 55 089 144 233 ...
-----------------------------------------------------
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 ...

フィボナッチ数列は0, 1のあとに自身と自身の頭をとったものの和が続いたものだ。

定義

fibs, tfibs :: [Integer]
fibs@(_ : tfibs) = 0 : 1 : zipWith (+) fibs tfibs

ghci fibonacci.hs
*Main> take 15 fibs
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377]

まとめ

Excellent!

課題

  1. 0, 1で始まり前の値の2倍と今の値を足した値が次の値になるような数列を作れ

「関数zipWithの紹介」へもどる 「1から学ぶHaskell」トップへ

正当なCSSです! HTML5 Powered with CSS3 / styling, and Semantics