カテゴリー: Project Euler

フィボナッチ数列の新しい項は直前の二つの項の和を求めることで生成される。 1および2から開始した最初の10項は1,2,3,5,8,13,21,34,55,89, …となる。
4000000以下のフィボナッチ数列のうち、全ての偶数の項の和をもとめよ。

フィボナッチ数列というのがまたHaskellの利点を最大限にアピールできるよう な問題のひとつである。これは頻出なのでGoogle先生が教えてくれると思うが、 Haskellでは必要になるまで式を評価しないので無限の数列を非常に簡単に表せ る。よくあるフィボナッチ数列の定義はこんな感じ。

fib = 1 : 1 : zipWith (+) fib (tail fib)

takeWhileはリストを前から順番に調べていって、条件が成立しつづけていると ころまで取り出す関数である。これで無限に続くフィボナッチ数列のリストか ら4000000以下の部分を取り出すことが出来る。filterはリスト全体の中から条 件を満たしている要素だけを取り出したリストを作る関数である。これで偶数 (even)の部分を取り出すことが出来る。最後に関数sumを用いて全てのリストの 要素の和を求めると答えとなる。

euler002 = sum $ filter even $ takeWhile (<= 4000000) fib

10より小さい自然数で3または5の倍数である ものを全て列挙すると3,5,6,9である。またその和は23になる。

1000より小さい全ての3または5の倍数の和を求めよ。

まずは小手調べ的な問題。FizzBuzzと言われているものの派生といった感じか。 こういう問題をHaskellなら直感的にそのままプログラムにできる。まずリスト の内包表記という便利なものがあって、以下のように、|の後ろの条件を満たす 要素n全てという風にリストが定義できる。これで問題文の1000より小さい3ま たは5の倍数というのをそのまま書くと、nは1から999までの数で、n を3で割っ たあまりが0もしくは5で割ったあまりが0の数でできたリストが生成される。

sumという関数はリストのすべての要素の和を求めるのでこれで問題の解答が得 られるというわけだ。modは余りを求める関数であるが`mod`のようにバックク オートでくくることで演算子のように用いることができる。

euler001 = sum [n | n <- [1..999], n `mod` 3 == 0 || n `mod` 5 == 0]

Project Eulerというサイトがある。 数学的な（とはいっても専門知識を必要とするようなものではない）問題を解 いて答えを入力すると正解かどうか判定してくれるというものだ。問題はどれ も人間が手で計算するにはちょっと面倒な設定になっていて、問題を解くプロ グラムを書いて答えを求めるように意図されている。アカウントを作成して参 加し、正解した問題にはチェックがつくというゲーム的な演出もあり、プログ ラムの演習的な題材としてよくできている。

最近（最近でもないが）Haskellに興味があるのだが、ただ興味があるだけでは なかなか身に着かないものなので、Haskellの練習もかねてこのProject Euler の問題に挑戦してみようと思う。Haskellのような関数型言語はこういう演習的 な問題を解くのに適しているので、練習の題材としてはちょうどいいと思う。

Haskellの環境を準備するのはこのページの本題ではないので割愛するというか Googleで調べてもらえばいろいろあると思う。とりあえず使用する処理系は ghc。Fedoraマシンで実行しているのでyum install ghcでインストールできた。 エディタはemacs。 haskell-mode というのを使えば色もつくし自動でインデントしてくれるので便利だ。という かHaskellの場合レイアウトを使うのが普通なのでインデントしてくれないとか なり大変。他に はhrefというツー ルもオススメ。これはコマンドラインから使えるHaskellのリファレンスマニュ アルで、日本語で説明してあって例もあるので非常に便利だ。